A023135 Number of cycles of function f(x) = 3x mod n.

1, 2, 1, 3, 2, 2, 2, 5, 1, 4, 3, 3, 5, 4, 2, 7, 2, 2, 2, 7, 2, 6, 3, 5, 3, 10, 1, 7, 2, 4, 2, 9, 3, 4, 5, 3, 3, 4, 5, 13, 6, 4, 2, 9, 2, 6, 3, 7, 3, 6, 2, 15, 2, 2, 6, 13, 2, 4, 3, 7, 7, 4, 2, 11, 10, 6, 4, 7, 3, 10, 3, 5, 7, 6, 3, 7, 6, 10, 2, 23, 1, 12, 3, 7, 7, 4, 2, 15, 2, 4, 18, 9, 2, 6, 5, 9, 3, 6, 3, 11

Offset: 1

Author

David W. Wilson

Keywords

• nonn

Comments

Number of factors in the factorization of the polynomial x^n-1 over GF(3). - T. D. Noe, Apr 16 2003

Examples

			a(15) = 2 because (1) the function 3x mod 15 has the two cycles (0),(3,9,12,6) and (2) the factorization of x^15-1 over integers mod 3 is (2+x)^3 (1+x+x^2+x^3+x^4)^3, which has two unique factors. Note that the length of the cycles is the same as the degree of the factors.
		

References

• R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, 1983, p. 65.

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000005, A000374.

Cf. A023136, A023137, A023138, A023139, A023140, A023141, A023142.

Programs

Mathematica

Table[Length[FactorList[x^n - 1, Modulus -> 3]] - 1, {n, 100}]
CountFactors[p_, n_] := Module[{sum=0, m=n, d, f, i}, While[Mod[m, p]==0, m/=p]; d=Divisors[m]; Do[f=d[[i]]; sum+=EulerPhi[f]/MultiplicativeOrder[p, f], {i, Length[d]}]; sum]; Table[CountFactors[3, n], {n, 100}]

PARI

a(n)={sumdiv(n/3^valuation(n, 3), d, eulerphi(d)/znorder(Mod(3, d)));}
vector(100,n,a(n)) \\ Joerg Arndt, Jan 22 2024

Formula

a(n) = Sum_{d|m} phi(d)/ord(3, d), where m is n with all factors of 3 removed. - T. D. Noe, Apr 19 2003

a(n) = (1/ord(3,m))*Sum_{j = 0..ord(3,m)-1} gcd(3^j - 1, m), where m is n with all factors of 3 removed. - Nihar Prakash Gargava, Nov 14 2018