|
| |
|
|
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.
|
|
36
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
Cox, David A., Galois Theory, John Wiley & Sons, Hoboken, New Jrsey, 2004, 235.
Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, pp. 92-93, 1993.
|
|
|
LINKS
|
|
|
|
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
|
|
|
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},
|
|
|
PROG
|
(PARI) a(n)=if(n<=2, 1, #znstar(n)[3]); \\ Joerg Arndt, Aug 26 2014
|
|
|
CROSSREFS
|
Cf. A046073 (number of squares in multiplicative group modulo n), A281855, A282625 (for total factorization).
|
|
|
KEYWORD
|
nonn,nice
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
