

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



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

3,1


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^(e2)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 nth 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 onetoone 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) seperately, 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) seperately, 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 equation 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.


LINKS

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


EXAMPLE

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)


PROG

(PARI) a(n) = my(v=vector(#znstar(n)[2]), f=factor(n)); if(n%2n%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[i1, 1]^f[i1, 2]), Mod(1, n/f[i1, 1]^f[i1, 2]))))); v=vecsort(v); v


CROSSREFS

Cf. A046072, A302257.
Sequence in context: A255709 A285512 A232928 * A026235 A086281 A097975
Adjacent sequences: A323018 A323019 A323020 * A323022 A323023 A323024


KEYWORD

nonn,tabf


AUTHOR

Jianing Song, Jan 11 2019


EXTENSIONS

Name simplified by Jianing Song, Mar 16 2019


STATUS

approved



