cp's OEIS Frontend

The multiplicative group modulo n can be written as the direct product of a(n) (but not fewer) cyclic groups. - Joerg Arndt, Dec 25 2014

a(n) = 1 (that is, the multiplicative group modulo n is cyclic) iff n is in A033948, or equivalently iff A034380(n)=1. - Max Alekseyev, Jan 07 2015

This sequence gives the minimal number of generators of the multiplicative group of integers modulo n which is isomorphic to the Galois group Gal(Q(zeta_n)/Q), with zeta_n =exp(2*Pi*I/n). See, e.g., Theorem 9.1.11., p. 235 of the Cox reference. See also the table of the Wikipedia link. - Wolfdieter Lang, Feb 28 2017

In this factorization the trivial group C_1 = {1} is allowed as a factor only for n = 0 and 1 (otherwise one could have arbitrarily many leading C_1 factors for n >= 3). - Wolfdieter Lang, Mar 07 2017

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.

The length of row n is given in A281855.

The multiplicative group of integers modulo n is written as (Z/(n Z))^x (in ring notation, group of units) isomorphic to Gal(Q(zeta(n))/Q) with zeta(n) = exp(2*Pi*I/n). The present table gives in row n the factors of the direct product decomposition of the non-cyclic group of integers modulo A033949(n) (in nonincreasing order). The cyclic group of order n is C_n. Note that only C-factors of prime power orders are used; for example C_6 has the decomposition C_3 x C_2, etc. C_n is decomposed whenever n has relatively prime factors like in C_30 = C_15 x C_2 = C_5 x C_3 x C_2. In the Wikipedia table partial decompositions appear.

The row products phi(A033949(n)) are given as 4*A281856(n), n >= 1, with phi(n) = A000010(n).

See also the W. Lang links for these groups.

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