OFFSET
1,8
COMMENTS
The multiplicative group modulo n can be written as the direct product of a(n) (but not fewer) cyclic groups. - Joerg Arndt, Dec 25 2014
a(n) = 1 (that is, the multiplicative group modulo n is cyclic) iff n is in A033948, or equivalently iff A034380(n)=1. - Max Alekseyev, Jan 07 2015
This sequence gives the minimal number of generators of the multiplicative group of integers modulo n which is isomorphic to the Galois group Gal(Q(zeta_n)/Q), with zeta_n =exp(2*Pi*I/n). See, e.g., Theorem 9.1.11., p. 235 of the Cox reference. See also the table of the Wikipedia link. - Wolfdieter Lang, Feb 28 2017
In this factorization the trivial group C_1 = {1} is allowed as a factor only for n = 1 and 2 (otherwise one could have arbitrarily many leading C_1 factors for n >= 3). - Wolfdieter Lang, Mar 07 2017 [Corrected by Jianing Song, May 29 2026]
REFERENCES
David A. Cox, Galois Theory, John Wiley & Sons, Hoboken, New Jrsey, 2004, 235.
Daniel Shanks, Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, pp. 92-93, 1993.
LINKS
Joerg Arndt, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Modulo Multiplication Group.
Wikipedia, Multiplicative group of integers modulo n. See the table at the end.
FORMULA
a(n) = A001221(n) - 1 if n > 2 is divisible by 2 and not by 4, a(n) = A001221(n) + 1 if n is divisible by 8, a(n) = A001221(n) in other cases. - Ivan Neretin, Aug 01 2016
Sum_{k=1..n} a(k) = n * (log(log(n)) + B - 1/8) + O(n/log(n)), where B is Mertens's constant (A077761). - Amiram Eldar, Sep 21 2024
MATHEMATICA
f[n_] := Which[OddQ[n], PrimeNu[n], EvenQ[n] && ! IntegerQ[n/4],
PrimeNu[n] - 1, IntegerQ[n/4] && ! IntegerQ[n/8], PrimeNu[n],
IntegerQ[n/8], PrimeNu[n] + 1];
Join[{1, 1}, Table[f[n], {n, 3, 102}]] (* Geoffrey Critzer, Dec 24 2014 *)
PROG
(PARI) a(n)=if(n<=2, 1, #znstar(n)[3]); \\ Joerg Arndt, Aug 26 2014
CROSSREFS
Cf. A001221, A046073 (number of squares in multiplicative group modulo n), A077761, A102476 (earliest occurrences of each number), A258446 (table of invariant factors).
KEYWORD
nonn,nice,easy
AUTHOR
STATUS
approved