A327790 - OEIS

%I #11 Mar 09 2021 02:55:16

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

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

%U 4,8,8,4,20,8,10,4,24,2,24,12,8,6,8,4,24,4,18,16,40,2,16,12

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

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

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

%H Jianing Song, <a href="/A327790/b327790.txt">Table of n, a(n) for n = 1..10000</a>

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

%e Let (Z/nZ)* be the multiplicative group of integers modulo n.

%e (Z/63Z)* = C_6 X C_6, so a(63) = phi(6)*phi(6) = 4.

%e (Z/513Z)* = C_18 X C_18, so a(513) = phi(18)*phi(18) = 36.

%e (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.

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

%Y Cf. A000010, A327791.

%K nonn

%O 1,5

%A _Jianing Song_, Sep 25 2019