JustToThePoint English Website Version
JustToThePoint en español
JustToThePoint in Thai

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 ∈ ℤ.

Examples:

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.

ℤ/nℤ = ℤn, the integers modulo n = {[0], [1], [2], … [n-1]} ≠ {0, 1, 2, ··· n}. ℤ/nℤ = ℤn is the set of equivalence classes, not the set of its representatives.

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 a1 ≡ b1 (mod n) and a2 ≡ b2 (mod n) then,

∃s, t ∈ ℤ: a1 = b1 + sn, a2 = b2 + tn.

a1 + a2 = b1 + b2 + (s + t)n ⇒ a1 + a2 ≡ b1 + b2 (mod n) ⇒ [a1 + a2] = [b1 + b2] (the sum of the congruence or residue classes is independent of the representative chosen elements)

a1a2 = (b1 + sn)(b2 + tn) = b1b2 + (b1t + b2s + st)n ≡ b1b2 (mod n) ⇒ [a1a2] = [b1b2] ∎

$\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 Zn, 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 Un, 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 Un to be the set of all positive integers less than n that have a multiplicative inverse modulo n, that is, ∀a ∈ Un, ∃ b ∈ Zn : ab = 1. Un = {a ∈ Zn: a is relatively prime to n, a < n} = {a ∈ Zn: gcd(a, n)=1}. In particular, |Un| = φ(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, U10 = {1, 3, 7, 9}. The Cayley table for U10 is in Figure 1.a.

Proposition. Un = {[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 ∈ Un, ∃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 ∈ Un.
  2. Associativity is inherited from Zn.
  3. The identify is 1 with multiplicative inverse to be itself.
  4. Every element of Un has a multiplicative inverse by definition.

Examples:

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

Examples.

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, Us(st) ≋ U(t) and Ut(st) ≋ U(s). Proof.

Corollary. Let m = n1n2···nk, ∀i, j, i ≠ j, gcd(ni, nj) = 1. Then, U(m) ≋ U(n1)⊕U(n2)⊕···⊕U(nk).

Theorem (Gauss, 1801). U(2) = {1} ≋ {0}, U(4) = {1, 3} ≋ ℤ2. U(2n) ≋ U(22) ⊕ U(2n-2) ≋ ℤ2⊕ℤ2n-2 ∀n ≥ 3, U(pn) ≋ ℤ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:

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 ap−1 ≡ 1 (mod p). Futhermore, ap≡ a (mod p) for any integer a.

Proof.

If p is prime, then Up = {1, 2, 3, ···, p-1}, |Up| = Φ(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.] bp-1 ≡ 1 (mod p) ⇒[a ≡ b (mod p)] ap-1 ≡ bp-1 ≡ 1 (mod p) ∎.

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

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

2401/96, quotient = 25, remainder = 1

(7796)25 ≡ 125 (mod 97) ⇒ 772400 ≡ 1 (mod 97) ⇒ 772401 ≡ 77 (mod 97).

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

(352)1923 ≡ 11923 (mod 53) ⇒ 399,996 ≡ 1 (mod 53) ⇒ 3100,000 = 34(399,996) ≡ 34 (mod 53) ⇒ 3100,000 81 (mod 53) ≡ 28 (mod 53).

Fermat’s Little Theorem Converse. If m ≥ 2 and ∀a: 1 ≤ a ≤ m-1, am-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, am-1≡ 1 (mod m) ⇒ a has an inverse modulo m, namely am-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 am-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 112 ≡ 1 (mod13); 212 = 4096 ≡ 1 (mod13); 312 = 531441 ≡ 1 (mod13); [···] and 1212 ≡ 1 (mod13).

Bibliography

This content is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. This post relies heavily on the following resources, specially on NPTEL-NOC IITM, Introduction to Galois Theory, Michael Penn, and Contemporary Abstract Algebra, Joseph, A. Gallian.
  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.
Bitcoin donation

JustToThePoint Copyright © 2011 - 2024 Anawim. ALL RIGHTS RESERVED. Bilingual e-books, articles, and videos to help your child and your entire family succeed, develop a healthy lifestyle, and have a lot of fun.

This website uses cookies to improve your navigation experience.
By continuing, you are consenting to our use of cookies, in accordance with our Cookies Policy and Website Terms and Conditions of use.