A282625 -id:A282625 - cp's OEIS frontend

A046072 Decompose 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) = m.

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 1, 2, 2, 1, 1, 3, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 3, 1, 2, 1, 2, 2, 1, 1, 3, 1, 1, 2, 2, 1, 1, 2, 3, 2, 1, 1, 3, 1, 1, 2, 2, 2, 2, 1, 2, 2, 2, 1, 3, 1, 1, 2, 2, 2, 2, 1, 3, 1, 1, 1, 3, 2, 1, 2, 3, 1, 2, 2, 2, 2, 1, 2, 3, 1, 1, 2, 2, 1, 2

Offset: 1

Eric W. Weisstein

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

David A. Cox, Galois Theory, John Wiley & Sons, Hoboken, New Jrsey, 2004, 235.
Daniel Shanks, Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, pp. 92-93, 1993.

Joerg Arndt, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Modulo Multiplication Group.
Wikipedia, Multiplicative group of integers modulo n. See the table at the end.

Cf. A001221, A046073 (number of squares in multiplicative group modulo n), A077761, A281855, A282625 (for total factorization).

a(n)=k iff n is in: A033948 (k=1), A272592 (k=2), A272593 (k=3), A272594 (k=4), A272595 (k=5), A272596 (k=6), A272597 (k=7), A272598 (k=8), A272599 (k=9).

f[n_] := Which[OddQ[n], PrimeNu[n], EvenQ[n] && ! IntegerQ[n/4],
  PrimeNu[n] - 1, IntegerQ[n/4] && ! IntegerQ[n/8], PrimeNu[n],
  IntegerQ[n/8], PrimeNu[n] + 1]; Join[{1, 1},
Table[f[n], {n, 3, 102}]] (* Geoffrey Critzer, Dec 24 2014 *)

a(n)=if(n<=2, 1, #znstar(n)[3]); \\ Joerg Arndt, Aug 26 2014

a(n) = A001221(n) - 1 if n > 2 is divisible by 2 and not by 4, a(n) = A001221(n) + 1 if n is divisible by 8, a(n) = A001221(n) in other cases. - Ivan Neretin, Aug 01 2016

Sum_{k=1..n} a(k) = n * (log(log(n)) + B - 1/8) + O(n/log(n)), where B is Mertens's constant (A077761). - Amiram Eldar, Sep 21 2024

A282624 Irregular triangle read by rows: row n gives a certain choice of generators of the multiplicative group of integers modulo A033949(n).

Original entry on oeis.org

3, 5, 5, 7, 2, 11, 3, 7, 3, 11, 2, 13, 5, 7, 13, 3, 13, 7, 11, 3, 31, 2, 23, 19, 13, 5, 19, 17, 5, 3, 11, 29, 5, 13, 3, 43, 11, 17, 5, 7, 17, 5, 35, 3, 5, 19, 23, 3, 13, 29, 2, 37, 7, 11, 19, 2, 5, 3, 31, 2, 31, 5, 43, 3, 67, 2, 68, 19, 13, 5, 17, 19, 11, 7

Offset: 1

Wolfdieter Lang, Mar 03 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 irregular triangle T(n, k) begins (here N = A033949(n), and the respective primitive cycle lengths and phi(N) are also given)
n,   N \k 1   2   3 ... cycle lengths, phi(N)
1,   8:   3   5           2  2          4
2,  12:   5   7           2  2          4
3,  15:   2  11           4  2          8
4,  16:   3   7           4  2          8
5,  20:   3  11           4  2          8
6,  21:   2  13           6  2         12
7,  24:   5   7  13       2  2  2       8
8,  28:   3  13           6  2         12
9,  30:   7  11           4  2          8
10, 32:   3  31           8  2         16
11, 33:   2  23          10  2         20
12, 35:  19  13           6  4         24
13, 36:   5  19           6  2         12
14, 39:  17   5           6  4         24
15, 40:   3  11  29       4  2  2      16
16: 42:   5  13           6  2         12
17, 44:   3  43          10  2         20
18, 45:  11  17           6  4         24
19, 48:   5   7  17       4  2  2      16
20, 51:   5  35          16  2         32
... See the link for more.

Wolfdieter Lang, Table for the multiplicative non-cyclic groups of integers modulo A033949.
Eldar Sultanow, Christian Koch, and Sean Cox, Collatz Sequences in the Light of Graph Theory, Universität Potsdam (Germany, 2020).

Cf. A033949, A046072, A279399, A281855, A281856, A282623, A282625.

A281855 Number of cyclic group factors in the total decomposition of the abelian non-cyclic group (Z/A033949(n) Z)^x. Row lengths of A281854.

Original entry on oeis.org

2, 2, 2, 2, 2, 3, 3, 3, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 3, 3, 4, 3, 3, 4, 2, 3, 3, 2, 3, 3, 4, 3, 3, 4, 3, 3, 4, 2, 3, 4, 3, 4, 3, 4, 3, 3, 4, 3, 2, 4, 4, 3, 3, 3, 4, 3, 3, 3, 4, 3, 4, 3, 4, 4, 4, 2, 4, 3

Offset: 1

Wolfdieter Lang, Mar 03 2017

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

Cf. A033949, A046072, A281854, A282623, A282624, A282625.

A380827 Least integer k such that the multiplicative group modulo n is a subgroup of the symmetric group S_k.

Original entry on oeis.org

1, 1, 2, 2, 4, 2, 5, 4, 5, 4, 7, 4, 7, 5, 6, 6, 16, 5, 11, 6, 7, 7, 13, 6, 9, 7, 11, 7, 11, 6, 10, 10, 9, 16, 9, 7, 13, 11, 9, 8, 13, 7, 12, 9, 9, 13, 25, 8, 12, 9, 18, 9, 17, 11, 11, 9, 13, 11, 31, 8, 12, 10, 10, 18, 11, 9, 16, 18, 15, 9, 14, 9, 17, 13, 11, 13, 12, 9, 18, 10, 29

Offset: 1

Asher Gray, Feb 04 2025

nonn

Asher Gray, Table of n, a(n) for n = 1..10000
Wikipedia, Multiplicative group of integers modulo n

Cf. A008475, A380222, A282625.

a(j*k) = a(j) + a(k) where j and k are coprime and both greater than 2.
a(2j) = j where j is odd.
a(2) = 1, a(4) = 2, a(2^k) = 2 + 2^(k-2) for k >= 3.
a(p^k) = A008475(p-1) * p^(k-1) for odd prime p.

cp's OEIS Frontend

A046072 Decompose 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) = m.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A282624 Irregular triangle read by rows: row n gives a certain choice of generators of the multiplicative group of integers modulo A033949(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A281855 Number of cyclic group factors in the total decomposition of the abelian non-cyclic group (Z/A033949(n) Z)^x. Row lengths of A281854.

Views

Author

Keywords

Comments

Crossrefs

A380827 Least integer k such that the multiplicative group modulo n is a subgroup of the symmetric group S_k.

Views

Author

Keywords

Links

Crossrefs

Formula