Modulo Multiplication Group

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

A modulo multiplication group can be visualized by constructing its group cycle graph. Group 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 , 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 iff , 2, 4, , or , where is an odd prime and (Shanks 1993, p. 92). For , this occurs exactly when has a primitive root. The first few moduli are 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, ... (OEIS A033948; Shanks 1993, p. 84).

The only moduli for which every element of equals its own inverse 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 of the displayed prime powers, retaining each factor separately. 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 with modulus . 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 have the same multiset of prime-power factors. 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). Group cycle graphs corresponding to for small are illustrated above, and more complicated group cycle graphs are illustrated by Shanks (1993, pp. 87-92).

The following table gives the moduli 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), using one factor of order 1 for the trivial group.

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 A002322), and are chosen generators of the group (of which there is a number equal to the number of characteristic factors).