Integers. Well Ordering Principle. Division & Euclidean Algorithm.

When you have eliminated the impossible, whatever remains, however improbable, must be the truth — Sherlock Holmes

 

The Integers, Divisibility, and the Euclidean Algorithm

While the natural numbers ($\mathbb{N}$) allow us to count, they possess a fatal algebraic flaw: we cannot always subtract. To solve an equation like $x + 5 = 2$, we must expand our mathematical universe. We must invent the integers.

Constructing the Integers ($\mathbb{Z}$)

An integer is a whole number that can be positive, negative, or zero. But mathematically, how do we build negative numbers using only the natural numbers?

We define the integers using equivalence classes of ordered pairs of natural numbers. Imagine a pair of natural numbers $(a, b) \in \mathbb{N} \times \mathbb{N}$ as representing the equation $a - b$. Of course, multiple pairs can represent the same integer. For example, $5 - 3 = 2$, but $7 - 5 = 2$ as well. Therefore, we define an equivalence relation: $(a, b) \sim (c, d) \iff a + d = c + b$

Notice that this definition only uses addition, which is perfectly valid in $\mathbb{N}$! The set of integers, denoted by $\mathbb{Z}$, is the set of all equivalence classes of these ordered pairs.

We can formally define integer addition and multiplication as maps

• $+ : \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}$, $[(a, b)] + [(c, d)] = [(a + c, b + d)]$.
• $\cdot : \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}$, $[(a, b)] \cdot [(c, d)] = [(ac + bd, ad + bc)]$

 

Algebraic Properties of $\mathbb{Z}$

The integers form a rich algebraic structure. They are closed under addition, subtraction, and multiplication.

Property	Addition	Multiplication
Closure	$a + b \in \mathbb{Z}$	$a \cdot b \in \mathbb{Z}$
Associativity	$a + (b + c) = (a + b) + c$	$a \cdot (b \cdot c) = (a \cdot b) \cdot c$
Commutativity	$a + b = b + a$	$a \cdot b = b \cdot a$
Identity	$a + 0 = a$	$a \cdot 1 = a$
Inverses	$a + (-a) = 0$	Only $1$ and $-1$ have inverses in $\mathbb{Z}$

Furthermore, multiplication distributes over addition: $a(b + c) = ab + ac$. Also, $\mathbb{Z}$ has no zero divisors: if $a \cdot b = 0$, then either $a = 0$ or $b = 0$.

In the language of abstract algebra, these properties mean that $(\mathbb{Z}, +)$ is an Abelian group, and $(\mathbb{Z}, +, \cdot)$ is an integral domain.

Finally, the positive integers obey the Well-Ordering Principle (WOP): Every non-empty subset of the positive integers contains a strictly smallest member. This principle is the bedrock of all divisibility proofs.

Divisibility and the Division Algorithm

Definition: Given $a, b \in \mathbb{Z}$ with $a \neq 0$, we say $a$ divides $b$, written $a \mid b$, if there exists some integer $k$ such that $b = ak$.

If $a$ does not divide $b$, we write $a \nmid b$. Examples: $2 \mid 16$ (since $16 = 2 \cdot 8$), but $2 \nmid 27$.

Properties of Divisibility:

1. Transitivity: If $a \mid b$ and $b \mid c$, then $a \mid c$.
2. Scaling: If $a \mid b$, then $ac \mid bc$.
3. Linear Combinations: If $a \mid b$ and $a \mid c$, then for any $x, y \in \mathbb{Z}$, $a \mid (bx + cy)$.
4. Units: If $a \mid 1$, then $a = \pm 1$.

Despite the name, integers do not always divide evenly. When they don’t, we rely on the foundational theorem of arithmetic:

Theorem: The Division Algorithm Let $a, b \in \mathbb{Z}$ with $b > 0$. There exist unique integers $q$ (the quotient) and $r$ (the remainder) such that $a = bq + r$, where $0 \le r < b$.

Proof of Existence:

Consider the set of all possible non-negative remainders: $S = \{a - bx \mid x \in \mathbb{Z}, \text{ and } a - bx \ge 0\}$

First, we must prove $S$ is not empty.

• If $a \ge 0$, let $x = 0$. Then $a - b(0) = a \ge 0$, so $a \in S$.
• If $a < 0$, let $x = a$. Then $a - ba = a(1 - b)$. Since $b \ge 1$ (as $b > 0$), we know $(1 - b) \le 0$. A negative times a non-positive is non-negative, so $a(1 - b) \ge 0$. Thus, $a - ba \in S$.

Since $S$ is a non-empty subset of non-negative integers, the Well-Ordering Principle guarantees it has a smallest element. Let’s call this minimum element $r$. Because $r \in S$, there is some corresponding $x$, which we will call $q$.

Therefore, $r = a - bq \implies a = bq + r$. By definition of the set $S$, $r \ge 0$. But is $r < b$?

Assume for contradiction that $r \ge b$. Then, we could subtract $b$ from $r$ and remain non-negative: $r - b \ge 0$.

Notice that $r - b = a - bq - b = a - b(q + 1)$. This means $(r - b)$ belongs to the set $S$. However, $r - b$ is strictly smaller than $r$, which contradicts our definition that $r$ was the minimum element of $S$! ($\bot$). Thus, $r < b$.

Proof of Uniqueness:

Suppose there are two sets of quotients and remainders: $a = bq + r$ and $a = bq' + r'$, both satisfying the bounds $0 \le r, r \lt b, 0 \le r', r' \lt b$.

Setting them equal: $bq + r = bq' + r' \implies b(q - q') = r' - r$

Take the absolute value of both sides: $b\vert{}q - q'\vert{} = \vert{}r' - r\vert{}$

Because both $r$ and $r'$ are strictly between $0$ and $b-1$, the maximum possible distance between them is strictly less than $b$. Therefore, $\vert{}r' - r\vert{} < b$.

This means $b\vert{}q - q'\vert{} < b$. Since $b > 0$, we can divide by $b$ to get $\vert{}q - q'\vert{} < 1$.

Since $\vert{}q - q'\vert{}$ is a non-negative integer, it must be exactly $0$.

Therefore, $q = q'$, and consequently, $r = r'$. The theorem is proven. ∎

Example: If $a = 9$ and $b = 2$, the division algorithm gives $9 = 4 \times 2 + 1, q = 4, r = 1, 0 \le 1 \lt 2$. If $a = 14$ and $b = 23$, then $14 = 23 \times 0 + 14, q = 0, r = 12$, and $0 \le 12 \lt 23$.

The Greatest Common Divisor (GCD)

An integer $d$ is a common divisor of $a$ and $b$ if $d \mid a$ and $d \mid b$. The greatest common divisor, denoted $\gcd(a, b)$, is the largest positive integer that divides both $a$ and $b$, $\gcd(8, 12) = 4, \gcd(54, 24) = 6$.

A deeper algebraic definition states that $d = \gcd(a,b)$ if $d$ is a common divisor, and for any other common divisor $c$, $c \mid d$.

If $\gcd(a, b) = 1$, we say the two numbers are relatively prime or coprime. They share no common factors other than $1$.

Examples:

• $\gcd(12, 18) = \gcd(2^2 \cdot 3, 3^2 \cdot 2) = \gcd (2 \cdot 3) = 6$ — the GCD takes the lowest power of each common prime factor.
• $\gcd(12, 36) = \gcd(2^2 \cdot 3, 3^2 \cdot 2^2) = \gcd (2^2 \cdot 3) = 12$.
• $\gcd(78, 54) = \gcd(2 \cdot 3 \cdot 13, 2 \cdot 3^3) = 6$.

Bézout’s Identity

One of the most important theorems in number theory states that the GCD of two numbers can always be written as a linear combination of those numbers.

Theorem. For any non-zero integers $a, b \in \mathbb{Z}$, there exist integers $x, y \in \mathbb{Z}$ such that $ax + by = \gcd(a, b)$.

Proof:

Consider the set of all positive linear combinations of $a$ and $b$: $S = \{ax + by \mid x, y \in \mathbb{Z}, \text{ and } ax + by > 0\}$

First, we establish that $S \ne \emptyset$. There are four possibilities:
$a \gt 0 \implies 1 \cdot a + 0 \cdot b \in S$
$a \lt 0 \implies (-1) \cdot a + 0 \cdot b \in S$
$b \gt 0 \implies 0 \cdot a + 1 \cdot b \in S$
$b \lt 0 \implies 0 \cdot a + (-1) \cdot b \in S$

By testing $x = \pm 1$ and $y = \pm 1$, we have shown that $S$ contains positive integers, so $S \neq \emptyset$.

By the Well-Ordering Principle, $S$ has a smallest element, $d$. Thus, $d = ax_0 + by_0$ for some integers $x_0, y_0$.

We claim $d = \gcd(a, b)$.

First, let’s prove $d \mid a$. By the Division Algorithm, $a = dq + r$ with $0 \le r < d$.

Rewrite $r$: $\begin{aligned} r &= a - dq \\ &= a - q(ax_0 + by_0) \\ &= a(1 - qx_0) + b(-qy_0) \end{aligned}$

This shows $r$ is a linear combination of $a$ and $b$. There are two possibilities:

1. If $r > 0$, then $r$ would belong to $S$. But $r < d$, which contradicts the fact that $d$ is the smallest element in $S$! ($\bot$).
2. Thus, $r = 0$, meaning $d \mid a$. By a symmetric argument, $d \mid b$.

Finally, let $c$ be any other common divisor of $a$ and $b$. By the properties of divisibility, if $c \mid a$ and $c \mid b$, then $c \mid (ax_0 + by_0)$. Therefore, $c \mid d$. This proves $d$ is indeed the greatest common divisor. ∎

The Euclidean Algorithm

Finding the GCD of two massive numbers by factoring them is computationally exhausting. The Euclidean Algorithm is a brilliant, hyper-efficient method for finding the GCD without needing to factorize.

It relies on a simple observation: if a number $d$ divides both $x$ and $y$, it must also divide their difference, $x - y$. Therefore, $\gcd(x, y) = \gcd(x - y, y)$

Instead of subtracting repeatedly, we can speed this up massively by using the remainder from the division algorithm! $\gcd(a, b) = \gcd(b, a \pmod b)$

Geometric Intuition: Imagine an $a \times b$ rectangle. You want to tile it perfectly with the largest possible square tiles. You place as many $b \times b$ squares as possible into the rectangle. If there is empty space left over, it will be a smaller rectangle measuring $b \times (a \bmod b)$. You now repeat the process on this smaller rectangle until no space remains!

Examples.

• $\gcd(7469, 2464)$

1. $7469 = 2464 \cdot 3 + 77$. In the following step, we replace 7469, 2464 by 2464 and 77 because $\gcd(7469, 2464) = \gcd(77, 2464)$.
2. $2464 = 77 \cdot 32 + 0$. The gcd is the last remainder different from zero, $\gcd(7469, 2464) = 77$.

• $\gcd(3587,1819)$

1. $3587 = 1819 \cdot 1 + 1768$
2. $1819 = 1768 \cdot 1 + 51$
3. $1768 = 51 \cdot 34 + 34$
4. $51 = 34 \cdot 1 + 17$
5. $34 = 17 \cdot 2 + 0$.

Therefore, $\gcd(3587,1819) = 17$.

Because of Bézout’s Identity, we know we can write the GCD as a linear combination of the two original numbers. We do this by running the Euclidean algorithm, and then working backwards up the chain of equations. This is vital in cryptography (like RSA) for finding modular inverses.

$$\begin{aligned} 17 &= \mathbf{51} - \mathbf{34}(1) \quad &\text{[From Step 4]} \\ &= 51 - [\mathbf{1768} - \mathbf{51}(34)] \quad &\text{[Substitute 34 from Step 3]} \\ &= 51(35) - 1768 \quad &\text{[Group the 51s]} \\ &= [\mathbf{1819} - \mathbf{1768}(1)](35) - 1768 \quad &\text{[Substitute 51 from Step 2]} \\ &= 1819(35) - 1768(35) - 1768 \\ &= 1819(35) - \mathbf{1768}(36) \quad &\text{[Group the 1768s]} \\ &= 1819(35) - [\mathbf{3587} - \mathbf{1819}(1)](36) \quad &\text{[Substitute 1768 from Step 1]} \\ &= 1819(35) - 3587(36) + 1819(36) \\ 17 &= 1819(\mathbf{71}) + 3587(\mathbf{-36}) \quad &\text{[Final grouping]} \end{aligned}$$

We have successfully expressed the GCD as a linear combination: $17 = 1819(71) + 3587(-36)$.

The Foundation of Primes: Euclid’s Lemma and the Fundamental Theorem of Arithmetic

Prime numbers are the indivisible atoms of mathematics. Understanding how they behave and how they build every other number is the central pursuit of number theory. We begin with a formal definition.

Definition: Let $p \in \mathbb{Z}$ with $p > 1$. We say that $p$ is a prime number if its only positive divisors are $1$ and $p$ itself. If an integer strictly greater than 1 is not prime, it is said to be composite.

To prove the most important theorems about primes, we must first recall a powerful corollary of Bézout’s Identity: If two integers $a$ and $b$ are relatively prime (coprime), there exist integers $x, y \in \mathbb{Z}$ such that $ax + by = 1$.

Example: $\gcd(4, 15) = 1$. By Bézout’s identity, $4(4) + 15(-1) = 16 - 15 = 1$.

Euclid’s Lemma

Euclid’s Lemma is arguably the most important property of prime numbers. It states that because a prime is an indivisible mathematical atom, if it divides a product of two numbers, it must be completely embedded inside at least one of those numbers.

Theorem (Euclid’s Lemma): If a prime number $p$ divides the product $ab$ of two integers, then $p$ must divide $a$ or $p$ must divide $b$.

Example: Let $p = 7$, $a = 56$, and $b = 12$. The product $ab = 672$. Since $672$ is divisible by $7$ ($7 \mid 672$), Euclid’s lemma guarantees that $7$ divides $56$ or $7$ divides $12$. Indeed, $7 \mid 56$.

Crucial constraint: The number $p$ must be prime. If it is composite, the lemma collapses. For example, $6 \mid (4 \cdot 3)$ because $6 \mid 12$. However, $6 \nmid 4$ and $6 \nmid 3$. The components of $6$ (which are $2$ and $3$) split apart to divide the two factors separately. Primes cannot split apart.

Proof:

Suppose $p$ is prime and $p \mid ab$. We have two cases:

1. If $p \mid a$, the theorem is immediately proven, and we are done.
2. If $p \nmid a$, we must prove that $p \mid b$.

Because $p$ is prime and it does not divide $a$, the greatest common divisor of $p$ and $a$ must be exactly $1$. They are coprime ($\gcd(a, p) = 1$).

By Bézout’s Identity, there exist integers $x, y$ such that: $ax + py = 1$

Multiply the entire equation by $b$: $abx + pyb = b$

Now, let’s examine the left side of this equation.

• We know $p \mid ab$, therefore $p \mid abx$.
• We also trivially know that $p \mid pyb$.

Because $p$ divides both terms on the left side, it must divide their sum. Therefore, $p$ divides the right side of the equation. $p \mid b \quad \blacksquare$

The Infinitude of Primes

Is there a “largest” prime number? Over two thousand years ago, Euclid provided one of the most elegant proofs in mathematical history to answer this question.

Theorem: There exist infinitely many prime numbers.

Proof:

For the sake of contradiction, assume there is only a finite number of primes. We can list every single one of them: $p_1, p_2, \dots, p_r$.

Let’s construct “a big, fat, ugly new number”, $q$, by multiplying every prime on our list together and adding $1$: $q = (p_1 \cdot p_2 \dots p_r) + 1$

Because $q$ is strictly larger than $1$, it must have at least one prime factor (which could be itself if $q$ is prime). Let’s call this prime factor $p_i$. Since our list is assumed to contain every prime, $p_i$ must be one of the primes on our list. Therefore, $p_i \mid q$.

Every integer greater than 1 can be written uniquely (up to order) as a product of prime numbers.

Also, because $p_i$ is on the list, it divides the massive product: $p_i \mid (p_1 \cdot p_2 \dots p_r)$.

By the linear combination property of divisibility, if $p_i$ divides both of these terms, it must divide their difference: $p_i \mid \Big[ q - (p_1 \cdot p_2 \dots p_r) \Big]$

$p_i \mid 1$. The only positive integer that divides $1$ is $1$. But $1$ is not a prime number! This is a contradiction ($\bot$). Therefore, our initial assumption was false; no finite list of primes can ever be complete. $\blacksquare$

The Fundamental Theorem of Arithmetic

We now arrive at the bedrock of number theory. Every whole number is built out of prime numbers in exactly one unique way.

Theorem: Every integer strictly greater than 1 is either a prime itself or can be factored as a product of prime numbers. Furthermore, this factorization is unique up to the ordering of the factors.

For example, $999 = 3^3 \cdot 37$. The theorem guarantees that no matter how you try to break apart $999$, you will always end up with exactly three $3$s and one $37$.

Proof of Existence (Every number can be factored):

For the sake of contradiction, assume there exist natural numbers greater than $1$ that cannot be factored into primes. By the Well-Ordering Principle, this set of failures must have a strictly smallest element. Let’s call it $m$.

Since $m$ cannot be factored into primes, $m$ itself cannot be prime (If $m$ is prime, then it is already a factorization into primes — namely: $m = m$). Therefore, $m$ must be composite, meaning it can be factored into two strictly smaller integers: $m = a \cdot b$, where $1 < a, b < m$.

Because $m$ was the strictly smallest number that defies prime factorization, the smaller numbers $a$ and $b$ must both obey the rule! Therefore, $a$ and $b$ can both be factored entirely into primes. But if $a$ is made of primes, and $b$ is made of primes, then $m = a \cdot b$ is made entirely of primes. This contradicts our definition of $m$ ($\bot$). Thus, all numbers can be factored.

Proof of Uniqueness:

Suppose a number $n$ has two completely different prime factorizations: $n = p_1 p_2 \dots p_k = q_1 q_2 \dots q_l$

Let’s look at the prime $p_1$ on the left side. Clearly, $p_1$ divides the left side, so it must divide the right side: $p_1 \mid (q_1 q_2 \dots q_l)$

By Euclid’s Lemma, if a prime divides a product, it must divide at least one of the factors. Therefore, $p_1 \mid q_r$ for some prime $q_r$ on the right side.

Since $q_r$ is prime, its only divisors are $1$ and itself. Thus, $p_1 = q_r$.

We can divide both sides by this common prime, canceling it out. We repeat this process iteratively. If the powers of any prime didn’t match (for example, if there were more $p_1$s on the left than on the right), we would eventually be left with a prime equal to $1$, or a prime dividing a product of entirely different primes, which violates Euclid’s Lemma ($\bot$). Therefore, the primes and their exponents must perfectly match. $\blacksquare$

The GCD, the LCM, and the Exponent Trick

We can define the Least Common Multiple (LCM) of two non-zero integers $a$ and $b$, denoted $\text{lcm}(a, b)$, as the smallest positive integer that is completely divisible by both $a$ and $b$.

The Fundamental Theorem of Arithmetic gives us an incredibly elegant way to calculate both the GCD and LCM simultaneously.

Imagine we have two numbers, $m$ and $n$. We can write both of them as a product of the exact same list of primes by allowing exponents of $0$. $m = p_1^{k_1} p_2^{k_2} \dots p_r^{k_r}$, $n = p_1^{l_1} p_2^{l_2} \dots p_r^{l_r}$

• To find the GCD, we simply take the minimum of the exponents for each prime. What is the most they can share?
• To find the LCM, we take the maximum of the exponents for each prime. What is the least required to encompass both?

Example: Let $a = 126$ and $b = 24$. $126 = 2^1 \cdot 3^2 \cdot 7^1$, $24 = 2^3 \cdot 3^1 \cdot 7^0$

• $\gcd(126, 24) = 2^{\min(1,3)} \cdot 3^{\min(2,1)} \cdot 7^{\min(1,0)} = 2^1 \cdot 3^1 \cdot 7^0 = 6$
• $\text{lcm}(126, 24) = 2^{\max(1,3)} \cdot 3^{\max(2,1)} \cdot 7^{\max(1,0)} = 2^3 \cdot 3^2 \cdot 7^1 = 504$.

This exponent trick leads to a beautiful geometric theorem:

Definition. The least common multiple or smallest common multiple of two non-zero integers a and b, typically denoted by lcm(a, b), is the smallest positive integer that is a multiple of (or divisible by) both a and b.

Theorem: The product of the LCM and the GCD of two positive integers is exactly equal to the product of the integers themselves. $\text{lcm}(m, n) \cdot \gcd(m, n) = m \cdot n$

Proof:

Using our prime exponent notation, if we multiply the LCM and the GCD, we are adding their exponents together for every prime $p_i$: $\text{lcm}(m,n) \cdot \gcd(m,n) = \prod p_i^{\max(k_i, l_i)} \cdot \prod p_i^{\min(k_i, l_i)}$

For any two numbers, the maximum plus the minimum is always exactly equal to the sum of the two numbers! $\max(k_i, l_i) + \min(k_i, l_i) = k_i + l_i$

Therefore, the product is exactly: $\prod p_i^{k_i + l_i} = \left( \prod p_i^{k_i} \right) \left( \prod p_i^{l_i} \right) = m \cdot n \quad \blacksquare$