Divisibility Theory & The Fundamental Theorem of Arithmetic

1. The Well-Ordering Principle of $\mathbb{N}$

Number theory rests upon the foundational structure of the set of integers $\mathbb{Z} = \{0, \pm 1, \pm 2, \dots\}$ and positive integers (natural numbers) $\mathbb{N} = \{1, 2, 3, \dots\}$.

Axiom 1.1 (The Well-Ordering Principle): Every non-empty subset $S \subseteq \mathbb{N}$ contains a least element (or minimum element):

The Well-Ordering Principle is logically equivalent to the Principle of Mathematical Induction and the Principle of Strong Mathematical Induction. It provides the fundamental deductive bedrock for proving existence, termination of algorithms, and impossibility via the method of infinite descent.

2. Divisibility in the Integers

Definition 1.1 (Divisibility): Let $a, b \in \mathbb{Z}$ with $a \ne 0$. We say that $a$ divides $b$ (or that $b$ is a multiple of $a$), denoted $a \mid b$, if there exists an integer $c \in \mathbb{Z}$ such that:

If $a$ does not divide $b$, we write $a \nmid b$.

Theorem 1.1 (Elementary Properties of Divisibility): For all $a, b, c, d \in \mathbb{Z}$:

1. Reflexivity: $a \mid a$ for all $a \ne 0$.

2. Transitivity: If $a \mid b$ and $b \mid c$, then $a \mid c$.

3. Linearity: If $a \mid b$ and $a \mid c$, then $a \mid (bx + cy)$ for any integers $x, y \in \mathbb{Z}$.

4. Cancellation: If $a \mid b$, then $ac \mid bc$ for all $c \ne 0$.

5. Size constraint: If $a \mid b$ and $b \ne 0$, then $|a| \le |b|$.

3. The Division Algorithm

Theorem 1.2 (The Division Algorithm): Let $a, b \in \mathbb{Z}$ with $b > 0$. Then there exist unique integers $q, r \in \mathbb{Z}$ such that:

Here $q$ is called the quotient ($q = \lfloor a/b \rfloor$) and $r$ is called the remainder ($r = a \bmod b$).

Proof (Existence): Consider the set of non-negative integers of the form $a - b k$:

First, we verify that $S$ is non-empty.

• If $a \ge 0$, setting $k = 0$ gives $a - b(0) = a \ge 0 \in S$.

• If $a < 0$, setting $k = a$ gives $a - b a = a(1 - b)$. Since $b \ge 1$, $1 - b \le 0$, so $a(1 - b) \ge 0 \in S$.

Since $S \subseteq \mathbb{Z}_{\ge 0}$ is non-empty, by the Well-Ordering Principle, $S$ has a smallest element, which we denote by $r \ge 0$. Since $r \in S$, there exists some $q \in \mathbb{Z}$ such that:

We must now show that $r < b$. Suppose for contradiction that $r \ge b$. Then consider the integer:

Since $r \ge b$, $r' \ge 0$, so $r' \in S$. But $b > 0 \implies r' = r - b < r$, which contradicts the minimality of $r$ in $S$! Thus, $0 \le r < b$.

Proof (Uniqueness): Suppose there exist two representations:

with $0 \le r_1 < b$ and $0 \le r_2 < b$. Equating the two expressions:

Taking absolute values:

Since $0 \le r_1 < b$ and $0 \le r_2 < b$, we have $-b < r_2 - r_1 < b$, which implies:

Thus:

Since $|q_1 - q_2|$ is a non-negative integer, we must have $|q_1 - q_2| = 0$, so $q_1 = q_2$. Consequently, $r_2 - r_1 = b(0) = 0 \implies r_1 = r_2$. $\blacksquare$

1. The Greatest Common Divisor

Definition 1.2 (Greatest Common Divisor): Let $a, b \in \mathbb{Z}$, not both zero. The greatest common divisor of $a$ and $b$, denoted $\gcd(a, b)$ or simply $(a, b)$, is the unique positive integer $d \in \mathbb{N}$ satisfying:

1. Common divisor: $d \mid a$ and $d \mid b$.

2. Greatest property: If $c \in \mathbb{Z}$ is any common divisor of $a$ and $b$ ($c \mid a$ and $c \mid b$), then $c \le d$ (and $c \mid d$).

If $\gcd(a, b) = 1$, the integers $a$ and $b$ are called relatively prime (or coprime).

2. Bézout's Identity

Theorem 1.3 (Bézout's Identity, 1730–1783): Let $a, b \in \mathbb{Z}$, not both zero. Then their greatest common divisor $d = \gcd(a, b)$ can be expressed as a linear combination of $a$ and $b$:

In fact, $\gcd(a, b)$ is the smallest positive integer in the set of all integer linear combinations:

Proof: Consider the set of all positive linear combinations:

Since not both $a, b$ are zero, $a^2 + b^2 = a(a) + b(b) > 0 \in S$, so $S$ is non-empty. By the Well-Ordering Principle, $S$ contains a smallest element $d = a x + b y > 0$. We claim that $d = \gcd(a, b)$.

1. Show $d \mid a$:

By the Division Algorithm, divide $a$ by $d$:

Substitute $d = ax + by$:

Thus, $r$ is an integer linear combination of $a$ and $b$. If $r > 0$, then $r \in S$ and $r < d$, contradicting the minimality of $d$ in $S$! Therefore, we must have $r = 0$, which proves $d \mid a$.

2. Show $d \mid b$:

An identical argument shows that $d \mid b$.

3. Show $d$ is greatest:

Let $c$ be any common divisor of $a$ and $b$ ($c \mid a$ and $c \mid b$). By linearity of divisibility (Theorem 1.1), $c \mid (a x + b y) = d$. Since $d > 0$, this implies $c \le |c| \le d$. Hence, $d = \gcd(a, b) = a x + b y$. $\blacksquare$

Corollary 1.1 (Coprimality Criterion): Two integers $a$ and $b$ are coprime ($\gcd(a, b) = 1$) if and only if there exist integers $x, y \in \mathbb{Z}$ such that:

3. The Euclidean Algorithm

The Euclidean algorithm is an ancient, highly efficient iterative method for computing $\gcd(a, b)$ and the Bézout coefficients $(x, y)$.

Lemma 1.1 (Euclidean Invariance): If $a = b q + r$, then:

Proof: Let $d_1 = \gcd(a, b)$ and $d_2 = \gcd(b, r)$. Since $d_1 \mid a$ and $d_1 \mid b$, we have $d_1 \mid (a - b q) = r$, so $d_1$ is a common divisor of $b$ and $r \implies d_1 \mid d_2$. Conversely, since $d_2 \mid b$ and $d_2 \mid r$, we have $d_2 \mid (b q + r) = a$, so $d_2$ is a common divisor of $a$ and $b \implies d_2 \mid d_1$. Since both $d_1, d_2 > 0$, we conclude $d_1 = d_2$. $\blacksquare$

By repeatedly applying the Division Algorithm:

Since $b > r_1 > r_2 > \dots \ge 0$ is a strictly decreasing sequence of non-negative integers, the process must terminate in a finite number of steps with remainder $0$. The last non-zero remainder $r_k$ is precisely $\gcd(a, b)$! Back-substituting through the steps yields the Bézout coefficients $x, y$ (Extended Euclidean Algorithm).

1. Formulation of the Problem

A Diophantine equation is an algebraic equation in which integer solutions are sought. The simplest Diophantine equation is the linear equation in two unknowns:

where $a, b, c \in \mathbb{Z}$ are given integer constants, with $a, b$ not both zero.

2. The Solvability Criterion

Theorem 1.4 (Solvability of $a x + b y = c$): The linear Diophantine equation $a x + b y = c$ has an integer solution $(x, y) \in \mathbb{Z}^2$ if and only if:

Proof: Forward direction ($\implies$): Suppose an integer solution $(x_0, y_0)$ exists, so that $a x_0 + b y_0 = c$. Let $d = \gcd(a, b)$. By definition, $d \mid a$ and $d \mid b$. By linearity of divisibility, $d \mid (a x_0 + b y_0)$, which means $d \mid c$.

Reverse direction ($\impliedby$): Suppose $d \mid c$. Then $c = d \cdot k$ for some integer $k \in \mathbb{Z}$. By Bézout's Identity (Theorem 1.3), there exist integers $u, v \in \mathbb{Z}$ such that:

Multiplying both sides by $k$:

Setting $x_0 = u k$ and $y_0 = v k$ gives an explicit integer solution $(x_0, y_0)$. $\blacksquare$

3. Complete Solution Family

Theorem 1.5 (General Solution Family): If $d = \gcd(a, b) \mid c$ and $(x_0, y_0)$ is any particular integer solution to $a x + b y = c$, then all integer solutions are given parametrically by:

Proof: First, verify that every pair $(x, y)$ of this form is a solution:

Conversely, let $(x, y)$ be any arbitrary solution, so $a x + b y = c$. Subtracting $a x_0 + b y_0 = c$ gives:

Dividing through by $d = \gcd(a, b)$:

Note that $\gcd\left(\frac{a}{d}, \frac{b}{d}\right) = 1$. Therefore, $\frac{b}{d} \mid \left(\frac{a}{d}\right)(x - x_0)$. By Euclid's Lemma (Theorem 1.6), since $\gcd\left(\frac{a}{d}, \frac{b}{d}\right) = 1$, we must have:

Substituting this back:

Thus:

1. Definition of Prime and Composite Numbers

Definition 1.3 (Prime and Composite Integers): An integer $p > 1$ is called a prime number if its only positive divisors are $1$ and $p$. An integer $n > 1$ that is not prime is called a composite number. The number $1$ is considered neither prime nor composite (it is a unit).

2. Euclid's Lemma

Theorem 1.6 (Euclid's Lemma): If $p$ is a prime number and $p \mid a b$, then $p \mid a$ or $p \mid b$.

Proof: Suppose $p \mid a b$ and $p \nmid a$. Since $p$ is prime, its only positive divisors are $1$ and $p$. Because $p \nmid a$, the greatest common divisor $\gcd(a, p)$ must be $1$. By Bézout's Identity (Theorem 1.3), there exist integers $x, y \in \mathbb{Z}$ such that:

Multiply this equation across by $b$:

Since $p \mid a b$, there exists an integer $k$ such that $a b = p k$. Substituting this in:

Since $k x + b y \in \mathbb{Z}$, this directly shows that $p \mid b$. $\blacksquare$

Corollary 1.2 (Generalization to Finite Products): If a prime $p$ divides a product of integers $a_1 a_2 \cdots a_k$, then $p \mid a_i$ for at least one index $i \in \{1, 2, \dots, k\}$. In particular, if $p \mid q_1 q_2 \cdots q_k$ where all $q_i$ are primes, then $p = q_i$ for some $i$.

3. Euclid's Proof of the Infinitude of Primes

Theorem 1.7 (Euclid, Book IX, Proposition 20): There are infinitely many prime numbers.

Proof: Suppose for contradiction that there are only finitely many prime numbers, which can be enumerated completely as:

Consider the integer:

Since $N > 1$, $N$ must possess at least one prime factor $q$ (by the Well-Ordering Principle, the smallest divisor of $N$ greater than $1$ is prime). Since $p_1, \dots, p_k$ is the list of all primes, $q$ must be equal to $p_i$ for some $1 \le i \le k$. Consequently, $q \mid (p_1 p_2 \cdots p_k)$. But by definition, $q \mid N = (p_1 p_2 \cdots p_k + 1)$. By linearity of divisibility:

But the only positive divisor of $1$ is $1$, so $q = 1$, which contradicts the fact that $q$ is a prime ($q > 1$)! Thus, the collection of primes cannot be finite. $\blacksquare$

1. Statement of the Fundamental Theorem of Arithmetic

The Fundamental Theorem of Arithmetic (Unique Factorization Theorem) states that every integer greater than $1$ can be represented uniquely as a product of prime numbers.

Theorem 1.8 (The Fundamental Theorem of Arithmetic): Every integer $n > 1$ can be represented as a product of prime numbers:

Furthermore, this factorization is unique up to the order of the prime factors.

2. Line-by-Line Mathematical Proof

Proof of Existence (by Strong Mathematical Induction): Base case ($n = 2$): $2$ is prime, so it is a product of a single prime. Inductive hypothesis: Assume every integer $k$ with $2 \le k < n$ can be factored into a product of primes. Inductive step for $n$:

• If $n$ is prime, we are done.

• If $n$ is composite, there exist integers $a, b$ such that $n = a b$ with $1 < a < n$ and $1 < b < n$.

By the inductive hypothesis, both $a$ and $b$ can be factored into primes:

Multiplying them gives:

which is a prime factorization of $n$. This proves existence for all $n \ge 2$.

Proof of Uniqueness: Suppose for contradiction that there exists at least one integer greater than $1$ that possesses two distinct prime factorizations. By the Well-Ordering Principle, let $m$ be the smallest such integer:

where all $p_i$ and $q_j$ are primes. Clearly, $p_1 \mid (p_1 p_2 \cdots p_r) = m$, so:

By Corollary 1.2 (Euclid's Lemma), $p_1$ must divide some $q_j$. Since $q_j$ is prime, its only divisors are $1$ and $q_j$, so:

Relabeling indices if necessary, let $p_1 = q_1$. Dividing both sides of the factorization of $m$ by $p_1 = q_1$:

If $r = 1$, then $m = p_1 = q_1 \cdots q_s$, which forces $s = 1$ and $p_1 = q_1$, so the factorizations were identical. If $r > 1$, then $m' < m$. But $m'$ now has two distinct prime factorizations! This directly contradicts the minimality of $m$. Therefore, every integer $n > 1$ has a strictly unique prime factorization. $\blacksquare$

3. Canonical Form and Divisor Formulas

Collecting identical primes together, every integer $n > 1$ has a unique canonical representation:

For two integers $a = \prod p_i^{\alpha_i}$ and $b = \prod p_i^{\beta_i}$:

Since $\min(\alpha, \beta) + \max(\alpha, \beta) = \alpha + \beta$, this yields the classical relation: