

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 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 (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 nth 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

Jianing Song, Table of n, a(n) for n = 1..10000
Jianing Song, Some notes on the generating sets whose elements are multiplicatively independent (MISs)
Wikipedia, Multiplicative group of integers modulo n


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
If n is a term in A033948 (i.e., (Z/nZ)* is cyclic; rank((Z/nZ)*) = 0 or 1), then a(n) = phi(A033948(n)) = A000010(A033948(n)) = A046144(n).


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

(PARI) a(n) = A258615(n) * A316089(n) / (#znstar(n)[2])! \\ See A258615 and A316089 for their programs


CROSSREFS

Cf. A033948, A046072, A046144, A258615, A316089, A323021.
Sequence in context: A275435 A029267 A111725 * A324748 A320387 A304707
Adjacent sequences: A302254 A302255 A302256 * A302258 A302259 A302260


KEYWORD

nonn


AUTHOR

Jianing Song, Apr 04 2018


EXTENSIONS

Typo corrected by Jianing Song, Jun 30 2018
More terms from Jianing Song, Jul 03 2018


STATUS

approved



