Fundamental Theorem of Arithmetics: A proof from first principles

The Fundamental Theorem of Arithmetic:A Proof from Elementary Principles

Michael Emmerich, December 7th, 2024

The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be uniquely represented as a product of prime numbers, apart from the order of the factors. This essay aims to prove the theorem rigorously from elementary principles, i.e., using only the basic concepts of school-level arithmetic. The proof is not new—I have just written it in my own way. It combines parts of Carl Friedrich Gauss’s proof from his doctoral dissertation and the Lemma of Euclid from the 13th Book of Elements and its modern explanations. I hope this essay succeeds in making the proof clear and easy to understand

1. Foundations and Definitions

Definition 1 (Relatively Prime Pair) Two integers ${a}$ and ${b}$ are said to be relatively prime if their greatest common divisor (gcd) is 1, i.e.:
$\displaystyle \gcd(a, b) = 1.$

This means that ${a}$ and ${b}$ do not share any prime factors.

Definition 2 (Prime Number) A prime number is a natural number ${p > 1}$ that has exactly two positive divisors, namely 1 and itself. In other words, ${p}$ is a prime if:
$\displaystyle \forall k \in \mathbb{N}, \; k \mid p \Rightarrow (k = 1 \lor k = p).$

Here, the symbol ${\mid}$ means “divides,” indicating that ${k}$ is a divisor of ${p}$ . For example, ${3 \mid 6}$ means that 3 is a divisor of 6.

Definition 3 (Prime Factorization) A prime factorization of an integer ${n > 1}$ is a representation of ${n}$ as a product of prime numbers:
$\displaystyle n = p_1 \cdot p_2 \cdot \ldots \cdot p_k,$

where ${p_1, p_2, \ldots, p_k}$ are primes. The order of the factors does not matter since multiplication is commutative.

Before we start to go into the details, let us provide an overview of the proof in the following diagram. We will then go through these parts step by step:

2. Proof of Existence

The proof proceeds by a tree-like factorization. Each number ${n > 1}$ is successively factored by dividing it by an arbitrary divisor other than 1 and itself, until only prime numbers remain. This is visualized using the example of the number 420:

In this tree, 420 is successively broken down into factors: first into 10 and 42, then 10 into 5 and 2, while 42 is factored into 21 and 2. Finally, 21 is factored into 7 and 3. Thus, we have:

$\displaystyle 420 = 2 \cdot 2 \cdot 3 \cdot 5 \cdot 7.$

This method shows that any ${n > 1}$ has at least one factorization that can be continued until only prime factors remain.

3. Proof of Uniqueness

The uniqueness proof is straightforward once one understands Euclid’s lemma, which plays a subtle role in the argument.

3.1. Initial Situation

Consider a number ${n}$ that can be represented as a product of prime factors. Suppose there are two possible representations:

$\displaystyle n = q_1 \cdots q_n \quad \text{or} \quad n = p_1 \cdots p_k,$

where all ${q_i}$ and ${p_j}$ are prime numbers. We already know that at least one such representation exists.

3.2. Further Course of the Proof

Now we take one of the factors ${q_i}$ for ${i = 1, \dots, n}$ . By Euclid’s lemma, we know that at least one of the factors ${p_1, \dots, p_k}$ is divisible by ${q_i}$ , say ${p_j}$ .

3.3. Division and Reduction

Let us first define ${n_{0}:=n}$ .

Now we iterate over all ${i :=1, 2, ..., n}$ .

Dividing ${n_{i-1}}$ by ${q_i}$ , we get:

$\displaystyle n_i = \frac{n_{i-1}}{q_i}.$

For the remaining number (after division) ${n_i}$ , there is also a product representation:

$\displaystyle n_i = q_2 \cdots q_n = \frac{p_1 \cdots p_k}{p_j}.$

Each time we lose one factor with equal value in both product representations, since ${p_j = q_i}$ (both are prime factors by definition). Therefore when all iterations have finished we will have shown that the factors of both factorizations are the same.

3.4. Proof of the Auxiliary Lemma

Lemma 4 (Auxiliary Lemma) If ${n}$ is a positive integer, ${n \mid ab}$ , and ${\gcd(a, n) = 1}$ , then ${n \mid b}$ .

Proof:

We prove the lemma by strong induction on the product ${ ab }$ .

Base Case: For ${ a'b' = 1 }$ , the lemma is trivial, since ${ n \mid 1 }$ implies ${ n = 1 }$ .

Inductive Hypothesis: Assume the lemma holds for all products ${ a'b' < N }$ .

Inductive Step: Let ${ ab = N }$ and ${ n \mid ab }$ . We need to show that ${ n \mid b }$ . In other words, since ${ n \mid ab }$ , there exists some ${ q \in \mathbb{N} }$ such that ${ n \cdot q = ab }$ .

We consider three cases:

Case 1: ${ n = a }$ . In this case, ${\gcd(a, n) = 1}$ only if ${ n = 1 }$ . Trivially, ${ n \mid b }$ holds then.

Case 2: ${ n > a }$ . Subtracting ${ a \cdot q }$ from both sides of ${ n \cdot q = a \cdot b }$ , we get:

$\displaystyle (n - a)q = a(b - q).$

Since ${ n }$ is coprime ${ a }$ and ${ n > a }$ , we have ${\gcd(n - a, a) = 1}$ .

(The latter statement holds, because any divisor ${d}$ of both ${n -a}$ and ${n}$ must also divide their sum: ${(n - a) + a = n}$ . Therefore, if ${d}$ divides both ${n - a}$ and ${a}$ , it must also divide ${n}$ .)

The product ${ a(b - q) }$ is smaller than ${ ab }$ because ${ b - q < b }$ . By the induction hypothesis, ${(n-a) \mid (b-q)}$ . Hence, there exists ${ r \in \mathbb{N} }$ such that:

$\displaystyle b - q = r(n - a).$

Substituting ${ b - q = r(n - a) }$ into the reduced equation ${ (n - a)q = a(b - q) }$ , we get:

$\displaystyle (n - a)q = a \cdot r(n - a).$

Since ${ n - a \neq 0 }$ , we can divide by ${ n - a }$ :

$\displaystyle q = a \cdot r.$

Case 3: ${n < a }$ . This case is analogous to Case 2. Subtracting ${ n \cdot b }$ from both sides of ${ n \cdot q = a \cdot b }$ , we have:

$\displaystyle n(q - b) = (a - n)b$

Since ${ n }$ and ${ a }$ are co-prime, ${\gcd(a - n, n) = 1}$ .

(The latter statement holds, because any divisor ${d}$ of both ${a - n}$ and ${n}$ must also divide their sum: ${(a - n) + n = a}$ . Therefore, if ${d}$ divides both ${a - n}$ and ${n}$ , it must also divide ${a}$ .)

Again, ${ n(q - b) < ab }$ . By the induction hypothesis, ${(a - n) \mid n(q - b)}$ . Because ${ a - n }$ and ${ n }$ are relatively prime we can use the induction hypothesis and conclude ${(a - n) \mid (q - b)}$ . Thus, there exists ${ r' \in \mathbb{Z} }$ :

$\displaystyle q - b = r'(a - n).$

Substituting ${ q - b = r'(a - n) }$ into ${(a - n)q = n(q - b)}$ :

$\displaystyle (a - n)q = n \cdot r'(a - n).$

Since ${ a - n \neq 0 }$ , we divide by ${ a - n }$ :

$\displaystyle q = n \cdot r'.$

We have thus found that ${ q }$ is a positive integer.

Conclusion: In all cases, it follows that ${ n \mid b }$ . This completes the proof of the lemma. $\Box$

Lemma 5 (Euclid’s Lemma) Let ${ n }$ be a prime number. If ${ n \mid ab }$ , then ${n \mid a}$ or ${ n \mid b }$ .

Proof: We prove the lemma by case distinction:

Case 1: ${ n \mid a }$

If ${ n \mid a }$ , then from the property of divisibility, ${ n \mid ab }$ is immediately true. In this case, the statement is trivially satisfied, as ${ n \mid b }$ need not be considered.

Case 2: ${ n \nmid a }$

If Case 1 does not apply, then ${ n \nmid a }$ , and also it holds ${ a \nmid n }$ , since ${n}$ is prime.
From this, it follows that ${ a }$ and ${ n }$ are relatively prime, i.e., ${ \gcd(a, n) = 1 }$ .
Since ${ \gcd(a, n) = 1 }$ , by the Auxiliary Lemma we conclude that ${ n \mid b }$ .

$\Box$

4. Consequences and Applications

The Fundamental Theorem of Arithmetic establishes that each integer greater than 1 can be uniquely represented by its set of prime factors. This uniqueness is not merely theoretical: it forms the basis for much of modern number theory, algebra, and cryptography.

One direct consequence is that positive integers can be encoded as “prime vectors.” That is, if we list all prime numbers in ascending order ${p_1 = 2, p_2 = 3, p_3 = 5, \ldots}$ , every positive integer ${n > 1}$ can be represented by a vector of exponents corresponding to these primes:

$\displaystyle n = 2^{a_1} \cdot 3^{a_2} \cdot 5^{a_3} \cdots \implies n \leftrightarrow (a_1, a_2, a_3, \ldots),$

where all but finitely many ${a_i}$ are zero. This idea is explored in, for example, “Playing with Primes” (2024), which discusses the intuition behind such representations and how factoring integers into their prime bases can be seen as mapping them into an infinite-dimensional vector space over the nonnegative integers and replace multiplication by prime vector addition.

The presented proof has many steps, the validity of each one of them should be easy to check by elementary math. But it would be still desirable to find proofs that work without induction and have less steps.

Alternative proves of the fundamental theorem of arithmetics are provided in Dawson (2015). Notably, the proof can be done by simple mathematics without Euclids argument and without Bezout’s theorem which is also often employed for proving FTA. It remains to be seen if even more simple and intuitive proofs can be found.

Gauss, Carl Friedrich (1966) [1801], Groth, Paul; Bressi, Todd W. (eds.), Disquisitiones Arithmeticae, translated by Clarke, Arthur A., New Haven: Yale, doi:10.12987/9780300194258,; Corrected ed. 1986, New York.

Playing with Primes – Michael Emmerich

Euclid (1956), The Thirteen Books of the Elements, vol. 2 (Books III-IX), translated by Heath, Thomas Little, Dover Publications

Dawson Jr, J. W. (2015). Why prove it again?: Alternative proofs in mathematical practice. Birkhäuser.

Fundamental Theorem of Arithmetics: A proof from first principles

Share this:

Leave a comment Cancel reply