Modulo Multiplication Group

A modulo multiplication group is a finite group M_m of residue classes prime to m under multiplication mod m. M_m is Abelian of group order phi(m), where phi(m) 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 A of the residue class, and connecting cycles obtained by iterating A^n. 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 C_n.

M_m is a cyclic group (which occurs exactly when m has a primitive root) iff m is of one of the forms m=2, 4, p^n, or 2p^n, where p is an odd prime and n>=1 (Shanks 1993, p. 92). The first few of these are m=3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, ... (OEIS A033948; Shanks 1993, p. 84).

The only ordered m for which the elements of M_m 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 <e>, C_2, C_2×C_2, and C_2×C_2×C_2. This also means that no modulo multiplication group is isomorphic to a direct product of more than three copies of C_2.

Isomorphic modulo multiplication groups can be determined using a particular type of factorization of the totient function phi(m) 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 m in the standard form

Now for each power of an odd prime, write

and factor the leading term

as

where <q^b> denotes the explicit expansion of q^b (i.e., 5^2=25), and the last term is omitted if a_i=1 (since in that case, <p_i^(a_i-1)>=1).

If m contains a power of 2 so that p_1=2, 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 phi_m and the group M_m is isomorphic to a direct product of cyclic groups of orders given by phi_m.

For example, consider the modulo multiplication group of order m=104=2^3·13. The only odd prime factor is 13, so factoring gives 13-1=12=<2^2><3>=3·4. 104 contains a factor of 2^3, so the rule for even prime factors gives <2><2^(3-2)>=<2><2>=2·2. Combining these two gives phi_(104)=2·2·3·4.

M_m and M_n are isomorphic iff phi_m and phi_n are identical. More specifically, the abstract group corresponding to a given M_m can be determined explicitly in terms of a group direct product of cyclic groups of the so-called characteristic factors, whose product is denoted Phi_n. This representation is obtained from phi_m as the set of products of largest powers of each factor of phi_m. For example, for phi_(104), the largest power of 2 is 4=2^2 and the largest power of 3 is 3=3^1, so the first characteristic factor is 4×3=12, leaving 2·2 (i.e., only powers of two). The largest power remaining is 2=2^1, so the second characteristic factor is 2, leaving 2, which is the third and last characteristic factor. Therefore, Phi_(104)=2·2·12, and the group M_m is isomorphic to C_2×C_2×C_(12).

The following table summarizes the isomorphic modulo multiplication groups M_n for the first few n and identifies the corresponding abstract group. No M_m is isomorphic to the cyclic group C_8, quaternion group Q_8, or the dihedral group D_4. However, every finite Abelian group is isomorphic to a subgroup of M_m for infinitely many different values of m (Shanks 1993, p. 96). Cycle graphs corresponding to M_n for small n 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 M_m that are isomorphic to direct products of cyclic groups for m<=50.

The number of characteristic factors r of M_m for m=1, 2, ... are 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, ... (OEIS A046072).

The number of quadratic residues in M_m for m>2 are given by phi(m)/2^r (Shanks 1993, p. 95). The first few for m=1, 2, ... are 0, 1, 1, 1, 2, 1, 3, 1, 3, 2, 5, 1, 6, ... (OEIS A046073).

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

See also

Explore with Wolfram|Alpha

References

Referenced on Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Modulo Multiplication Group." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ModuloMultiplicationGroup.html

Subject classifications