Integers mod n, symmetries and matrices as groups
The integers mod n, the motions that carry a rectangle onto itself, and the invertible matrices look like unrelated objects. In what sense is each of them a group, and which axiom takes real work in each case?
Where you are 6 in Groups
Why this exists
The facts proved in Binary operations and the group axioms pay off only if many objects satisfy the group axioms. Three sources supply most of the groups in this course: arithmetic modulo n, the motions that carry a figure onto itself, and invertible matrices. In each, one axiom takes the work: for \mathbb{Z}_n that the operation is well defined, for multiplication mod n that inverses exist, for symmetries that an inverse is again a symmetry, and for matrices that a product of invertible matrices is invertible.
Definition
Throughout, n is a positive integer. Writing k for the class [k]_n, as in Relations, equivalence classes and partitions, \mathbb{Z}_n = \{0, 1, \dots, n - 1\} with [a] + [b] = [a + b] and [a][b] = [ab], both well defined by Theorem 8 there (the arithmetic of Congruence modulo n and its arithmetic).
The integers mod n. The group (\mathbb{Z}_n, +) is \mathbb{Z}_n under addition.
The units mod n. A class [a] is a unit if [a][b] = [1] for some [b] \in \mathbb{Z}_n. The units form \mathbb{Z}_n^\times, with multiplication as the operation (some texts, Judson’s among them, write U(n)). Euler’s function \varphi(n) counts the k with 1 \le k \le n and \gcd(k, n) = 1 (Fermat's little theorem).
Symmetries. Write d(P, Q) for the distance between points of the plane. An isometry is a map f : \mathbb{R}^2 \to \mathbb{R}^2 with d(f(P), f(Q)) = d(P, Q) for all P, Q (a rigid motion, Rigid motions defined precisely, and what they preserve). A symmetry of a set F of points (a figure) is a bijective isometry f with f(F) = F. The symmetries of F under composition form \mathcal{S}(F). (We avoid \operatorname{Sym}(F), which means all bijections of the set F.)
Matrix groups. The general linear group \operatorname{GL}_n(\mathbb{R}) is the set of n \times n real matrices with nonzero determinant, and the special linear group \operatorname{SL}_n(\mathbb{R}) the set of those with determinant 1, under matrix multiplication (Matrix multiplication). For a prime p, \operatorname{GL}_2(\mathbb{Z}_p) is the set of 2 \times 2 matrices with entries in \mathbb{Z}_p and ad - bc \ne 0 in \mathbb{Z}_p, under matrix multiplication with arithmetic in \mathbb{Z}_p.
Intuition
When the elements are maps, associativity is free, since composition of maps is associative. Symmetries are maps of the plane and a matrix is a linear map (Linear transformation), so in both families the work is in closure and inverses. In \mathbb{Z}_n, associativity is inherited from \mathbb{Z} one class at a time.
Results
Theorem 1 (integers mod n). (\mathbb{Z}_n, +) is an abelian group of order n with identity 0, and the inverse of [a] is [-a] = [n - a].
Theorem 2 (units mod n). Multiplication on \mathbb{Z}_n is associative and commutative, has identity [1], and distributes over addition. A class [a] is a unit if and only if \gcd(a, n) = 1, a condition that does not depend on the representative a. And \mathbb{Z}_n^\times is an abelian group of order \varphi(n).
Corollary 3 (prime modulus). For n \ge 2, the nonzero classes \mathbb{Z}_n \setminus \{0\} form a group under multiplication if and only if n is prime.
Theorem 4 (symmetry groups). For every figure F, (\mathcal{S}(F), \circ) is a group.
Lemma 5 (three points fix an isometry). An isometry that fixes three points not on one line fixes every point. So two symmetries of F that agree at three such points are equal.
Theorem 6 (real matrix groups). \operatorname{GL}_n(\mathbb{R}) and \operatorname{SL}_n(\mathbb{R}) are groups under matrix multiplication with identity I_n; for n \ge 2 neither is abelian.
Theorem 7 (matrices over \mathbb{Z}_p). For a prime p, \operatorname{GL}_2(\mathbb{Z}_p) is a group of order (p^2 - 1)(p^2 - p). The inverse of A = \begin{pmatrix} a & b \\ c & d \end{pmatrix} is \delta^{-1}\begin{pmatrix} d & -b \\ -c & a \end{pmatrix}, where \delta = ad - bc.
Why it is true
Proof of Theorem 1. Addition is well defined (Relations, equivalence classes and partitions, Theorem 8), and associative and commutative by Exercise 20 there. [0] + [a] = [a] and [a] + [-a] = [0], with [-a] = [n - a] since n \mid (n - a) - (-a). The classes [0], \dots, [n - 1] are distinct and are all of \mathbb{Z}_n (Theorem 7 there). \square
Proof of Theorem 2. As for addition, ([a][b])[c] = [(ab)c] = [a(bc)] = [a]([b][c]) and [a][b] = [ab] = [ba] = [b][a], by the same laws in \mathbb{Z}; likewise [1][a] = [a] and [a]([b] + [c]) = [ab + ac] = [a][b] + [a][c]. If a' = a + qn, the common divisors of a and n are those of a' and n, so \gcd(a', n) = \gcd(a, n). By Modular inverses and linear congruences (Theorem 1), ab \equiv 1 \pmod{n} has a solution b exactly when \gcd(a, n) = 1. As multiplication is associative with an identity, the elements with an inverse form a group (Binary operations and the group axioms, Exercise 14), and they are the distinct classes of the k with 1 \le k \le n and \gcd(k, n) = 1. \square
Proof of Corollary 3. If n = p is prime, \gcd(k, p) = 1 for 1 \le k \le p - 1, so \mathbb{Z}_p \setminus \{0\} = \mathbb{Z}_p^\times. If n = rs with 1 < r, s < n, then [r] and [s] are nonzero but [r][s] = [0], so the nonzero classes are not closed. \square
Proof of Theorem 4. Let f, g \in \mathcal{S}(F). Then g \circ f is a bijection (Composing functions between sets, and when an inverse exists), keeps distances, as f and g do, and (g \circ f)(F) = g(F) = F. Composition is associative, and \mathrm{id} is an identity. The inverse map f^{-1} is a bijection. It keeps distances: put P = f(P_0) and Q = f(Q_0); then d(f^{-1}(P), f^{-1}(Q)) = d(P_0, Q_0) = d(P, Q). Applying f^{-1} to f(F) = F gives F = f^{-1}(F). \square
Proof of Lemma 5. Let the isometry f fix A, B, C, not on one line, and let Q = f(P). Then d(Q, A) = d(f(P), f(A)) = d(P, A), and likewise for B and C. If Q \ne P, the points equally far from P and Q form a line, the perpendicular bisector of PQ, and it would contain A, B, C. So f(P) = P. If f, g \in \mathcal{S}(F) agree at A, B, C, then g^{-1} \circ f fixes them, so g^{-1} \circ f = \mathrm{id} and f = g. \square
Proof of Theorem 6. Matrix multiplication is associative with identity I_n. By the product rule \det(AB) = \det A \det B (Properties of determinants: row operations, products, transposes, Theorem 4), both sets are closed. A matrix with \det A \ne 0 has an inverse (The invertible matrix theorem), and \det A \det A^{-1} = \det I_n = 1 gives \det A^{-1} = 1/\det A, nonzero, and 1 when \det A = 1. For n \ge 2, let X be I_n with entry (1, 2) changed to 1, and Y be I_n with entry (2, 1) changed to 1. Both are triangular with 1s on the diagonal, so lie in \operatorname{SL}_n(\mathbb{R}), and the (1, 1) entry of XY is 2 but that of YX is 1. \square
Proof of Theorem 7. By Theorems 1 and 2, arithmetic in \mathbb{Z}_p obeys the associative, commutative and distributive laws, which are all that the expansions proving (AB)C = A(BC) and \det(AB) = \det A \det B for 2 \times 2 matrices use. A product of nonzero classes mod p is nonzero (Modular inverses and linear congruences, Corollary 4), so the set is closed, with identity I_2. If \delta \ne 0, it has an inverse in \mathbb{Z}_p (Corollary 3), and multiplying out, A times the stated matrix is \delta^{-1}\delta I_2 = I_2, in either order; its determinant \delta^{-2}(da - bc) = \delta^{-1} is nonzero.
For the order, write u = (a, c) and v = (b, d) for the columns. We claim \delta \ne 0 exactly when u \ne 0 and v is not a multiple tu with t \in \mathbb{Z}_p. If u = 0, or v = tu, then \delta = 0. Conversely, let u \ne 0 and \delta = 0. If a \ne 0, put t = a^{-1}b: then b = ta, and ad = bc gives d = a^{-1}bc = tc. If a = 0, then c \ne 0; put t = c^{-1}d, so d = tc, and -bc = 0 gives b = 0 = ta. There are p^2 - 1 choices of u \ne 0, and its multiples are p distinct vectors, since (t - t')u = 0 forces t = t' by canceling a nonzero entry of u. That leaves p^2 - p choices of v. \square
Worked examples
The units mod 10
Write the table of \mathbb{Z}_{10}^\times and find each inverse; compare the inverse of 9 with its inverse in (\mathbb{Z}_{10}, +). Solve 3x = 7 in \mathbb{Z}_{10}^\times and 3 + x = 7 in \mathbb{Z}_{10}.
SolutionThe numbers from 1 to 10 prime to 10 are 1, 3, 7, 9, so \mathbb{Z}_{10}^\times = \{1, 3, 7, 9\} (Theorem 2), of order \varphi(10) = 4. Reducing each product mod 10:
| \cdot | 1 | 3 | 7 | 9 |
|---|---|---|---|---|
| 1 | 1 | 3 | 7 | 9 |
| 3 | 3 | 9 | 1 | 7 |
| 7 | 7 | 1 | 9 | 3 |
| 9 | 9 | 7 | 3 | 1 |
The 1s give 1^{-1} = 1, 3^{-1} = 7, 7^{-1} = 3 and 9^{-1} = 9. In (\mathbb{Z}_{10}, +) the inverse of 9 is -9 = 1: one class, two operations, two different inverses.
By Theorem 4 of Binary operations and the group axioms, 3x = 7 has exactly one solution, x = 3^{-1} \cdot 7 = 49, that is, x = 9; check: 3 \cdot 9 = 27 \equiv 7. In \mathbb{Z}_{10}, x = -3 + 7, so x = 4.
This is not the table of the Klein four-group V_4 of Binary operations and the group axioms, where every element is its own inverse: here 3 \cdot 3 = 9. Instead the powers 3, 9, 7, 1 of 3 run through the whole group.
A group with identity 6
Show that H = \{2, 4, 6, 8\} \subseteq \mathbb{Z}_{10} is a group under multiplication, although none of its elements is a unit of \mathbb{Z}_{10}.
SolutionThe products, reduced mod 10:
| \cdot | 2 | 4 | 6 | 8 |
|---|---|---|---|---|
| 2 | 4 | 8 | 2 | 6 |
| 4 | 8 | 6 | 4 | 2 |
| 6 | 2 | 4 | 6 | 8 |
| 8 | 6 | 2 | 8 | 4 |
Every entry lies in H, and multiplication is associative and commutative on all of \mathbb{Z}_{10} (Theorem 2), so on H. The row of 6 copies the headings, so 6 is the identity. Reading the 6s, 2 \cdot 8 = 16 \equiv 6 and 4 \cdot 4 \equiv 6, so 2^{-1} = 8, 4^{-1} = 4 and 6^{-1} = 6. So H is a group of order 4.
Its identity is 6, not 1; with respect to 1, 2 has no inverse, as \gcd(2, 10) = 2. The powers 2, 4, 8, 16 \equiv 6 of 2 run through H as those of 3 run through \mathbb{Z}_{10}^\times, so renaming 2^k as 3^k turns one table into the other, a first hint of Isomorphisms.
The symmetries of a rectangle
Let R be the filled rectangle with corners A = (-p, -q), B = (p, -q), C = (p, q) and D = (-p, q), where p > q > 0. Prove that \mathcal{S}(R) has exactly four elements, and find its table.
Four symmetries. Let h(x, y) = (-x, -y), the half turn about O; m_1(x, y) = (x, -y), the reflection in \ell_1; m_2(x, y) = (-x, y), the reflection in \ell_2; and e = \mathrm{id}. Each only changes signs of coordinates, so it keeps distances, is its own inverse, and maps R (where |x| \le p and |y| \le q) onto itself. Their values at C are C, A, B, D, so they are distinct.
No others. Call a point of R a corner if it is not the midpoint of two distinct points of R. A point with |x| < p is the midpoint of (x \pm \varepsilon, y) for small \varepsilon > 0, and one with |y| < q likewise. But x_1 + x_2 = 2p with x_1, x_2 \le p forces x_1 = x_2 = p, and the same for y, so C is a corner, as are A, B, D. Now M is the midpoint of P and Q exactly when \displaystyle d(P, M) = d(M, Q) = \frac{1}{2}d(P, Q) (equality in the triangle inequality), so isometries keep midpoints. If f \in \mathcal{S}(R) sent a corner to the midpoint of distinct P', Q' \in R, then f^{-1} \in \mathcal{S}(R) would make that corner the midpoint of f^{-1}(P') and f^{-1}(Q'). So f permutes the corners.
From each corner, exactly one corner lies at distance 2p, one at 2q and one at \displaystyle 2\sqrt{p^2 + q^2}, three different numbers. So once f(A) is chosen (four ways), f(B) must be the corner at distance 2p from it and f(D) the one at distance 2q. As A, B, D are not on one line, Lemma 5 leaves at most four symmetries: \mathcal{S}(R) = \{e, h, m_1, m_2\}.
The table. (m_1 \circ m_2)(x, y) = m_1(-x, y) = (-x, -y), so m_1 \circ m_2 = h. In the same way the composite of any two of h, m_1, m_2 is the third, and each composed with itself is e:
| \circ | e | h | m_1 | m_2 |
|---|---|---|---|---|
| e | e | h | m_1 | m_2 |
| h | h | e | m_2 | m_1 |
| m_1 | m_1 | m_2 | e | h |
| m_2 | m_2 | m_1 | h | e |
This is the table of V_4 in Binary operations and the group axioms, with a, b, c renamed h, m_1, m_2. For a square (p = q) the count breaks at 2p = 2q, and there are eight symmetries (Dihedral groups).
Turning a mattress
At a mattress shop, Amara tells customers to turn a mattress every season. Place it as the box |x| \le p, |y| \le q, |z| \le s with p > q > s > 0. Three turns put it back on the frame: spinning it flat (a half turn about the z-axis), flipping it end over end (about the y-axis) and flipping it side over side (about the x-axis). Show that these turns and staying put form a group of order 4. A customer alternates spinning and flipping end over end, starting with a spin. Where is the mattress after 7 seasons?
SolutionA half turn about a coordinate axis keeps that coordinate and negates the other two, so the turns are the diagonal matrices S = \operatorname{diag}(-1, -1, 1), E = \operatorname{diag}(-1, 1, -1) and F = \operatorname{diag}(1, -1, -1), each of determinant 1 and mapping the box onto itself. Diagonal matrices multiply entry by entry, so each turn squares to I_3 and the product of two different turns is the third: ES = SE = F, SF = FS = E and EF = FE = S. So T = \{I_3, S, E, F\} is closed, contains I_3 and each element’s inverse (the element itself), and matrix multiplication is associative: T is a group of order 4, with the rectangle’s table (S, E, F for h, m_1, m_2).
As T is abelian, the position after 7 seasons depends only on how many of each turn were made: 4 spins and 3 flips, and S^4E^3 = I_3 E = E. The mattress lies as after one flip end over end. The first four seasons give S, ES = F, SF = E, E^2 = I_3: each position once a year.
The group \operatorname{GL}_2(\mathbb{Z}_2)
List the elements of \operatorname{GL}_2(\mathbb{Z}_2) and show that it is not abelian. With X = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} and Y = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}, find the smallest k \ge 1 with (XY)^k = I_2.
SolutionBy Theorem 7 the order is (4 - 1)(4 - 2) = 6. As in its proof, the first column is one of the nonzero vectors (1, 0), (0, 1), (1, 1), and the second is either nonzero vector other than the first (over \mathbb{Z}_2 the multiples of u are 0 and u). The six elements are
With arithmetic mod 2,
so XY \ne YX. Next, (XY)^2 = \begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix}, which is YX mod 2, not I_2, and
So k = 3, while X^2 = Y^2 = I_2. The symmetries of an equilateral triangle also form a non-abelian group of order 6, with three reflections and two rotations, through one third and two thirds of a full turn; the two tables agree after renaming, a fact for Isomorphisms.
Boundaries
- Multiplication on all of \mathbb{Z}_n is not a group for n \ge 2: 0 \cdot x = 0 \ne 1. Deleting 0 helps only for a prime modulus (Corollary 3); in general the units are the right set.
- “Onto” matters. For the ray F = \{(x, 0) : x \ge 0\}, the shift f(x, y) = (x + 1, y) is a bijective isometry with f(F) \subseteq F, but f^{-1} sends (0, 0) outside F.
- Over \mathbb{Z}_n with n composite, a nonzero determinant is not enough. In \mathbb{Z}_4 the matrix \begin{pmatrix} 2 & 0 \\ 0 & 1 \end{pmatrix} has determinant 2 but no inverse: \det(AA') = 2\det A' is 0 or 2, never 1. The determinant must be a unit.
Where this goes next
\operatorname{SL}_n(\mathbb{R}) inside \operatorname{GL}_n(\mathbb{R}) and the mattress turns inside \operatorname{SL}_3(\mathbb{R}) are Subgroups. \mathbb{Z}_n and \mathbb{Z}_{10}^\times are built from one element, the subject of Cyclic groups. Regular polygons give Dihedral groups, and bijections of a finite set give Permutation groups and cycle notation. With Lagrange's theorem, |\mathbb{Z}_n^\times| = \varphi(n) reproves Euler’s theorem from Fermat's little theorem. Two operations at once, as on \mathbb{Z}_n, make a ring (Rings and integral domains).
Exercises
Integers mod n
- In \mathbb{Z}_{15}, find the inverses of 4 and 7 under addition. In \mathbb{Z}_{15}^\times, find the inverses of 4 and 7.
- List \mathbb{Z}_9^\times and the inverse of each element.
- Solve 5 + x = 3 in \mathbb{Z}_{14} and 5x = 3 in \mathbb{Z}_{14}^\times.
- Find the orders of \mathbb{Z}_{16}^\times, \mathbb{Z}_{21}^\times and \mathbb{Z}_{25}^\times.
- Which of these sets are groups under multiplication? Name the identity of each group. (a) \{1, 9\} \subseteq \mathbb{Z}_{16}; (b) \{1, 3, 9\} \subseteq \mathbb{Z}_{13}; (c) \{5, 25\} \subseteq \mathbb{Z}_{30}; (d) \{0, 5\} \subseteq \mathbb{Z}_{10}.
Symmetries
- Find \mathcal{S}(F) when F is (a) a filled rhombus that is not a square; (b) a filled isosceles triangle that is not equilateral.
- Samir alternates flipping side over side and spinning flat, starting with a flip (Example 4). Where is his mattress after 10 turns? Which positions can he reach if he only ever spins?
Matrices
- Let A = \begin{pmatrix} 3 & 1 \\ 5 & 2 \end{pmatrix} and B = \begin{pmatrix} 1 & 0 \\ 2 & 1 \end{pmatrix} in \operatorname{SL}_2(\mathbb{R}). Compute AB, BA, A^{-1} and (AB)^{-1}.
- Which of these sets are groups under matrix multiplication? (a) Real 2 \times 2 matrices with \det A > 0; (b) with \det A < 0; (c) integer 2 \times 2 matrices with \det A = 1.
- Find the orders of \operatorname{GL}_2(\mathbb{Z}_3) and \operatorname{GL}_2(\mathbb{Z}_5).
- In \operatorname{GL}_2(\mathbb{Z}_3) let C = \begin{pmatrix} 1 & 2 \\ 1 & 0 \end{pmatrix}. Find C^{-1}, show that C^3 = -I_2, and find the smallest k \ge 1 with C^k = I_2.
Proofs
- For a positive integer n, prove that \mu_n = \{z \in \mathbb{C} : z^n = 1\} is a group under multiplication, of order n.
- Prove that the matrices \begin{pmatrix} a & b \\ 0 & d \end{pmatrix} with real a, b, d and ad \ne 0 form a group under multiplication, and that it is not abelian.
- Prove that |\mathbb{Z}_n^\times| is even for every n \ge 3.
- For a prime p, let \operatorname{SL}_2(\mathbb{Z}_p) be the set of matrices in \operatorname{GL}_2(\mathbb{Z}_p) with determinant 1. Prove that |\operatorname{SL}_2(\mathbb{Z}_p)| = p(p^2 - 1).
Answers
- Under addition, -4 = 11 and -7 = 8. Under multiplication, 4 \cdot 4 = 16 \equiv 1, so 4^{-1} = 4, and 7 \cdot 13 = 91 \equiv 1, so 7^{-1} = 13.
- \mathbb{Z}_9^\times = \{1, 2, 4, 5, 7, 8\}. As 2 \cdot 5, 4 \cdot 7 and 8 \cdot 8 are all \equiv 1: 1^{-1} = 1, 2^{-1} = 5, 5^{-1} = 2, 4^{-1} = 7, 7^{-1} = 4, 8^{-1} = 8.
- x = 3 - 5 = -2, so x = 12. In \mathbb{Z}_{14}^\times, 5 \cdot 3 = 15 \equiv 1, so x = 3 \cdot 3 = 9; check: 5 \cdot 9 = 45 \equiv 3.
- \varphi(16) = 8 (the odd classes); \varphi(21) = 12 (21 less the 9 numbers sharing a factor 3 or 7); \varphi(25) = 20.
- Associativity comes from \mathbb{Z}_n. (a) A group with identity 1: 9 \cdot 9 = 81 \equiv 1. (b) A group with identity 1: 3 \cdot 3 = 9, 3 \cdot 9 = 27 \equiv 1, 9 \cdot 9 = 81 \equiv 3, so 3^{-1} = 9. (c) A group with identity 25: 25 \cdot 25 = 625 \equiv 25, 25 \cdot 5 = 125 \equiv 5 and 5 \cdot 5 = 25, so 5^{-1} = 5. (d) Not a group: 5 \cdot 0 = 0 and 5 \cdot 5 \equiv 5 make 5 the identity, but 0 \cdot x = 0 \ne 5, so 0 has no inverse.
- As in Example 3, a symmetry permutes the corners, and by Lemma 5 it is fixed by the images of three corners. (a) Put the corners at (\pm p, 0) and (0, \pm q) with p > q. Only (\pm p, 0) lie 2p apart, so f maps \{(\pm p, 0)\} to itself and \{(0, \pm q)\} to itself: at most 2 \cdot 2 = 4 choices for the images of (p, 0) and (0, q), which fix that of (-p, 0). The four are e, the half turn and the reflections in the two diagonals, with the rectangle’s table. (b) With apex A and AB = AC \ne BC, only A is equally far from the other two corners, so f(A) = A and f fixes or swaps B and C: \mathcal{S}(F) = \{e, m\}, with m the reflection in the line through A and the midpoint of BC.
- Ten turns are 5 side flips and 5 spins, and T is abelian, so the position is F^5S^5 = FS = E: as after one flip end over end. Spinning alone gives only S and S^2 = I_3: the start and the spun position.
- AB = \begin{pmatrix} 5 & 1 \\ 9 & 2 \end{pmatrix}, BA = \begin{pmatrix} 3 & 1 \\ 11 & 4 \end{pmatrix}, A^{-1} = \begin{pmatrix} 2 & -1 \\ -5 & 3 \end{pmatrix} and (AB)^{-1} = \begin{pmatrix} 2 & -1 \\ -9 & 5 \end{pmatrix}, which equals B^{-1}A^{-1}.
- (a) Yes: closed by the product rule, \det I_2 = 1 > 0, and \det A^{-1} = 1/\det A > 0. (b) No: a product of two has positive determinant, and I_2 is missing. (c) Yes: products of integer matrices are integer matrices, and the inverse \begin{pmatrix} d & -b \\ -c & a \end{pmatrix} has integer entries and determinant 1.
- (9 - 1)(9 - 3) = 48 and (25 - 1)(25 - 5) = 480.
- \det C = -2 \equiv 1, so C^{-1} = \begin{pmatrix} 0 & -2 \\ -1 & 1 \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 2 & 1 \end{pmatrix}. Mod 3, C^2 = \begin{pmatrix} 0 & 2 \\ 1 & 2 \end{pmatrix} and C^3 = C^2C = \begin{pmatrix} 2 & 0 \\ 3 & 2 \end{pmatrix} = -I_2. None of C, C^2, C^3 = -I_2, C^4 = -C, C^5 = -C^2 is I_2, and C^6 = (-I_2)^2 = I_2: k = 6.
- Proof. Multiplication in \mathbb{C} is associative with identity 1, and z \ne 0 has inverse 1/z (Complex numbers). If z^n = w^n = 1, then (zw)^n = z^nw^n = 1 (multiplication is commutative) and (1/z)^n = 1/z^n = 1, and 1^n = 1. So \mu_n is closed under products and inverses and contains 1, and associativity is inherited. By Roots of a complex number and roots of unity, z^n = 1 has exactly the n distinct solutions \omega^k, 0 \le k \le n - 1, where \displaystyle \omega = \operatorname{cis}\frac{2\pi}{n}. \square
- Proof. The product of \begin{pmatrix} a & b \\ 0 & d \end{pmatrix} and \begin{pmatrix} a' & b' \\ 0 & d' \end{pmatrix} has diagonal aa', dd', lower left entry 0 and upper right ab' + bd', and aa'dd' \ne 0: the set is closed. It contains I_2, and the inverse \begin{pmatrix} 1/a & -b/(ad) \\ 0 & 1/d \end{pmatrix} lies in it. Associativity holds for all matrices. With X = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} and Y = \begin{pmatrix} 2 & 0 \\ 0 & 1 \end{pmatrix}, XY = \begin{pmatrix} 2 & 1 \\ 0 & 1 \end{pmatrix} but YX = \begin{pmatrix} 2 & 2 \\ 0 & 1 \end{pmatrix}. \square
- Proof. If [a] \in \mathbb{Z}_n^\times, then [-a] \in \mathbb{Z}_n^\times, as \gcd(-a, n) = \gcd(a, n) = 1. If [a] = [-a], then 2a \equiv 0 \cdot a \pmod{n}, and canceling a (Modular inverses and linear congruences, Theorem 3) gives 2 \equiv 0 \pmod{n}, impossible for n \ge 3. So each set \{[a], [-a]\} has two elements, and two such sets that share an element are equal, since -(-a) = a. They split \mathbb{Z}_n^\times into pairs. \square
- Proof. For c \in \mathbb{Z}_p^\times let G_c be the set of matrices in \operatorname{GL}_2(\mathbb{Z}_p) with determinant c, and T_c = \begin{pmatrix} c & 0 \\ 0 & 1 \end{pmatrix}. By the product rule, A \mapsto T_cA maps G_1 into G_c, and B \mapsto T_c^{-1}B maps G_c into G_1; the two maps are inverse to each other, so |G_c| = |G_1|. The p - 1 sets G_c partition \operatorname{GL}_2(\mathbb{Z}_p), so (p - 1)|G_1| = (p^2 - 1)(p^2 - p), and |G_1| = p(p^2 - 1). \square