A327790 Decompose the multiplicative group of integers modulo n as a product of cyclic groups C_{k_1} X C_{k_2} X ... X C_{k_r}, where k_i > 1, k_i divides k_j for i < j; then a(n) = Product_{i=1..r} phi(k_i), phi = A000010.

1, 1, 1, 1, 2, 1, 2, 1, 2, 2, 4, 1, 4, 2, 2, 2, 8, 2, 6, 2, 2, 4, 10, 1, 8, 4, 6, 2, 12, 2, 8, 4, 4, 8, 4, 2, 12, 6, 4, 2, 16, 2, 12, 4, 4, 10, 22, 2, 12, 8, 8, 4, 24, 6, 8, 2, 6, 12, 28, 2, 16, 8, 4, 8, 8, 4, 20, 8, 10, 4, 24, 2, 24, 12, 8, 6, 8, 4, 24, 4, 18, 16, 40, 2, 16, 12

Offset: 1

Author

Jianing Song, Sep 25 2019

Keywords

• nonn

Comments

Related to A327791, which concerns the number of ways, up to the order, of decomposing the multiplicative group of integers modulo n to the inner direct product of cyclic subgroups. See the formula for it there.

Note that the choice of (k_1, k_2, ..., k_r) does not affect the result. For example, (Z/35Z)* = C_2 X C_12 = C_4 X C_6 = C_2 X C_2 X C_12, and we have phi(2)*phi(12) = phi(4)*phi(6) = phi(2)*phi(2)*phi(12) = 4 = a(35).

Examples

			Let (Z/nZ)* be the multiplicative group of integers modulo n.
(Z/63Z)* = C_6 X C_6, so a(63) = phi(6)*phi(6) = 4.
(Z/513Z)* = C_18 X C_18, so a(513) = phi(18)*phi(18) = 36.
(Z/840Z)* = C_2 X C_2 X C_2 X C_2 X C_12, so a(840) = phi(2)^4*phi(12) = 4.
		

Links

• Jianing Song, Table of n, a(n) for n = 1..10000
• Wikipedia, Multiplicative group of integers modulo n

Crossrefs

Cf. A000010, A327791.

Programs

PARI

a(n) = prod(i=1,#znstar(n)[2],eulerphi(znstar(n)[2][i]))