cp's OEIS Frontend

Numbers n such that A046072(n) = 6.

Numbers n such that A046072(n) = 7.

Numbers n such that A046072(n) = 8.

Numbers n such that A046072(n) = 9.

After a(2), this matches A034380 except for n = 63, 65, 80, 85, ... - R. J. Mathar, Feb 27 2009 [Updated by Andrey Zabolotskiy, May 09 2018]

The length of row n is given by A046072(A033949(n)), n >= 1.

The generators are chosen minimally in the sense that the product of their orders (cycle lengths) is phi(N(n)) = A000010(N(n)) with N(n) = A033949(n). In addition, the generators are sorted with nonincreasing orders, and the smallest numbers with these orders are listed.

Note that the first instance where a composite generator is needed is N = 51 = A033949(20) with a generator 35. The next such number is N = 69 = A033949(31) with a generator 68. Such numbers N will be called exceptional.

For a table with n = 1..69, N = 8, 12, ..., 130, see the W. Lang link. Compare this with the Wikipedia table (where some generator errors will be corrected). There non-minimal generators are also used, i.e., the product of the orders of the generators is larger than phi(N). The Wikipedia table often uses composite generators when primes would do the job. E.g., N = 16 with generators 2, 14 instead of 2, 11; or N = 16 with 3, 15 instead of 3, 7, etc.

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

See A281854.

Compare this with A046072(A033949(n)). In A046072 the decompositions used are not total, e.g., n = 6 with A033949(6) = 1 uses C_6, but C_6 = C_2 x C_3. Or, 21 = A033949(6), A046072(21) = 2 not 3 = a(6).

The multiplicative group of integers modulo n, (Z/n*Z)^x, also the cyclotomic group, the Galois group Gal(Q(zeta(n))/Q) with zeta(n) = exp(2*Pi*I/n), is cyclic for n from A033948 and non-cyclic for n from A033949. Each of these groups is the direct product of cyclic factors (one factor is included).

In the total factorization for n >= 3 only cyclic factors whose orders are prime powers appear, and because the direct product is associative, and for these abelian groups also commutative, one can order the factors with nonincreasing orders.

For n=1 and n=2 the group is C_1 = {1} (for n=1 one has 1 == 0 (mod 1)).

Cyclic groups may also have a factorization into more than one factor. E.g., C_6 = C_3 x C_2.

The number of factors in this total factorization is for a cyclic group C_m, for m >= 2, given by A001221(m). For m=1 this number is 1 (not A001221(1)).

For non-cyclic groups the number of factors in this total factorization is given by A281855(m) if n = A033949(m), m >= 1.

For the non-cyclic group case see also the W. Lang links under A281854.

Compare this sequence with A046072 where another factorization of these groups is used, the one with the least cyclic factors. E.g., A046072(7) = 1 for the group C_6, and a(7) = 2 here (see the example above).