A323021 A way to generate a minimal generating set of (Z/nZ)* whose elements are multiplicatively independent for every n: row n lists the elements of S(n), where S(n) is defined in the comment section. Here (Z/nZ)* is the multiplicative group of integers modulo n.

2, 3, 2, 5, 3, 5, 7, 2, 7, 2, 5, 7, 2, 3, 7, 11, 5, 15, 3, 11, 2, 11, 17, 8, 10, 13, 5, 7, 13, 17, 2, 15, 2, 15, 17, 2, 7, 11, 3, 5, 31, 13, 23, 3, 22, 31, 19, 29, 2, 21, 14, 28, 17, 21, 31, 6, 29, 31, 3, 13, 23, 11, 37, 5, 5, 17, 31, 37, 3, 27, 35, 37, 27, 41

Offset: 3

Author

Jianing Song, Jan 11 2019

Keywords

• nonn
• tabf

Comments

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.

Examples

			Table begins
(1)  Empty set;
(2)  Empty set;
(3)  {2};
(4)  {3};
(5)  {2};
(6)  {5};
(7)  {3};
(8)  {5, 7};
(9)  {2};
(10) {7};
...
Example shows that S(560) = {241, 337, 351, 421}: (Start)
Since 560 = 16*5*7, we have S(560) = {1 <= x <= 560: x == 2 (mod 5) and x == 1 (mod 16*7), or x == 3 (mod 7) and x == 1 (mod 16*5), or x == 5 (mod 16) and x == 1 (mod 5*7), or x == 15 (mod 16) and x == 1 (mod 5*7)} = {241, 337, 351, 421}.
To find the index of a number, say, 403, with respect to the base (241, 337, 351, 421) modulo 560, suppose 241^a * 337^b * 351^c * 421^d == 403 (mod 560). Then we have:
- Modulo 16: 15^c * 5^d == 3 (mod 16) => c = 1, d = 3;
- Modulo 5: 2^b == 3 (mod 5) => b = 3;
- Modulo 7: 3^a == 4 (mod 7) => a = 4.
So the index of 403 with respect to the base (241, 337, 351, 421) modulo 560 is (4, 3, 1, 3). Note that the bases here are ordered. So the index of 403 with respect to the base (337, 241, 421, 351) modulo 560 is (3, 4, 3, 1). (End)
		

Links

• Jianing Song, Rows n = 3..1000
• Wikipedia, Multiplicative group of integers modulo n.

Crossrefs

Cf. A046072, A302257.

Programs

PARI

a(n) = my(v=vector(#znstar(n)[2]), f=factor(n)); if(n%2||n%8==4, for(i=1, #v, v[i]=lift(chinese(znprimroot(f[i,1]^f[i,2]), Mod(1, n/f[i,1]^f[i,2]))))); if(n%4==2, for(i=1, #v, v[i]=lift(chinese(znprimroot(f[i+1,1]^f[i+1,2]), Mod(1, n/f[i+1,1]^f[i+1,2]))))); if(n%8==0, v[1]=lift(chinese(Mod(5, 2^f[1,2]), Mod(1, n/2^f[1,2]))); v[2]=lift(chinese(Mod(-1, 2^f[1,2]), Mod(1, n/2^f[1,2]))); for(i=3, #v, v[i]=lift(chinese(znprimroot(f[i-1,1]^f[i-1,2]), Mod(1, n/f[i-1,1]^f[i-1,2]))))); v=vecsort(v); v

Extensions

Name simplified by Jianing Song, Mar 16 2019