login
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.
36

%I #87 Sep 21 2024 08:41:50

%S 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,

%T 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,

%U 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

%N 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.

%C 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

%C 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

%C 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

%C 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

%D David A. Cox, Galois Theory, John Wiley & Sons, Hoboken, New Jrsey, 2004, 235.

%D Daniel Shanks, Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, pp. 92-93, 1993.

%H Joerg Arndt, <a href="/A046072/b046072.txt">Table of n, a(n) for n = 1..10000</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ModuloMultiplicationGroup.html">Modulo Multiplication Group</a>.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n">Multiplicative group of integers modulo n</a>. See the table at the end.

%F 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

%F 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

%t f[n_] := Which[OddQ[n], PrimeNu[n], EvenQ[n] && ! IntegerQ[n/4],

%t PrimeNu[n] - 1, IntegerQ[n/4] && ! IntegerQ[n/8], PrimeNu[n],

%t IntegerQ[n/8], PrimeNu[n] + 1]; Join[{1, 1},

%t Table[f[n], {n, 3, 102}]] (* _Geoffrey Critzer_, Dec 24 2014 *)

%o (PARI) a(n)=if(n<=2, 1, #znstar(n)[3]); \\ _Joerg Arndt_, Aug 26 2014

%Y Cf. A001221, A046073 (number of squares in multiplicative group modulo n), A077761, A281855, A282625 (for total factorization).

%Y 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).

%K nonn,nice,easy

%O 1,8

%A _Eric W. Weisstein_