A046072 Decompose multiplicative group of integers modulo n as a product of cyclic groups C_{k_1} x C_{k_2} x ... x C_{k_m}, where k_i divides k_j for i < j; then a(n) = m.

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 1, 2, 2, 1, 1, 3, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 3, 1, 2, 1, 2, 2, 1, 1, 3, 1, 1, 2, 2, 1, 1, 2, 3, 2, 1, 1, 3, 1, 1, 2, 2, 2, 2, 1, 2, 2, 2, 1, 3, 1, 1, 2, 2, 2, 2, 1, 3, 1, 1, 1, 3, 2, 1, 2, 3, 1, 2, 2, 2, 2, 1, 2, 3, 1, 1, 2, 2, 1, 2

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 = 0 and 1 (otherwise one could have arbitrarily many leading C_1 factors for n >= 3). - Wolfdieter Lang, Mar 07 2017

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, A281855, A282625 (for total factorization).

a(n)=k iff n is in: A033948 (k=1), A272592 (k=2), A272593 (k=3), A272594 (k=4), A272595 (k=5), A272596 (k=6), A272597 (k=7), A272598 (k=8), A272599 (k=9).

Sequence in context: A071891 A359306 A332761 * A072273 A157230 A034380

Adjacent sequences: A046069 A046070 A046071 * A046073 A046074 A046075

Keyword

nonn,nice,easy

Author

Eric W. Weisstein

Status

approved