Primes Factorization

Euclid’s Theorem. Primes are infinite.

Proof. Let’s assume that the set of primes P = {p₁, ..., pₙ} is finite and let k = ∏ pᵢ. If the factorization of k+1 contains one prime pᵢ ∈ P then pᵢ|k+1. Since pᵢ|k then pᵢ|(k+1-k)=1, which is impossible. Follows that k+1 is a new prime or is divisible by a prime not in P.

Fundamental Theorem of Arithmetic

Every integer n ≥ 1 can be uniquely written as the product of primes. That is, n = ∏ pᵢ^eᵢ with eᵢ ∈ N and pᵢ ∈ P.

Proof. Trivial, by induction.

GCD and LCM

The greatest common divisor (gcd) is defined as:

gcd(a,b) = max { d > 0: d|a and d|b }

With a and b not both zero.

Property. For any integer a ∈ Z, gcd(a,0) = |a| (should be positive)

The least common multiple (lcm) is defined as:

lcm(a,b) = min { m > 0: a|m and b|m }

Given two integers a and b lets write both of them as the product of all the primes pᵢ ∈ P that appear at least in one of the factorization of the numbers:

a = ∏ pᵢ^eᵢ
b = ∏ pᵢ^kᵢ

The two products may differ only for some of the exponents values. Some exponents can be zero if such prime doesn’t appear in the factorization of the number according to the fundamental theorem of arithmetic.

Then we can define both the gcd and lcm as:

gcd(a,b) = ∏ pᵢ^min{eᵢ,kᵢ)
lcm(a,b) = ∏ pᵢ^max{eᵢ,kᵢ}

Follows that:

a·b = gcd(a,b)·lcm(a,b)`

From now on, if the context is not ambiguous, as a shortcut we’ll use the popular notation gcd(a,b) = (a,b).

Definition. Two integers a and b are coprime if (a,b) = 1.

Division Theorem

For every integer a and non-zero integer b > 0 there exist unique q and r such that:

a = b·q + r  with  0 ≤ r < b

Existence Proof.

Let R = { r: r = a - b·q ≥ 0 }, the set is not empty since b·q can be made arbitrary small by taking a negative q. For the well ordering principle there is min r₀. Also, r₀ < b because if instead r₀ ≥ b, then we can define r₁ = r₀ - b ≥ 0 and thus r₀ was not the min.

Uniqueness Proof.

If a = b·q' + r' then (assuming r ≥ r') 0 ≤ r - r' = b·(q' - q) ≤ r < b. Dividing both sides by b we have that 0 ≤ (q - q') < 1. Follows that q - q' = 0, thus that q = q' and consequently r = r'.

∎

From the division theorem follows that q and r are functions of a and b.

These functions have quite popular names:

• q = a div b is the integer division operation result;
• r = a mod b is the integer modulo operation result.

The functions images also have very well known names:

• q is the division quotient
• r is the division remainder

Homomorphism

Consider the set of integers equipped with the operation sum (Z, +) and the set of remainders modulo n equipped with the operation modular sum (Zₙ, +ₙ).

The modulo operation is an homomorphism between these two sets.

That is, given a, b ∈ Z and setting f(x) = (x mod n) ∈ Zₙ.

f(a + b) = f(a) +ₙ f(b)

(a + b) mod n = (a mod n) +ₙ (b mod n)

Proof

a mod n = r₁ = a - n·q₁
b mod n = r₂ = b - n·q₂
→ r₁ + r₂ = a + b - n·(q₁ + q₂)
→ r₁ + r₂ ≡ a + b (mod n)

The same holds for the product:

f(a · b) = f(a) ·ₙ f(b)

(a · b) mod n = (a mod n) ·ₙ (b mod n)

Proof

a mod n = r₁ = a - n·q₁
b mod n = r₂ = b - n·q₂
→ r₁·r₂ = a·b - a·n·q₂ - b·n·q₁ + n²·q₁·q₂
→ r₁·r₂ ≡ a·b (mod n)

From now on, for simplicity, we’ll write +ₙ as + and ·ₙ as · both followed by the (mod n) postfix to make the reduction modulo n explicit.

Modular Arithmetic Properties

1. a ≡ b (mod n) iff a+k ≡ b+k (mod n), for any integer k

Proof (→)

a = q₁·n + r  and  b = q₂·n + r
→ a + k = q₁·n + (r + k)  and  b + k = q₂·n + (r + k)
→ a + k ≡ b + k ≡ r + k (mod n)

2. If a ≡ b (mod n) then a·k ≡ b·k (mod n), for any integer k

The proof similar to the previous one. But the converse holds iff (k,n) = 1.

3. If a ≡ b (mod n) then aᵏ ≡ bᵏ (mod n), for any integer k

Proof (from property 2)

a ≡ b (mod n) → a² ≡ b·a (mod n) and a·b ≡ b² (mod n) → a² ≡ b² (mod n)
The thesis follows by induction.

4. It is not the case that if a ≡ b (mod n) then k^a ≡ k^b (mod n)

Counter example: 3 ≡ 8 (mod 5) but 2^3 ≢ 2^8 (mod 5)

5. If (a,m) = 1 and (a,n) = 1 then (a,m·n) = 1

Proof If a prime p|a since (a,m) = 1 then p⫮m and the same holds for n. For p to divide m·n it must divide at least one of m or n. However, p divides neither of m nor n, thus p⫮(m·n).

Proof (using Bezout’s identity)

a·s + m·t = 1` and `a·h + n·k = 1
→ a·(a·s·h + s·n·k + m·h·t) + m·n·t·k = 1
→ (a,m·n) = 1

Multiplicative Inverse

Proposition. The multiplicative inverse of a modulo n exists iff (a,n) = 1.

Proof

(⇒) If x is the inverse of a, then a·x ≡ 1 (mod n) and thus 1 = a·x + n·y. If d|a and d|n then d|1. Thus, d = 1.

(⇐) If (a,n) = 1 then for Bezout’s identity 1 = a·x + n·y ≡ a·x (mod n). Thus, x is the inverse of a modulo n.

∎

Proposition. When the inverse exists is unique modulo n.

Proof. If x and y are both inverses of a ∈ Zₙ then a·x ≡ 1 (mod n) → y·a·x ≡ y (mod n) → x ≡ y (mod n)

∎

Algebraic Structures

Given c ∈ Zₙ:

• additive inverse always exists and is n - c
• multiplicative inverse exists iff gcd(c,n) = 1

For example, in Z₁₀:

(1,10) = 1  →  1⁻¹ = 1
(3,10) = 1  →  3⁻¹ = 7  →  3·7 = 21 ≡ 1 (mod 10)
(7,10) = 1  →  7⁻¹ = 3  →  3·7 = 21 ≡ 1 (mod 10)
(9,10) = 1  →  9⁻¹ = 9  →  9·9 = 81 ≡ 1 (mod 10)

We define Zₙ* as the set of numbers in Zₙ with multiplicative inverse:

Zₙ* = { x ∈ Zₙ: gcd(x,n) = 1 }

For example, Z₁₀* = { 1, 3, 7, 9 }

Zₙ* is a group with respect to the product.

Closure: If a, b ∈ Zₙ* then a·b = c ∈ Zₙ*

Proof.

a·b = c  →  (a·b)·(b⁻¹·a⁻¹) = c·(b⁻¹⋅a⁻¹) = c·k ≡ 1 (mod n)
Follows that k = b⁻¹·a⁻¹ is the inverse of c and thus c ∈ Zₙ*

Note that in general Zₙ* is not a group with respect to the addition. (For example, 1 + 3 = 4 ∉ Z₁₀*).

If p is a prime number then Zᵨ* = Zᵨ\{0} is an abelian group with multiplication and Zᵨ is an abelian group with addition. That is (Zᵨ*, ·) and (Zᵨ, +) are both abelian groups.

Because in Zᵨ the distributivity of multiplication over addition holds then Zᵨ is a finite field.

All known finite fields are Z_(pᵏ), with k ≥ 1 and p a prime number. If k > 1 then the field is called an extension field and its elements are polynomials.

Congruence Classes

By definition, a is congruent to b modulo n > 0 if a mod n = b mod n.

Common alternative notations for a congruent to b modulo n are a ≡ b (mod n) or a ≡ₙ b.

Fixed n > 0 then Zₙ = { 0, ..., n-1 } is the set of all the possible remainders modulo n.

Proposition. a ≡ b (mod n) iff n | (a - b)

Proof

⇒   r = a - n·q₁ = b - n·q₂
    → a - b = n·(q₁ - q₂)
    → n | (a - b)

⇐   n | (a - b)
    → a - b = n·q + r, with r = 0
    → given that should exist unique q₁, r₁, q₂, r₂ such that
      a = n·q₁ + r₁ and b = n·q₂ + r₂
    → a - b = n·(q₁ - q₂) + (r₁ - r₂)
    → r = r₁ - r₂ = 0 → r₁ = r₂

∎

Congruence between remainder classes is an equivalence relation. That is, reflexive, symmetric, transitive properties hold.

Elements in ℤ that are equivalent according to the congruence relation are said to belong to the same equivalence class.

For example, if a = n·q₁ + r and b = n·q₂ + r then both a and b are in the congruence class [r]ₙ.

If a = n·q + r, the set of elements in the same congruence class [r]ₙ are defined as:

[r]ₙ = { r + k·n, ∀ k ∈ Z }

The set of all the congruence classes modulo n is:

Z/n = { [0]ₙ, [1]ₙ, ... , [n-1]ₙ }, with |Z/n| = n

Set of representatives

A complete set of representatives refers to a specific selection of integers chosen to represent all the different congruence classes in Z/n. Each congruence class is represented by one and only once element.

Each representative can be chosen by using a different criterion, what is important is that there is only one representative for each class.

Given a modulo n and a number a, if r is the integer division remainder of a divided n, then r is the smallest positive value in the class [r]ₙ and is often taken as the representative for the whole congruence class.

Zₙ = { 0, 1, .. , n-1 }, with |Zₙ| = n

Nevertheless, in some cases makes sense to work with representatives chosen using different criteria (e.g. bigger or negative numbers).

Proposition. If { a₁, .. , aₙ } is a complete set of representatives, then for any integer b, { a₁+b, .. , aₙ+b } is a complete set of representatives.

Proof

If not, then aᵢ+b ≡ aⱼ+b (mod n) and thus aᵢ ≡ aⱼ (mod n), contradicting the hypothesis.

∎

Proposition. If { a₁, .. , aₙ } is a complete set of representatives for Zₙ, then { a₁·b, .. , aₙ·b } is a complete set of representatives iff (b,n) = 1.

Proof

If (b,n) = 1 and aᵢ·b ≡ aⱼ·b (mod n) then there exists the inverse of b modulo n. Thus follows that aᵢ ≡ aⱼ (mod n), contradicting the hypothesis.

Conversely, if (b,n) = d, with 1 < d < n, then there exists a non-zero value z = n/d < n such that b·z ≡ 0 (mod n) (note: b and z are both non-zero and their product is 0 mod n, these are called zero-divisors). In this case the set { a₁·b, .., aₙ·b } cannot be a set of representatives since if 0 is equal to some aᵢ·b then now there are two elements congruent to 0 modulo n (namely 0·b and z·b).

∎

Note that from the previous proof follows that if p is prime then Zᵨ doesn’t have zero-divisors and the property always hold for all b.

Further readings

• Euclidean algorithm
• Chinese remainder theorem
• Euler’s totient
• Fermat’s little theorem and Euler’s theorem
• Number theory and Abstract Algebra notes.
• Fast Modular Exponentiation