Modular arithmetic groups and cyclic groups

The simplest groups are those generated by a single element: start with one element, take all its powers and their inverses, and see what you get. These are the cyclic groups. Every one of them is either the integers or a group of integers modulo \(n\), so this lesson starts with modular arithmetic. Along the way we meet the group \(U(n)\) of units modulo \(n\), which is the setting for Fermat's little theorem and RSA, and the notion of the order of an element, which runs through the rest of the course.

The integers modulo n

Fix a positive integer \(n\). Two integers \(a\) and \(b\) are congruent modulo \(n\), written \(a \equiv b \pmod n\), if \(n\) divides \(a - b\). Congruence is an equivalence relation, and MATH-228 showed that its classes partition \(\mathbb{Z}\) into \(n\) classes, one for each remainder \(0, 1, \dots, n - 1\). We write \(\mathbb{Z}_n\) for the set of these classes, usually naming each class by its smallest nonnegative member.

Congruence respects addition: if \(a \equiv a'\) and \(b \equiv b'\), then \(a + b \equiv a' + b'\), because \((a + b) - (a' + b') = (a - a') + (b - b')\) is a sum of multiples of \(n\). So addition of classes is well defined: to add two classes, add any representatives and take the class of the result. The group axioms for \(\mathbb{Z}_n\) under addition are inherited from \(\mathbb{Z}\). The identity is 0, the inverse of \(a\) is \(n - a\) for \(a \ne 0\), and the group is abelian of order \(n\). This is clock arithmetic: on a 12-hour clock, 5 hours after 9 o'clock is 2 o'clock, because \(9 + 5 = 14 \equiv 2 \pmod{12}\).

The phrase well defined deserves attention, because it will return in lesson 9 when we build quotient groups. An operation on classes is defined by choosing representatives, and the definition only makes sense if every choice gives the same answer. Multiplication is also well defined on \(\mathbb{Z}_n\), but \(\mathbb{Z}_n\) under multiplication is not a group, because 0 has no inverse, and neither do other elements when \(n\) is composite.

The units modulo n

Which classes do have multiplicative inverses modulo \(n\)? An integer \(a\) has an inverse modulo \(n\) exactly when \(\gcd(a, n) = 1\). If \(\gcd(a, n) = 1\), Bézout's identity gives integers \(x, y\) with \(ax + ny = 1\), so \(ax \equiv 1 \pmod n\) and \(x\) is an inverse. Conversely, if \(ax \equiv 1\), then \(ax - 1 = ny\) for some \(y\), so any common divisor of \(a\) and \(n\) divides 1.

Let \(U(n)\) be the set of classes in \(\mathbb{Z}_n\) coprime to \(n\). It is a group under multiplication modulo \(n\). Closure holds because a product of numbers coprime to \(n\) is coprime to \(n\); associativity is inherited from \(\mathbb{Z}\); the identity is 1; and inverses exist by the argument above. The order of \(U(n)\) is Euler's totient \(\varphi(n)\), the number of integers in \(1, \dots, n\) coprime to \(n\). For a prime \(p\), \(U(p) = \{1, 2, \dots, p - 1\}\) has order \(p - 1\).

The order of an element

Let \(a\) be an element of a group \(G\). The order of \(a\), written \(|a|\) or \(\operatorname{ord}(a)\), is the smallest positive integer \(n\) with \(a^n = e\), if such an \(n\) exists; otherwise \(a\) has infinite order. In additive notation the condition is \(na = 0\). The identity is the only element of order 1. In \(\mathbb{Z}_{12}\) the element 4 has order 3, since \(4 + 4 + 4 = 12 \equiv 0\), and 5 has order 12. In \(\mathbb{Z}\) every nonzero element has infinite order. In \(D_4\) the quarter turn has order 4 and every reflection has order 2.

Theorem. Suppose \(a\) has finite order \(n\). Then \(a^k = e\) if and only if \(n\) divides \(k\), and the powers \(e, a, a^2, \dots, a^{n-1}\) are all different. Proof: divide \(k\) by \(n\) to get \(k = qn + r\) with \(0 \le r < n\). Then \(a^k = (a^n)^q a^r = a^r\). If \(a^k = e\) then \(a^r = e\) with \(r < n\), so \(r = 0\) by the minimality of \(n\), and \(n \mid k\). The converse is clear. If \(a^i = a^j\) with \(0 \le i < j < n\), then \(a^{j - i} = e\) with \(0 < j - i < n\), a contradiction.

So the powers of \(a\) cycle with period exactly \(n\): \(a^k\) depends only on \(k\) modulo \(n\). If \(a\) has infinite order, all powers \(a^k\) for \(k \in \mathbb{Z}\) are different, by the same argument.

Cyclic groups

For an element \(a\) of a group \(G\), the set of all its powers \(\langle a \rangle = \{a^k : k \in \mathbb{Z}\}\) is a group under the same operation, the cyclic subgroup generated by \(a\). By the theorem, \(\langle a \rangle\) has exactly \(|a|\) elements when \(a\) has finite order. A group \(G\) is cyclic if \(G = \langle a \rangle\) for some \(a\), called a generator. Every cyclic group is abelian, because \(a^i a^j = a^{i+j} = a^j a^i\).

Examples: \(\mathbb{Z}\) is cyclic, generated by 1 or by \(-1\). \(\mathbb{Z}_n\) is cyclic, generated by 1. \(U(10)\) is cyclic, generated by 3. The rotations of a regular \(n\)-gon form a cyclic group of order \(n\) generated by the rotation through \(360^\circ/n\). The Klein four-group is not cyclic, because each of its elements has order at most 2. \(U(8) = \{1, 3, 5, 7\}\) is not cyclic either: \(3^2 = 9 \equiv 1\), \(5^2 = 25 \equiv 1\) and \(7^2 = 49 \equiv 1\) modulo 8.

Generators of a cyclic group

A cyclic group usually has several generators. In \(\mathbb{Z}_{12}\), the element 5 generates everything: its multiples are \(5, 10, 3, 8, 1, 6, 11, 4, 9, 2, 7, 0\). The element 4 generates only \(\{0, 4, 8\}\). The difference is that \(\gcd(5, 12) = 1\) while \(\gcd(4, 12) = 4\).

Theorem. Let \(G = \langle a \rangle\) be cyclic of order \(n\). For any integer \(k\), the element \(a^k\) has order \(n / \gcd(n, k)\). In particular \(a^k\) generates \(G\) if and only if \(\gcd(n, k) = 1\), and \(G\) has exactly \(\varphi(n)\) generators.

Proof: let \(d = \gcd(n, k)\). By the earlier theorem, \((a^k)^m = a^{km} = e\) exactly when \(n \mid km\). Write \(n = dn'\) and \(k = dk'\) with \(\gcd(n', k') = 1\). Then \(n \mid km\) means \(dn' \mid dk'm\), that is \(n' \mid k'm\), and because \(n'\) and \(k'\) are coprime this means \(n' \mid m\). So the smallest positive such \(m\) is \(n' = n/d\). The element \(a^k\) generates \(G\) exactly when its order is \(n\), that is when \(d = 1\).

For example, the generators of \(\mathbb{Z}_{12}\) are 1, 5, 7 and 11, matching \(\varphi(12) = 4\), and the element 8 has order \(12/\gcd(12, 8) = 3\).

Subgroups of cyclic groups

Theorem. Every subgroup of a cyclic group is cyclic. If \(G = \langle a \rangle\) has order \(n\), then for each positive divisor \(d\) of \(n\) there is exactly one subgroup of order \(d\), namely \(\langle a^{n/d} \rangle\), and there are no other subgroups.

Proof of the first statement: let \(H\) be a subgroup of \(G = \langle a \rangle\) (lesson 6 defines subgroups formally: a subset that is a group under the same operation). If \(H = \{e\}\) it is cyclic. Otherwise \(H\) contains some \(a^k\) with \(k \ne 0\), and since it contains inverses it contains a positive power of \(a\). Let \(m\) be the smallest positive integer with \(a^m \in H\). We claim \(H = \langle a^m \rangle\). Certainly \(\langle a^m \rangle \subseteq H\). Conversely, if \(a^k \in H\), divide: \(k = qm + r\) with \(0 \le r < m\). Then \(a^r = a^k (a^m)^{-q} \in H\), so \(r = 0\) by minimality of \(m\), and \(a^k = (a^m)^q \in \langle a^m \rangle\).

For the count, the previous theorem shows that \(\langle a^{n/d} \rangle\) has order \(d\). If \(H\) is any subgroup of order \(d\), it is \(\langle a^m \rangle\) for the least positive \(m\) with \(a^m \in H\); since \(a^n = e \in H\), the same division argument shows \(m \mid n\), and \(H\) has order \(n/m\). So \(n/m = d\), \(m = n/d\), and \(H = \langle a^{n/d} \rangle\). The subgroups of \(\mathbb{Z}_{12}\) are therefore generated by 1, 2, 3, 4, 6 and 12, one for each divisor of 12.

Products of cyclic groups

When is \(\mathbb{Z}_m \times \mathbb{Z}_n\) cyclic? The element \((1, 1)\) has order equal to the least \(k\) with \(m \mid k\) and \(n \mid k\), which is \(\operatorname{lcm}(m, n)\). If \(\gcd(m, n) = 1\) then \(\operatorname{lcm}(m, n) = mn\), so \((1, 1)\) generates the whole group and \(\mathbb{Z}_m \times \mathbb{Z}_n\) is cyclic of order \(mn\). If \(\gcd(m, n) = d > 1\), every element \((x, y)\) satisfies \(\ell(x, y) = (0, 0)\) with \(\ell = \operatorname{lcm}(m, n) = mn/d < mn\), so no element has order \(mn\) and the group is not cyclic. Thus \(\mathbb{Z}_2 \times \mathbb{Z}_3\) is cyclic of order 6, while \(\mathbb{Z}_2 \times \mathbb{Z}_2\) is the Klein four-group. This is the group-theoretic form of the Chinese remainder theorem, which MATH-351 Number Theory studies in detail.

The groups \(U(n)\) are more subtle. Gauss proved in his Disquisitiones Arithmeticae of 1801 that \(U(n)\) is cyclic exactly when \(n\) is 1, 2, 4, \(p^k\) or \(2p^k\) for an odd prime \(p\). A generator of \(U(n)\) is called a primitive root modulo \(n\). The code below computes element orders in \(\mathbb{Z}_{12}\) and in several groups \(U(n)\), and tests which \(U(n)\) are cyclic.

from math import gcd

def order_add(k, n):
    """order of k in Z_n under addition"""
    m, x = 1, k % n
    while x != 0:
        x = (x + k) % n
        m += 1
    return m

def order_mul(a, n):
    """order of a in U(n) under multiplication"""
    m, x = 1, a % n
    while x != 1:
        x = x * a % n
        m += 1
    return m

print("orders in Z_12:", {k: order_add(k, 12) for k in range(1, 12)})
print("generators of Z_12:", [k for k in range(12) if order_add(k, 12) == 12])
print("check n/gcd(n,k):", all(order_add(k, 12) == 12 // gcd(12, k) for k in range(1, 12)))

for n in [7, 8, 9, 10, 12, 15, 18]:
    U = [a for a in range(1, n) if gcd(a, n) == 1]
    orders = {a: order_mul(a, n) for a in U}
    gens = [a for a in U if orders[a] == len(U)]
    status = f"cyclic, generators {gens}" if gens else "not cyclic"
    print(f"U({n}) has order {len(U)}: orders {orders} -> {status}")

orders in Z_12: {1: 12, 2: 6, 3: 4, 4: 3, 5: 12, 6: 2, 7: 12, 8: 3, 9: 4, 10: 6, 11: 12}
generators of Z_12: [1, 5, 7, 11]
check n/gcd(n,k): True
U(7) has order 6: orders {1: 1, 2: 3, 3: 6, 4: 3, 5: 6, 6: 2} -> cyclic, generators [3, 5]
U(8) has order 4: orders {1: 1, 3: 2, 5: 2, 7: 2} -> not cyclic
U(9) has order 6: orders {1: 1, 2: 6, 4: 3, 5: 6, 7: 3, 8: 2} -> cyclic, generators [2, 5]
U(10) has order 4: orders {1: 1, 3: 4, 7: 4, 9: 2} -> cyclic, generators [3, 7]
U(12) has order 4: orders {1: 1, 5: 2, 7: 2, 11: 2} -> not cyclic
U(15) has order 8: orders {1: 1, 2: 4, 4: 2, 7: 4, 8: 4, 11: 2, 13: 4, 14: 2} -> not cyclic
U(18) has order 6: orders {1: 1, 5: 6, 7: 3, 11: 6, 13: 3, 17: 2} -> cyclic, generators [5, 11]

The output confirms the theorems: the orders in \(\mathbb{Z}_{12}\) are all divisors of 12 given by \(12/\gcd(12, k)\); \(U(7)\), \(U(9)\), \(U(10)\) and \(U(18)\) are cyclic, while \(U(8)\), \(U(12)\) and \(U(15)\) are not, in line with Gauss's theorem.

Fermat and Euler revisited

Lesson 7 proves Lagrange's theorem: the order of an element of a finite group divides the order of the group. Applied to \(U(n)\), whose order is \(\varphi(n)\), it gives \(a^{\varphi(n)} \equiv 1 \pmod n\) whenever \(\gcd(a, n) = 1\). This is Euler's theorem, and the special case \(a^{p-1} \equiv 1 \pmod p\) for a prime \(p\) is Fermat's little theorem. MATH-260 proved these by counting; here they become consequences of a single structural fact about groups. The same fact underlies RSA encryption, which works in the group \(U(pq)\) for two large primes.