|
| |
|
|
A302257
|
|
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. Here (Z/nZ)* is the multiplicative group of integers modulo n.
|
|
5
|
|
|
|
1, 1, 1, 1, 2, 1, 2, 3, 2, 2, 4, 3, 4, 2, 8, 8, 8, 2, 6, 8, 12, 4, 10, 28, 8, 4, 6, 12, 12, 8, 8, 16, 24, 8, 32, 12, 12, 6, 32, 96, 16, 12, 12, 24, 32, 10, 22, 96, 12, 8, 32, 32, 24, 6, 64, 168, 36, 12, 28, 96, 16, 8, 144, 32, 192, 24, 20, 32, 60, 32, 24, 168, 24, 12, 64, 36, 96, 32
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,5
|
|
|
COMMENTS
|
Originally named "Decompose the multiplicative group of integers modulo n as a product of cyclic groups C_{k_1} X C_{k_2} X ... X C_{k_m}, where k_i divides k_j for i < j, then a(n) is the number of generating sets {x_k_i} where x_k_i generates C_{k_i}", which is incorrect for n = 35, 39, 45, 52, 55, ...
A minimal generating set of a finitely generated group G is defined as a generating set of G with the least elements. For n >= 3, the number of elements in the minimal generating sets of (Z/nZ)* (denoted by rank((Z/nZ)*)) is given in A046072. The multiplicative group of integers modulo 1 or 2 is the trivial group (has rank 0). The minimal generating set of it is the empty set, which also meets the condition by the convention empty product is 1. - Jianing Song, Jun 27 2018
Equivalently, number of sets {x_1, x_2, ..., x_r} (r = rank((Z/nZ)*)) such 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 (so a necessary condition is that (Z/nZ)* = C_{ord(x_1,n)} X C_{ord(x_2,n)} X ... X C_{ord(x_r,n)}). Here ord(x,n) is the multiplicative order of x modulo n. Such sets are generalizations of primitive roots modulo n (for r = 1). For an element g in (Z/nZ)*, the corresponding e_1, e_2, ..., e_r can be seen as index of g under a given such set {x_1, x_2, ..., x_r} modulo n. For example, for n = 16 and a given such set {3, 15}, we have: 1 == 3^0 * 15^0 (mod 16), 3 == 3^1 * 15^0 (mod 16), 5 == 3^3 * 15^1 (mod 16), 7 == 3^2 * 15^1 (mod 16), 9 == 3^2 * 15^0 (mod 16), 11 == 3^3 * 15^0 (mod 16), 13 == 3^1 * 15^1 (mod 16), 15 == 3^0 * 15^1 (mod 16).
For any finite abelian multiplicative group G and a generating set (not necessarily minimal) S = {x_1, x_2, ..., x_m}, the property "Product_{i=1..m} (x_i)^(e_i) = o implies that (x_i)^(e_i) = o for i = 1..m" (o is the group identity) can be stated as "the elements in S are multiplicatively independent". If G is viewed as an additive group, then the corresponding property is "Sum_{i=1..m} (e_i)*(x_i) = o implies that (e_i)*(x_i) = o for i = 1..m", which can be stated as "the elements in S are linearly independent". For convenience, if the elements in S are multiplicatively independent, we call S a MIS. The link below lists some more general results for MISs. They concern only on finite abelian multiplicative groups but they also have their versions on additive groups. - Jianing Song, Mar 16 2019
Let S = {x_1, x_2, ..., x_r} be a minimal generating set of (Z/nZ)*, then S is a MIS iff all Dirichlet characters modulo n are generated when Chi(x_1), Chi(x_2), ..., Chi(x_r) run through their all possible values. If so, for an element g in (Z/nZ)*, g == Product_{i=1..r} (x_i)^(e_i) (mod n), we have Chi(g) = Product_{i=1..r} Chi(x_i)^(e_i). For example, if we choose {3, 15} as a minimal generating set of (Z/16Z)*, then all 8 Dirichlet characters modulo 16 are generated when Chi(3) runs through {1, -1, i, -i} and Chi(15) runs through {1, -1}. On the other hand, if S is not a MIS, it implies that some values for Chi(x_1), Chi(x_2), ..., Chi(x_r) cannot be taken. Since (x_i)^(e_i) == 1 (mod n) doesn't imply that (x_i)^(e_i) == 1 (mod n) for 1 <= i <= r, suppose that (x_1)^(e_1) !== 1 (mod n), letting Chi(x_1) = exp(2*Pi*i/ord(x_1,n)) and Chi(x_2) = Chi(x_3) = ... = Chi(x_r) = 1 results in 1 = Chi(1) = Product_{i=1..r} Chi(x_i)^(e_i) = Chi(x_1)^(e_1) = exp(2e_1*Pi*i/ord(x_1,n)) != 1, a contradiction. - Jianing Song, Jun 27 2018 [Revised by Jianing Song, Mar 16 2019]
The elements in one MIS that is minimal of (Z/nZ)* is given in the n-th row of A323021. All other such sets can be obtained using group isomorphisms and automorphisms. See Theorem 3 in the link. - Jianing Song, Mar 16 2019
|
|
|
LINKS
|
|
|
|
FORMULA
|
For a given n, let r = rank((Z/nZ)*) (= A046072(n) for n >= 3), then a(n) = A258615(n)*A316089(n)/r!. See these two sequences for explicit formulae. - Jianing Song, Jun 27 2018
|
|
|
EXAMPLE
|
For n = 16, we're looking for generating sets {x_1, x_2} such that (x_1)^(e_1) * (x_2)^(e_2) == 1 (mod 16) implies (x_1)^(e_1) == (x_2)^(e_2) == 1 (mod 16). Since (Z/16Z)* = C_2 X C_4, we can suppose that ord(x_1,16) = 4 and ord(x_2,16) = 2, which gives a total of 8 sets: {3, 7}, {5, 7}, {11, 7}, {13, 7}, {3, 15}, {5, 15}, {11, 15} and {13, 15}, so a(16) = 8. Note that {3, 5} is not what we want because 3^2 * 5^2 == 1 (mod 16) but 3^2 == 5^2 == 9 (mod 16).
For n = 35, we're looking for generating sets {x_1, x_2} such that (x_1)^(e_1) * (x_2)^(e_2) == 1 (mod 35) implies (x_1)^(e_1) == (x_2)^(e_2) == 1 (mod 35). Since (Z/35Z)* = C_2 X C_12 = C_4 X C_6, we can suppose that ord(x_1,35) = 12 and ord(x_2,35) = 2 (for example {2, 6}), or ord(x_1,35) = 6 and ord(x_2,35) = 4 (for example {19, 8}), which gives a total of 32 sets, so a(35) = 32.
|
|
|
PROG
|
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
