A282625 Number of cyclic groups in the total direct product factorization of the multiplicative group of integers modulo n, for n >= 1.

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

Offset: 1

Author

Wolfdieter Lang, Mar 02 2017

Keywords

• nonn

Comments

The multiplicative group of integers modulo n, (Z/n*Z)^x, also the cyclotomic group, the Galois group Gal(Q(zeta(n))/Q) with zeta(n) = exp(2*Pi*I/n), is cyclic for n from A033948 and non-cyclic for n from A033949. Each of these groups is the direct product of cyclic factors (one factor is included).

In the total factorization for n >= 3 only cyclic factors whose orders are prime powers appear, and because the direct product is associative, and for these abelian groups also commutative, one can order the factors with nonincreasing orders.

For n=1 and n=2 the group is C_1 = {1} (for n=1 one has 1 == 0 (mod 1)).

Cyclic groups may also have a factorization into more than one factor. E.g., C_6 = C_3 x C_2.

The number of factors in this total factorization is for a cyclic group C_m, for m >= 2, given by A001221(m). For m=1 this number is 1 (not A001221(1)).

For non-cyclic groups the number of factors in this total factorization is given by A281855(m) if n = A033949(m), m >= 1.

For the non-cyclic group case see also the W. Lang links under A281854.

Compare this sequence with A046072 where another factorization of these groups is used, the one with the least cyclic factors. E.g., A046072(7) = 1 for the group C_6, and a(7) = 2 here (see the example above).

Examples

			n = 35, a non-cyclic case because A033949(12) = 35. The group can be written as <19_6, 13_4 > where the orders modulo 35 of the generators are given as subscript. Therefore the group is C_6 x C4 = C_4 x C_3 x C_2 and a(35) = 3, whereas A046072(35) = 2.
		

Crossrefs

Cf. A001221, A033948, A033949, A046072, A281854, A281855, A282624.