## Modulo Multiplication Group

A Finite Group of Residue Classes prime to under multiplication mod . is Abelian of Order , where is the Totient Function. The following table gives the modulo multiplication groups of small orders.

 Group Elements 1 1 2 1, 2 2 1, 3 4 1, 2, 3, 4 2 1, 5 6 1, 2, 3, 4, 5, 6 4 1, 3, 5, 7 6 1, 2, 4, 5, 7, 8 4 1, 3, 7, 9 10 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 4 1, 5, 7, 11 12 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 6 1, 3, 5, 9, 11, 13 8 1, 2, 4, 7, 8, 11, 13, 14 8 1, 3, 5, 7, 9, 11, 13, 15 16 1, 2, 3, ..., 16 6 1, 5, 7, 11, 13, 17 18 1, 2, 3, ..., 18 8 1, 3, 7, 9, 11, 13, 17, 19 12 1, 2, 4, 5, 7, 8, 10, 11, 13, 16, 17, 19 10 1, 3, 5, 7, 9, 13, 15, 17, 19, 21 22 1, 2, 3, ..., 22 8 1, 5, 7, 11, 13, 17, 19, 23

is a Cyclic Group (which occurs exactly when has a Primitive Root) Iff is of one of the forms , 4, , or , where is an Odd Prime and (Shanks 1993, p. 92).

Isomorphic modulo multiplication groups can be determined using a particular type of factorization of as described by Shanks (1993, pp. 92-93). To perform this factorization (denoted ), factor in the standard form

 (1)

Now write the factorization of the Totient Function involving each power of an Odd Prime
 (2)

as
 (3)

where
 (4)

denotes the explicit expansion of (i.e., ), and the last term is omitted if . If , write
 (5)

Now combine terms from the odd and even primes. For example, consider . The only odd prime factor is 13, so factoring gives . The rule for the powers of 2 gives . Combining these two gives . Other explicit values of are given below.

and are isomorphic Iff and are identical. More specifically, the abstract Group corresponding to a given can be determined explicitly in terms of a Direct Product of Cyclic Groups of the so-called Characteristic Factors, whose product is denoted . This representation is obtained from as the set of products of largest powers of each factor of . For example, for , the largest power of is and the largest power of 3 is , so the first characteristic factor is , leaving (i.e., only powers of two). The largest power remaining is , so the second Characteristic Factor is 2, leaving 2, which is the third and last Characteristic Factor. Therefore, , and the group is isomorphic to .

The following table summarizes the isomorphic modulo multiplication groups for the first few and identifies the corresponding abstract Group. No is Isomorphic to , , or . However, every finite Abelian Group is isomorphic to a Subgroup of for infinitely many different values of (Shanks 1993, p. 96). Cycle Graphs corresponding to for small are illustrated above, and more complicated Cycle Graphs are illustrated by Shanks (1993, pp. 87-92).

 Group Isomorphic , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,

The number of Characteristic Factors of for , 2, ... are 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, ... (Sloane's A046072). The number of Quadratic Residues in for are given by (Shanks 1993, p. 95). The first few for , 2, ... are 0, 1, 1, 1, 2, 1, 3, 1, 3, 2, 5, 1, 6, ... (Sloane's A046073).

In the table below, is the Totient Function (Sloane's A000010) factored into Characteristic Factors, is the Carmichael Function (Sloane's A011773), and are the smallest generators of the group (of which there is a number equal to the number of Characteristic Factors).

 3 2 2 2 27 18 18 2 4 2 2 3 28 6 13, 3 5 4 2 2 29 28 28 2 6 2 2 5 30 4 11, 7 7 6 6 3 31 30 30 3 8 2 7, 3 32 8 31, 3 9 6 6 2 33 10 10, 2 10 4 4 3 34 16 16 3 11 10 10 2 35 12 6, 2 12 2 5, 7 36 6 19,5 13 12 12 2 37 36 36 2 14 6 6 3 38 18 18 3 15 4 14, 2 39 12 38, 2 16 4 15, 3 40 4 39, 11, 3 17 16 16 3 41 40 40 6 18 6 6 5 42 6 13, 5 19 18 18 2 43 42 42 3 20 4 19, 3 44 10 43, 3 21 6 20, 2 45 12 44, 2 22 10 10 7 46 22 22 5 23 22 22 5 47 46 46 5 24 2 5, 7, 13 48 4 47, 7, 5 25 20 20 2 49 42 42 3 26 12 12 7 50 20 20 3

References

Riesel, H. The Structure of the Group .'' Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, pp. 270-272, 1994.

Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, pp. 61-62 and 92, 1993.

Sloane, N. J. A. Sequences A011773, A046072, A046073, and A000010/M0299 in An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html.

Weisstein, E. W. Groups.'' Mathematica notebook Groups.m.