cp's OEIS Frontend

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

If the map "G -> Automorphism group of G" eventually reaches the trivial group, then the initial group IS a cyclic group.

From Jianing Song, Oct 12 2019: (Start)

These are numbers k such that every step of the iteration results in a cyclic group, i.e., numbers k such that k, phi(k), phi(phi(k)), phi(phi(phi(k))), ... (or equivalently, k, A258615(k), A258615(A258615(k)), ...) are all in A033948, phi = A000010.

Number of iterations to reach the trivial group:

k = 1: 0;

k = 2: 1;

k = 4: 2;

k = 5, 10: 3;

k = 11, 22: 4;

k = 23, 46: 5;

k = 47, 94: 6;

k = 3^i, 2*3^i, i > 0: i+1;

k = 2*3^i+1, 2*(2*3^i+1), i > 0, 2*3^i+1 is prime: i+2. (End)

From Peter Schorn, Apr 06 2021: (Start)

Since the values of a(n) have a simple formula it is easy to confirm by direct calculation for all cases that A003434(a(n)) = A185816(a(n)), i.e., the number of iterations to reach 1 via the Euler phi function is the same as the number of iterations to reach 1 via the Carmichael lambda function.

A computer search up to n = 10^8 also confirms the conjecture that if A003434(n) = A185816(n) then n is a term of A117729.

(End)

Note that 24 is only number k such that the multiplicative group of integers modulo k is isomorphic to C_m X C_m X C_m, m > 1.

The number of elements in the multiplicative group of integers modulo a(n) of order d is A007434(d), whenever d is divisible by A002322(a(n)).

The corresponding m (=A002322(a(n))) are 2, 2, 6, 6, 18, 18, 42, 42, 100, 100, 156, 162, 156, 162, 486, 486, 1458, 2028, 1458, 2028, ... Each term in A114874, except for those of the form 2^k, k >= 2, occurs exactly twice in this list.

Numbers k such that A046072(k) = 2 and A316089(k) = 1. - Jianing Song, Sep 15 2018

Except for 8 and 12, these are numbers of the form p^e*((p-1)*p^(e-1) + 1) or 2*p^e*((p-1)*p^(e-1) + 1) where p is an odd prime and (p-1)*p^(e-1) + 1 is prime. - Jianing Song, Apr 13 2019