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
Keywords
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
Programs
-
PARI
a(n) = prod(i=1,#znstar(n)[2],eulerphi(znstar(n)[2][i]))
Comments