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.

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

Offset: 1

Author

Jianing Song, Apr 04 2018

Keywords

• nonn

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

Examples

			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.
		

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

Crossrefs

Cf. A033948, A046072, A046144, A258615, A316089, A323021.

Programs

PARI

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

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).

Extensions

Typo corrected by Jianing Song, Jun 30 2018

More terms from Jianing Song, Jul 03 2018