A316089 Number of ordered (k_1, k_2, ..., k_r) such that (Z/nZ)* is isomorphic to C_{k_1} X C_{k_2} X ... X C_{k_r}. Here (Z/nZ)* is the multiplicative group of integers modulo n, r = rank((Z/nZ)*).

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

Offset: 1

Author

Jianing Song, Jun 27 2018

Keywords

• nonn

Comments

The rank of a finitely generated group rank(G) is defined as the size of the minimal generating sets (the generating sets with the least elements) of G. By convention a(1) = a(2) = 1, since the multiplicative group of integers modulo 1 or 2 has rank 0, and the empty direct product yields the trivial group.

This sequence is related to the number of minimal generating sets {x_1, x_2, ..., x_r} of (Z/nZ)* such that Product_{i=1..r} x_i^e_i == 1 (mod n) implies that x_i^e_i == 1 (mod n) for 1 <= i <= r. See A302257.

For n >= 3, also the number of ordered (k_1, k_2, ..., k_r) such that (Z/nZ)* is isomorphic to C_{k_1} X C_{k_2} X ... X C_{k_r} and gcd(k_1, k_2, ..., k_r) > 1.

a(n) = 1 iff there exists an integer m such that (Z/nZ)* = (C_m)^r, that is, n is a term in A033948 or A305236 or n = 24.

First occurrence of k, or -1 if k never occurs: 1, 15, 40, 35, -1, 160, -1, 143, 104, -1, -1, 480, -1, -1, -1, ... It's easy to show that prime number >= 5 never occurs.

In general, let (Z/nZ)* = C_(Product_{j=1..k} p_j^e_1j) X C_(Product_{j=1..k} p_j^e_2j) X ... X C_(Product_{j=1..k} p_j^e_rj) where p_1, p_2, ..., p_k are different primes, 0 <= e_1j <= e_2j <= ... <= e_rj for 1 <= j <= k (for n = 1 or 2, (Z/nZ)* is the trivial group, thus r = k = 0), then a(n) is the number of matrices C = (c_ij) such that (c_1j, c_2j, ..., c_rj) is a permutation of (e_1j, e_2j, ..., e_rj) for 1 <= j <= k. - Jianing Song, Feb 04 2019

Examples

			For n = 35, rank((Z/35Z)*) = 2, and (Z/35Z)* = C_2 X C_12 = C_12 X C_2 = C_4 X C_6 = C_6 X C_4, so a(35) = 4. Also, (Z/35Z)* = C_(2^1*3^0) X C_(2^2*3^1), e_11 = 1, e_12 = 0, e_21 = 2, e_22 = 1, so b_11 = b_12 = b_21 = b_22 = 1, then a(35) = (2!)^2 = 4.
For n = 105, rank((Z/105Z)*) = 3, and (Z/105Z)* = C_2 X C_2 X C_12 (along with its two permutations) = C_2 X C_4 X C_6 (along with its five permutations), so a(105) = 9. Also, (Z/35Z)* = C_(2^1*3^0) X C_(2^1*3^0) X C_(2^2*3^1), e_11 = 1, e_12 = 0, e_21 = 1, e_22 = 0, e_31 = 2, e_32 = 1, so b_11 = b_12 = b_21 = b_22 = 2, b_31 = b_32 = 1, then a(105) = (3!)^2/(2!*2!) = 9.
		

Links

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

Crossrefs

Cf. A033948, A302257, A305236.

Programs

PARI

zp(g)={sum(i=1, #g, my(f=factor(g[i])); sum(j=1, #f~, x^f[j,1]*(y^f[j,2]-1)))}
a(n)={my(g=znstar(n).cyc); my(p=zp(g), r=#g); prod(i=1, poldegree(p), my(u=Vec(r + polcoeff(p,i))); r!/prod(j=1, #u, u[j]!))} \\ Andrew Howroyd, Jun 30 2018

Formula

Let (Z/nZ)* = C_(Product_{j=1..k} p_j^e_1j) X C_(Product_{j=1..k} p_j^e_2j) X ... X C_(Product_{j=1..k} p_j^e_rj) where p_1, p_2, ..., p_k are different primes, 0 <= e_1j <= e_2j <= ... <= e_rj for 1 <= j <= k. Define b_ij = max{1 <= t <= r | e_tj = e_ij} - min{1 <= t <= r | e_tj = e_ij} + 1, then a(n) = (r!)^k/Product_{i=1..r, j=1..k} (b_ij)!^(1/b_ij).