cp's OEIS Frontend

Note that 24 is only number k such that the multiplicative group of integers modulo k is isomorphic to C_m X C_m X C_m, m > 1.

The number of elements in the multiplicative group of integers modulo a(n) of order d is A007434(d), whenever d is divisible by A002322(a(n)).

The corresponding m (=A002322(a(n))) are 2, 2, 6, 6, 18, 18, 42, 42, 100, 100, 156, 162, 156, 162, 486, 486, 1458, 2028, 1458, 2028, ... Each term in A114874, except for those of the form 2^k, k >= 2, occurs exactly twice in this list.

Numbers k such that A046072(k) = 2 and A316089(k) = 1. - Jianing Song, Sep 15 2018

Except for 8 and 12, these are numbers of the form p^e*((p-1)*p^(e-1) + 1) or 2*p^e*((p-1)*p^(e-1) + 1) where p is an odd prime and (p-1)*p^(e-1) + 1 is prime. - Jianing Song, Apr 13 2019

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

For any finite abelian multiplicative group G and a generating set (not necessarily minimal) S = {x_1, x_2, ..., x_m}, we say the elements in S are multiplicatively independent if Product_{i=1..m} (x_i)^(e_i) = o implies that (x_i)^(e_i) = o for i = 1..m", where o is the group identity. For example, let G = (Z/16Z)*, the elements in {3, 15} are multiplicatively independent, while the elements in {3, 5} are not because 3^2 * 5^2 == 1 (mod 16) but 3^2 == 5^2 == 9 (mod 16). - Jianing Song, Mar 16 2019

S(n) is defined as: S(p^e) = {the least primitive root modulo p^e} if p is an odd prime; S(2) = the empty set, S(4) = {3}, S(2^e) = {5, 2^e - 1} for e >= 3. If gcd(m_1, m_2) = 1, then S((m_1)*(m_2)) = {1 <= x <= (m_1)*(m_2) : x belongs to S(m_1) and x == 1 (mod m_2), or x belongs to S(m_2) and x == 1 (mod x_1)}. The reason we choose S(2^e) = {5, 2^e - 1} is that for n >= 3, 1, 5, 5^2, ..., 5^(2^(e-2)-1) are all elements in (Z/(2^e)Z)* that are congruent to 1 modulo 4 and their additive inverses are all elements that are congruent to 3 modulo 4.

Offset 3, because the generating set of (Z/1Z)* or (Z/2Z)* is the empty set. The length of the n-th row is A046072(n) for n >= 3.

We now show that S(n) is a generating set of (Z/nZ)* whose elements are multiplicatively independent by induction. According to A302257, we only need to show that for every n, S(n) = {x_1, x_2, ..., x_r} satisfies that a one-to-one mapping can be set between all products of the form Product_{i=1..r} (x_i)^(e_i) and the elements in (Z/nZ)*, where 0 <= e_i < ord(x_i,n) for 1 <= i <= r. Suppose gcd(m_1, m_2) = 1. Let S(m_1) = {x_1, x_2, ..., x_s}, S(m_2) = {y_1, y_2, ..., y_t}, then S((m_1)*(m_2)) = {x'1, x'_2, ..., x'_s, y'_1, y'_2, ..., y'_t} where x'_i == x_i (mod m_1), x'_i == 1 (mod m_2), y'_i == 1 (mod m_1), y'_i == y_i (mod m_2). For every a coprime to n, solving a == Product{i=1..s} (x'i)^(e_i) * Product{i=1..t} (y'i)^(f_i) (mod (m_1)*(m_2)) is equivalent to solving a == Product{i=1..s} (x'i)^(e_i) (mod m_1) and a == Product{i=1..s} (y'i)^(f_i) (mod m_2) separately, which are immediately reduced to a == Product{i=1..s} (x_i)^(e_i) (mod m_1) and a == Product_{i=1..s} (y_i)^(f_i) (mod m_2). Since the elements in S(m_1) are multiplicatively independent, the elements in S(m_2) are multiplicatively independent as well, hence the elements in S((m_1)*(m_2)) must also be multiplicatively independent. For example, S(5) = {2}, S(7) = {3}, so S(35) = {22, 31}. For every a coprime to 35, solving a == 22^e * 31^f (mod 35) is equivalent to solving a == 2^e * 1^f (mod 35) and a == 1^e * 3^f (mod 7) separately, which are immediately reduced to a == 2^e (mod 5) and a == 3^f (mod 7). See A302257 for more information. [Revised by Jianing Song, Mar 16 2019]

Also, S(n) can be used to show that if gcd(m_1, m_2) = 1, then every Dirichlet character modulo (m_1)*(m_2) can be written as the product of a character modulo m_1 and a character modulo m_2. Define S(m_1), S(m_2) and S((m_1)*(m_2)) as above. Let {Chi(n, k)} be a Dirichlet character modulo n. {Chi((m_1)*(m_2), k)} is wholly determined by Chi((m_1)*(m_2), x'_1), Chi((m_1)*(m_2), x'_2), ..., Chi((m_1)*(m_2), x'_r), Chi((m_1)*(m_2), y'_1), Chi((m_1)*(m_2), y'_2), ..., Chi((m_1)*(m_2), y'_s). We have Chi(m_1, t)*Chi(m_2, t) = Chi((m_1)*(m_2), t) for every t belongs to S((m_1)*(m_2)). These equations then reduce to Chi(m_1, x_i) = Chi((m_1)*(m_2), x'_i) and Chi(m_2, y_i) = Chi((m_1)*(m_2), y'_i), so {Chi(m_1, k)} and {Chi(m_2, k)} are determined. It's easy to see that the product of a character modulo m_1 and a character modulo m_2 is a character modulo (m_1)*(m_2), so all characters modulo (m_1)*(m_2) can be constructed using the characters modulo m_1 and the characters modulo m_2.

In general, let G be a finite abelian group and r = rank(G), let s be the number of arrays (k_1, k_2, ..., k_r) such that G = C_(k_1) X C_(k_2) X ... X C_(k_r). We can see from A302257 that:

(a) Given (k'1, k'_2, ..., k'_r) such that G = C(k'1) X C(k'2) X ... X C(k'_r), the number of arrays (a_1, a_2, ..., a_r) such that G = X X ... and that ord(a_i) = k'_i is |Aut(G)|, where is the subgroup of G generated by a. This is because if one group of such (a_1, a_2, ..., a_r) is found, all the others can be found by group automorphism. As a result, the number of sets {a_1, a_2, ..., a_r} such that G = X X ... is |Aut(G)|*s/r!. As (k'_1, k'_2, ..., k'_r) runs through all the s possible choices, each array (a_1, a_2, ..., a_r) such that G = X X ... occurs exactly once, giving a total of |Aut(G)|*s arrays. But the elements in a set are unordered, so the number of sets is |Aut(G)|*s/r!;