|
%I #134 May 26 2021 02:19:20
%S 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,
%T 16,24,8,32,12,12,6,32,96,16,12,12,24,32,10,22,96,12,8,32,32,24,6,64,
%U 168,36,12,28,96,16,8,144,32,192,24,20,32,60,32,24,168,24,12,64,36,96,32
%N 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.
%C 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, ...
%C 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
%C 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).
%C 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
%C 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]
%C 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
%H Jianing Song, <a href="/A302257/b302257.txt">Table of n, a(n) for n = 1..10000</a>
%H Jianing Song, <a href="/A302257/a302257.txt">Some notes on the generating sets whose elements are multiplicatively independent (MISs)</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n">Multiplicative group of integers modulo n</a>
%F 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
%F 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).
%e 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).
%e 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.
%o (PARI) a(n) = A258615(n) * A316089(n) / (#znstar(n)[2])! \\ See A258615 and A316089 for their programs
%Y Cf. A033948, A046072, A046144, A258615, A316089, A323021.
%K nonn
%O 1,5
%A _Jianing Song_, Apr 04 2018
%E Typo corrected by _Jianing Song_, Jun 30 2018
%E More terms from _Jianing Song_, Jul 03 2018
|
