Modulo Multiplication Group

A modulo multiplication group is a finite group of residue classes prime to under multiplication mod . is Abelian of group order , where is the totient function.

A modulo multiplication group can be visualized by constructing its cycle graph. Cycle graphs are illustrated above for some low-order modulo multiplication groups. Such graphs are constructed by drawing labeled nodes, one for each element of the residue class, and connecting cycles obtained by iterating . Each edge of such a graph is bidirected, but they are commonly drawn using undirected edges with double edges used to indicate cycles of length two (Shanks 1993, pp. 85 and 87-92).

The following table gives the modulo multiplication groups of small orders, together with their isomorphisms with respect to cyclic groups .

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). The first few of these are , 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, ... (OEIS A033948; Shanks 1993, p. 84).

The only ordered for which the elements of are all self-conjugate are the divisors of 24: 1, 2, 3, 4, 6, 8, 12, 24 (OEIS A018253; Eggar 2000). These correspond to the groups , , , and . This also means that no modulo multiplication group is isomorphic to a direct product of more than three copies of .

Isomorphic modulo multiplication groups can be determined using a particular type of factorization of the totient function using the property that

as described by Shanks (1993, pp. 92-93). To perform this factorization, begin by analogy with computation of the totient function by factoring in the standard form

Now for each power of an odd prime, write

and factor the leading term

as

where denotes the explicit expansion of (i.e., ), and the last term is omitted if (since in that case, ).

If contains a power of 2 so that , then write

Now combine terms from the odd and even primes, write them as a product and combine any unambiguous products of terms. The resulting expression is denoted and the group is isomorphic to a direct product of cyclic groups of orders given by .

For example, consider the modulo multiplication group of order . The only odd prime factor is 13, so factoring gives . 104 contains a factor of , so the rule for even prime factors gives . Combining these two gives .

and are isomorphic iff and are identical. More specifically, the abstract group corresponding to a given can be determined explicitly in terms of a group 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 2 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 the cyclic group , quaternion group , or the dihedral group . 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).

The following table gives the orders of modulo multiplication groups that are isomorphic to direct products of cyclic groups for .

The number of characteristic factors of for , 2, ... are 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, ... (OEIS 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, ... (OEIS A046073).

In the table below, is the totient function (OEIS A000010) factored into characteristic factors, is the Carmichael function (OEIS A011773), and are the smallest generators of the group (of which there is a number equal to the number of characteristic factors).