The Integers modulo n. The Group of Units. Fermat’s Theorem.

“Life is good and there’s no reason to think it won’t be, right until the moment when a blonde, non experienced nurse is going to insert a catheter in your penis like a Spanish matador,” Dad retorted. [···]

“Unless your name is Google, stop pretending you know everything. Unless your name is Facebook, stop sharing it because unless your name is Amazon, we are not buying it,” the class’ bully teased me once again, Apocalypse, Anawim, #justtothepoint.

Modular Arithmetic as an Equivalence Relations.

Let n be a fixed positive integer. Let’s define a relation on ℤ by a ~ b if and only if n | (b - a). It is clearly an equivalence relation. It is written as a ≡ b (mod n), “a is congruent to be mod n”.

An alternative is a ~ b if and only if b - a = kn for some k ∈ ℤ.

• Reflexive: a ~ a ↭ a - a = 0 = 0·n, therefore a ≡ a (mod n).
• Symmetry: a ~ b ↭ ∃k ∈ ℤ: b - a = kn ⇒ ∃-k ∈ ℤ: a -b = -kn
• Transitivity a ~ b ↭ ∃k ∈ ℤ : b - a = kn, b ~ c ↭ ∃k’ ∈ ℤ: c - b = k’n ⇒∃(k + k’) ∈ ℤ : c - a = (k + k’)n ⇒ a ~ c

Examples:

• 7 ≡ 1 (mod 3), 5 ≡ 2 (mod 3).
• $12 \equiv 5 (mod~ 7)$, but $9 \not\equiv 5 (mod~ 7)$
• 10 ≡ 0 (mod 5), 12 ≡ 2 (mod 5).

  12 ≡ 5 is written in LaTeX as 12 \equiv 5, but $9 \not\equiv 5$ is written as 9 \not\equiv 5.

Let [a] be the equivalent class of a. It is called the congruence class or residue class of a mod n. It is the set of integers that are congruent to a modulo n, that is, that differ from a by a multiple of n, i.e., [a] = {b: b ∈ ℤ: b ≡ a (mod n)} = {a + kn: k ∈ ℤ} = {a, a ± n, a ± 2n, a ± 3n, ···}.

Notice that there are n-1 possible remainders after division by n ⇒ there are n distinct equivalence classes mod n. Therefore, the integers modulo n are the set of these equivalence classes = {[0], [1], [2], … [n-1]}, usually symbolized by the quotient ℤ/nℤ. The representative is just the remainder of the integer when divided by n.

Let’s define an addition and multiplication for ℤ/nℤ:

1. [a] + [b] = [a+b]
2. [a] · [b] = [ab]

These operations are well-defined, that is, they do not depend on the choices of representatives for the classes involved.

Proof:

Suppose a₁ ≡ b₁ (mod n) and a₂ ≡ b₂ (mod n) then,

∃s, t ∈ ℤ: a₁ = b₁ + sn, a₂ = b₂ + tn.

a₁ + a₂ = b₁ + b₂ + (s + t)n ⇒ a₁ + a₂ ≡ b₁ + b₂ (mod n) ⇒ [a₁ + a₂] = [b₁ + b₂] (the sum of the congruence or residue classes is independent of the representative chosen elements)

a₁a₂ = (b₁ + sn)(b₂ + tn) = b₁b₂ + (b₁t + b₂s + st)n ≡ b₁b₂ (mod n) ⇒ [a₁a₂] = [b₁b₂] ∎

$\frac{ℤ}{rℤ}$ is an Abelian group with this operation, [0] is the neutral element, and -[n]=[-n].

The Group of Units.

The group ℤ_n consists of the elements {[0], [1], [2], . . . , [n-1]} with addition mod n as the operation. For convenience’s sake, we identify each equivalence class with its representative. You can also multiply elements of Z_n, but you do not obtain a group. For instance, the identity element 0 does not have a multiplicative inverse.

ℤ_n is a commutative ring with identity 1.

However, if you confine your attention to the units in ℤ_n, that is, the elements which have multiplicative inverses, u ∈ ℤ_n is a unit if ∃v ∈ ℤ_n: u·v = 1 and v is called a multiplicative inverse of u, then you indeed get a group under multiplication mod n. It is denoted as U_n, and is called the group of units in ℤ_n

Theorem. An integer “a” has a multiplicative inverse modulo n if and only if a and n are coprime or relative prime. Figure 1.b.

Proof.

⇐) Let n be an integer, suppose a is coprime to n ⇒ [By Bézout’s identity] ∃α, β ∈ ℤ: αa + βn = 1 ⇒ αa = 1 - βn ⇒ αa ≡ 1(mod n) ⇒ a has a multiplicative inverse (α).

⇒) Suppose that a has a multiplicative inverse and, for the sake of contradiction, a is not coprime to n ⇒∃d ∈ ℤ, d > 1 such that a = da’, n = db and (a has a multiplicative inverse, αa ≡ 1 (mod n) ) αa = 1 + βn for some α, β ∈ Z ⇒ αda’ = 1 + βnb ⇒ d(αa’ -βb) = 1 ⇒ d = ±1 ⊥ (which is impossible since d > 1)∎

For each n > 1, we define U_n to be the set of all positive integers less than n that have a multiplicative inverse modulo n, that is, ∀a ∈ U_n, ∃ b ∈ Z_n : ab = 1. U_n = {a ∈ Z_n: a is relatively prime to n, a < n} = {a ∈ Z_n: gcd(a, n)=1}. In particular, |U_n| = φ(n) where φ is the Euler’s totient function.

Equivalently, the elements of this group can be thought of as the congruence classes, also known as residues modulo n, that are coprime to n. (ℤ/nℤ)^x = {[a] ∈ ℤ/nℤ | gcd(a, n) = 1}

Theorem. ℤ/nℤ ≋ ℤ_n.

Example. For n = 10, U₁₀ = {1, 3, 7, 9}. The Cayley table for U₁₀ is in Figure 1.a.

Proposition. U_n = {[m]| gcd(m, n) = 1} is a group under multiplication mod n, i.e., [x][y] = [xy]. It is called the multiplicative group of integers modulo n.

1. is it well defined? [a]·[b] = [ab] have been previously demonstrated that they do not depend on the choices of representatives for the classes involved. Besides, ∀a, b ∈ U_n, ∃a^-1, b^-1. (b^-1a^-1)(ab) =[Associative] b^-1(a^-1a)b = (b^-1b) = e. Analogously, mutatis mutandis (ab)(b^-1a^-1) = e ⇒ ab has a multiplicate inverse, ab ∈ U_n.
2. Associativity is inherited from Z_n.
3. The identify is 1 with multiplicative inverse to be itself.
4. Every element of U_n has a multiplicative inverse by definition.

Examples:

• U₅ = {1, 2, 3, 4} and U₆ = {1, 5}. Their Cayley’s table are shown in Figure 1.c and 1.d respectively.

• If p is a prime, then all the positive integers smaller than p are relatively prime to p. Then, U(p) = {1, 2, 3, ···, p-1} e.g., U(3) = {1, 2}, U(7) = {1, 2, 3, 4, 5, 6}, and U₁₁ = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.
• U(14) = {1, 3, 5, 9, 11, 13}. Notice that you multiply elements of U(14) by multiplying as if they were integers, then reducing mod 14, e.g., 11·13 = 143 = 3 (mod 14).
• U(21) = {1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20}.

Definition. The subgroup generated by an element. If k is a divisor of n. U_k(n) = {x ∈ U(n): x mod k = 1}. U_k(n) is a subgroup of U(n).

Examples.

• U(18) = {1, 5, 7, 11, 13, 17}. 3 is a divisor of 18, U₃(18) = {x ∈ U(18): x mod 3 = 1} = {1, 7, 13} = ⟨7⟩ ≤ U(18).
• U(105) = {1, 2, 4, 8, 11, 13, 16, 17, 19, 22, 23, 26, 29, 31, 32, 34, 37, 38, 41, 43, 44, 46, 47, 49, 52, 53, 56, 58, 59, 61, 62, 64, 67, 68, 71, 73, 74, 76, 79, 82, 83, 86, 88, 89, 92, 94, 97, 98, 101, 103, 104}. 7 is a divisor of 105. U₇(105) = {x ∈ U(105): x mod 7 = 1} = {1, 8, 22, 29, 43, 64, 71, 92}.

The Group of Units Modulo n as an External Direct Product

Theorem. Suppose s and t are relatively prime. Then, U(st) ≋ U(s)⊕U(t), i.e., U(st) is isomorphic to the external direct product of U(s) and U(t). Futhermore, U_s(st) ≋ U(t) and U_t(st) ≋ U(s). Proof.

Corollary. Let m = n₁n₂···n_k, ∀i, j, i ≠ j, gcd(n_i, n_j) = 1. Then, U(m) ≋ U(n₁)⊕U(n₂)⊕···⊕U(n_k).

Theorem (Gauss, 1801). U(2) = {1} ≋ {0}, U(4) = {1, 3} ≋ ℤ₂. U(2ⁿ) ≋ U(2²) ⊕ U(2^n-2) ≋ ℤ₂⊕ℤ_2^n-2 ∀n ≥ 3, U(pⁿ) ≋ ℤ_pⁿ-p^n-1 for p a positive integer and an odd prime.

Theorem. Every group U(n) is isomorphic to the external direct product of cyclic groups.

Examples:

• U(55) ≋[Criterion for the direct product to be cyclic] U(5) ⊕ U(11) ≋ ℤ₄⊕ℤ₁₀ ≋ ℤ₄⊕ℤ₂⊕ℤ₅

• U(8) = U(2³) = {1, 3, 5, 7} has 4 elements and is non-cyclic since each element (except the identity 1) has order 2. U(8) ≋ ℤ₂⊕ℤ₂.

• If p = 5, n = 2, U(5²) ≋[U(pⁿ) ≋ ℤ_pⁿ-p^n-1 for p a positive integer and an odd prime] ℤ_5²-5¹, i.e., U(25) ≋ ℤ₂₀.

• U(16) ≋[U(2ⁿ) ≋ ℤ₂⊕ℤ_2^n-2 ∀n ≥ 3] ℤ₂ ⊕ ℤ₄, U(9) ≈[9 = 3², 2 ≱ 3] ℤ₆, U(7) ≋ ℤ₆, U(5) ≋ ℤ₄, U(3) ≋ ℤ₂.

• U(105) ≋ [105 = 3·5·7] U(3)⊕U(5)⊕U(7) ≋ ℤ₂ ⊕ ℤ₄ ⊕ ℤ₆. |U(105)| = 2 × 4 × 6 = 48.

• U(100) ≋ U(4) ⊕ U(25) ≋ ℤ₂ ⊕ ℤ₂₀

• U(168) ≋ [168 = 3·7·8] U(3)⊕U(7)⊕U(8) ≋ ℤ₂ ⊕ ℤ₆ ⊕ ℤ₂ ⊕ ℤ₂.

Euler’s theorem

Euler’s theorem. Let a, n ∈ ℤ, n > 0 and gcd(a, n) = 1. Then, a^Φ(n)≡1 (mod n).

Proof.

If gcd(a, n) = 1 ⇒ a ∈ ℤ_n^* = U(n), |U(n)| = Φ(n) ⇒ [By Lagrange’s theorem. The order of an element of a finite group divides the order of the group] a^Φ(n) = e ↭ a^Φ(n) ≡ 1 (mod n)∎

Fermat’s Theorem

Fermat’s Theorem. If a and p are integers, p is prime, and p ɫ a, then a^p−1 ≡ 1 (mod p). Futhermore, a^p≡ a (mod p) for any integer a.

Proof.

If p is prime, then U_p = {1, 2, 3, ···, p-1}, |U_p| = Φ(p) = p-1.

If p is prime and p ɫ a ⇒ a ≡ b (mod p), where b ∈ {1, 2, 3, ···, p-1} -we could exclude the 0 from the list, b≠ 0-

⇒ [By Lagrange’s theorem. The order of an element of a finite group divides the order of the group, a^|G|=e.] b^p-1 ≡ 1 (mod p) ⇒[a ≡ b (mod p)] a^p-1 ≡ b^p-1 ≡ 1 (mod p) ∎.

a^p≡ a (mod p) is an immediate consequence by multiplying both sides of a^p−1 ≡ 1 (mod p) by a. Besides, if p | a, then a ≡ 0 (mod p), and a^p ≡ 0^p ≡ 0 ≡ 0 (mod p).

Examples. Let’s use this recently proven Fermat’s Theorem to reduce power.

• 77²⁴⁰¹ (mod 97). 97 is prime, 97 ɫ 77 ⇒ [Fermat’s Theorem. p is prime, p ɫ a, then a^p−1 ≡ 1 (mod p).] 77⁹⁶ ≡ 1(mod 97).

2401/96, quotient = 25, remainder = 1

(77⁹⁶)²⁵ ≡ 1²⁵ (mod 97) ⇒ 77²⁴⁰⁰ ≡ 1 (mod 97) ⇒ 77²⁴⁰¹ ≡ 77 (mod 97).

• 3^100,000 (mod 53). 53 is prime, 53 ɫ 3 ⇒ [Fermat’s Theorem. p is prime, p ɫ a, then a^p−1 ≡ 1 (mod p).] 3⁵² ≡ 1 (mod 53).

100,000/52, quotient = 1923, remainder = 4

(3⁵²)¹⁹²³ ≡ 1¹⁹²³ (mod 53) ⇒ 3^99,996 ≡ 1 (mod 53) ⇒ 3^100,000 = 3⁴(3^99,996) ≡ 3⁴ (mod 53) ⇒ 3^100,000 ≡ 81 (mod 53) ≡ 28 (mod 53).

Fermat’s Little Theorem Converse. If m ≥ 2 and ∀a: 1 ≤ a ≤ m-1, a^m-1≡ 1 (mod m) ⇒ m is prime.

Proof. (Source LibreTexts,Elementary Number Theory (Barrus and Clark), Primality Test.)

If m ≥ 2 and ∀a: 1 ≤ a ≤ m-1, a^m-1≡ 1 (mod m) ⇒ a has an inverse modulo m, namely a^m-2 ⇒ [An integer has an inverse modulo m ↭ (a, m) = 1] ∀a: 1 ≤ a ≤ m-1, (a, m) = 1. Claim: m is prime.

For the sake of contradiction, suppose m is not prime ⇒ m = a·b, 1 < a < m, 1 < b < m ⇒ gcd(a, m) = a > 1 ⊥

Corollary. Primarily Test. Given an integer m ≥ 2, for each a between 1 and m -1, test wether a^m-1 ≡ 1 (mod m). If the congruence is true for every value of a, then m is prime. Otherwise, if the congruence fails for any value of a between 1 and m-1, then m is not prime.

Example: 13 is prime because 1¹² ≡ 1 (mod13); 2¹² = 4096 ≡ 1 (mod13); 3¹² = 531441 ≡ 1 (mod13); [···] and 12¹² ≡ 1 (mod13).

Bibliography

1. NPTEL-NOC IITM, Introduction to Galois Theory.
2. Algebra, Second Edition, by Michael Artin.
3. LibreTexts, Abstract and Geometric Algebra, Abstract Algebra: Theory and Applications (Judson).
4. Field and Galois Theory, by Patrick Morandi. Springer.
5. Michael Penn (Abstract Algebra), and MathMajor.
6. Contemporary Abstract Algebra, Joseph, A. Gallian.
7. Andrew Misseldine: College Algebra and Abstract Algebra.