“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.
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 ∈ ℤ.
Examples:
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ℤ:
These operations are well-defined, that is, they do not depend on the choices of representatives for the classes involved.
Proof:
Suppose a_{1} ≡ b_{1} (mod n) and a_{2} ≡ b_{2} (mod n) then,
∃s, t ∈ ℤ: a_{1} = b_{1} + sn, a_{2} = b_{2} + tn.
a_{1} + a_{2} = b_{1} + b_{2} + (s + t)n ⇒ a_{1} + a_{2} ≡ b_{1} + b_{2} (mod n) ⇒ [a_{1} + a_{2}] = [b_{1} + b_{2}] (the sum of the congruence or residue classes is independent of the representative chosen elements)
a_{1}a_{2} = (b_{1} + sn)(b_{2} + tn) = b_{1}b_{2} + (b_{1}t + b_{2}s + st)n ≡ b_{1}b_{2} (mod n) ⇒ [a_{1}a_{2}] = [b_{1}b_{2}] ∎
$\frac{ℤ}{rℤ}$ is an Abelian group with this operation, [0] is the neutral element, and -[n]=[-n].
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_{10} = {1, 3, 7, 9}. The Cayley table for U_{10} 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.
Examples:
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.
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_{1}n_{2}···n_{k}, ∀i, j, i ≠ j, gcd(n_{i}, n_{j}) = 1. Then, U(m) ≋ U(n_{1})⊕U(n_{2})⊕···⊕U(n_{k}).
Theorem (Gauss, 1801). U(2) = {1} ≋ {0}, U(4) = {1, 3} ≋ ℤ_{2}. U(2^{n}) ≋ U(2^{2}) ⊕ U(2^{n-2}) ≋ ℤ_{2}⊕ℤ_{2n-2} ∀n ≥ 3, U(p^{n}) ≋ ℤ_{pn-pn-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) ≋ ℤ_{4}⊕ℤ_{10} ≋ ℤ_{4}⊕ℤ_{2}⊕ℤ_{5}
U(8) = U(2^{3}) = {1, 3, 5, 7} has 4 elements and is non-cyclic since each element (except the identity 1) has order 2. U(8) ≋ ℤ_{2}⊕ℤ_{2}.
If p = 5, n = 2, U(5^{2}) ≋[U(p^{n}) ≋ ℤ_{pn-pn-1} for p a positive integer and an odd prime] ℤ_{52-51}, i.e., U(25) ≋ ℤ_{20}.
U(16) ≋[U(2^{n}) ≋ ℤ_{2}⊕ℤ_{2n-2} ∀n ≥ 3] ℤ_{2} ⊕ ℤ_{4}, U(9) ≈[9 = 3^{2}, 2 ≱ 3] ℤ_{6}, U(7) ≋ ℤ_{6}, U(5) ≋ ℤ_{4}, U(3) ≋ ℤ_{2}.
U(105) ≋ [105 = 3·5·7] U(3)⊕U(5)⊕U(7) ≋ ℤ_{2} ⊕ ℤ_{4} ⊕ ℤ_{6}. |U(105)| = 2 × 4 × 6 = 48.
U(100) ≋ U(4) ⊕ U(25) ≋ ℤ_{2} ⊕ ℤ_{20}
U(168) ≋ [168 = 3·7·8] U(3)⊕U(7)⊕U(8) ≋ ℤ_{2} ⊕ ℤ_{6} ⊕ ℤ_{2} ⊕ ℤ_{2}.
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. 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.
2401/96, quotient = 25, remainder = 1
(77^{96})^{25} ≡ 1^{25} (mod 97) ⇒ 77^{2400} ≡ 1 (mod 97) ⇒ 77^{2401} ≡ 77 (mod 97).
100,000/52, quotient = 1923, remainder = 4
(3^{52})^{1923} ≡ 1^{1923} (mod 53) ⇒ 3^{99,996} ≡ 1 (mod 53) ⇒ 3^{100,000} = 3^{4}(3^{99,996}) ≡ 3^{4} (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^{12} ≡ 1 (mod13); 2^{12} = 4096 ≡ 1 (mod13); 3^{12} = 531441 ≡ 1 (mod13); [···] and 12^{12} ≡ 1 (mod13).