A327790 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,5

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

LINKS

Jianing Song, Table of n, a(n) for n = 1..10000

Wikipedia, Multiplicative group of integers modulo n

EXAMPLE

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.

PROG

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

CROSSREFS

Cf. A000010, A327791.