cp's OEIS Frontend

The rank of a finitely generated group rank(G) is defined to be the size of the minimal generating sets of G.

Let p be an odd prime and (Z[i]/nZ[i])* be the multiplicative group of Gaussian integers modulo n, then: (Z[i]/p^e*Z[i])* = (C_((p-1)*p^(e-1)))^2 if p == 1 (mod 4); C_(p^(e-1)) X C_(p^(e-1)*(p^2-1)) if p == 3 (mod 4). (Z[i]/2Z[i])* = C_2, (Z[i]/2^e*Z[i])* = C_4 X C_(2^(e-2)) X C_(2^(e-1)) for e >= 2. If n = Product_{i=1..k} (p_i)^(e_i), then (Z[i]/nZ[i])* = (Z[i]/(p_1)^(e_1)*Z[i])* X (Z[i]/(p_2)^(e_2)*Z[i])* X ... X (Z[i]/(p_k)^(e_k)*Z[i])*.

The order of (Z[i]/nZ[i])* is A079458(n) and the exponent of it is A227334(n).

{a(n)} is not additive: (Z[i]/2Z[i])* = C_2, (Z[i]/9Z[i])* = C_3 X C_24, so (Z[i]/18Z[i])* = C_6 X C_24, a(18) < a(2) + a(9). The same problem occurs for a(36), a(54) and a(72) and so on. But note that (Z[i]/63Z[i])* = C_3 X C_24 X C_48 and a(63) = a(7) + a(9).

A079458(n)/A227334(n) is always an integer, and is 1 if and only if (Z[i]/nZ[i])* is cyclic, that is, rank((Z[i]/nZ[i])*) = a(n) = 0 or 1, and n has a primitive root in (Z[i]/nZ[i])*. a(n) = 1 if and only if n = 2 or a prime congruent to 3 mod 4. - Jianing Song, Jan 08 2019

From Jianing Song, Oct 03 2022: (Start)

More generally, let pi be a prime element of Z[i] of norm p or p^2 for prime p, then:

- for p == 1 (mod 4), (Z[i]/(pi^e)Z[i])* = C_((p-1)*p^(e-1));

- for p == 3 (mod 4), (Z[i]/(pi^e)Z[i])* = C_(p^(e-1)) X C_(p^(e-1)*(p^2-1));

- for p = 2, (Z[i]/(pi^e)Z[i])* = C_1 for e = 1, C_2 for e = 2, C_4 X C_(2^floor((e-3)/2)) X C_(2^ceiling((e-3)/2)) for e >= 3.

For a more general result see my link below. (End)

The rank of a finitely generated group rank(G) is defined to be the size of the minimal generating sets of G.

Let p be an odd prime and (Z[w]/nZ[w])* be the multiplicative group of Gaussian integers modulo n, then: (Z[w]/p^e*Z[w])* = (C_((p-1)*p^(e-1)))^2 if p == 1 (mod 6); C_(p^(e-1)) X C_(p^(e-1)*(p^2-1)) if p == 5 (mod 6); (Z[w]/3^e*Z[w])* = C_3 X C_(3^(e-1)) X C_(2*3^(e-1)); (Z[w]/2Z[w])* = C_3, (Z[w]/2^e*Z[w])* = C_2 X C_(2^(e-2)) X C_(3*2^(e-1)) for e >= 2. If n = Product_{i=1..k} (p_i)^(e_i), then (Z[w]/nZ[w])* = (Z[w]/(p_1)^(e_1)*Z[w])* X (Z[w]/(p_2)^(e_2)*Z[w])* X ... X (Z[w]/(p_k)^(e_k)*Z[w])*.

The order of (Z[w]/nZ[w])* is A319445(n) and the exponent of it is A319446(n).

{a(n)} is not additive: (Z[w]/2Z[w])* = C_3, (Z[w]/25Z[w])* = C_5 X C_120, so (Z[w]/50Z[w])* = C_15 X C_120, a(50) < a(2) + a(25).

A319445(n)/A319446(n) is always an integer, and is 1 if and only if (Z[w]/nZ[w])* is cyclic, that is, rank((Z[w]/nZ[w])*) = a(n) = 0 or 1, and n has a primitive root in (Z[w]/nZ[w])*. a(n) = 1 if and only if n = 3 or a prime congruent to 2 mod 3. - Jianing Song, Jan 08 2019

From Jianing Song, Oct 03 2022: (Start)

More generally, let pi be a prime element of Z[w] of norm p or p^2 for prime p, then:

- for p == 1 (mod 6), (Z[w]/(pi^e)Z[w])* = C_((p-1)*p^(e-1));

- for p == 5 (mod 6), (Z[w]/(pi^e)Z[w])* = C_(p^(e-1)) X C_(p^(e-1)*(p^2-1));

- for p = 3, (Z[w]/(pi^e)Z[w])* = C_2 for e = 1, C_3 X C_(3^floor((e-2)/2)) X C_(2*3^ceiling((e-2)/2)) for e >= 2;

- for p = 2, (Z[w]/(pi^e)Z[w])* = C_3 for e = 1, C_2 X C_(2^(e-2)) X C_(3*2^(e-1)) for e >= 2.

For a more general result see my link below. (End)

Here, "primorial(n)" is A002110(n) = Product_{k=1..n} prime(k).

For n >= 1, a(n) is the number of coprime squares modulo 4*primorial(n). Note that 4*primorial(n) = A102476(n+1) is the smallest k such that rank((Z/kZ)*) = n+1 for n >= 1. (The rank of a finitely generated group rank(G) is defined to be the size of the minimal generating sets of G. In particular, rank((Z/kZ)*) = 0 if k <= 2 and A046072(k) otherwise.) - Jianing Song, Oct 18 2021

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

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.

The rank of a finitely generated group rank(G) is defined to be the size of the minimal generating sets of G. In particular, rank((Z/kZ)*) = 0 if k <= 2 and A046072(k) otherwise.

The number of coprime squares modulo a(n) is given by A046073(a(n)) = A348420(n-2) for n >= 2.

a(n) is the least k such that the Sylow 2-subgroup of (Z/kZ)* is (C_2)^n. - Jianing Song, Aug 13 2023

a(n) is the number of coprime squares modulo A348418(n+2), where A348418(n) is the smallest k with rank((Z/kZ)*) = n such that there are an odd number of coprime squares modulo k. (The rank of a finitely generated group rank(G) is defined to be the size of the minimal generating sets of G. In particular, rank((Z/kZ)*) = 0 if k <= 2 and A046072(k) otherwise.)

Numbers k such that A046073(k) = A000010(k)/2^A034380(k).

An empirical observation, calculated for 2 <= k <= 10^5. The number of quadratic residues mod k coprime to k is |Q_k| = phi(k)/2^r, r = A046072(k) <= phi(k)/lambda(k). Up to 10^5, the equality holds for 37758 moduli, and the inequality holds for 62241.

Row lengths are A046072.

The products of the terms in each row are A000010.

First column is A002322.

Row 2^k is [2, 2^(k-2)] for k > 2. - Tom Edgar, May 31 2015

Row p^k (and row 2*p^k) is [(p-1)*p^(k-1)] for odd prime p. - Tom Edgar, May 31 2015

The number of distinct groups over numbers less than or equal to 10^k for k=1,2,3,4,5,6 is 5, 50, 447, 4060, 36655, 335714.

Arguably a(1)=3, as the multiplicative group mod 2 has only one element, hence its factorization is the empty product. - Joerg Arndt, May 18 2018

For n >= 2, positions of records of A046072. - Joerg Arndt, May 18 2018