Why primes are the atoms of the integers: what the Fundamental Theorem of Arithmetic really says

Unique prime factorization is not as obvious as it seems. Through a counterexample in Z[sqrt(-5)], we witness uniqueness break down, then prove both the existence and uniqueness parts of the Fundamental Theorem, and survey the Sieve of Eratosthenes and the linear sieve.

Folio Official

March 1, 2026

"Every positive integer can be written as a product of primes, and that factorization is unique." This is the Fundamental Theorem of Arithmetic, the bedrock on which all of number theory is built. But this "obvious" fact rests on a deep structural reason– one that becomes visible only when we examine a number system where uniqueness fails.

1 The definition of a prime

Definition 1 (Prime number).

An integer

p \geq 2

is prime if its only positive divisors are

1

and

p

itself. An integer

\geq 2

that is not prime is called composite.

Remark 2.

Primes are the atoms of the integers. Just as molecules decompose into atoms in chemistry, integers decompose into primes. Unlike chemical atoms, however, there are infinitely many primes.

Theorem 3 (Infinitude of primes (Euclid)).

There are infinitely many primes.

Proof.

Suppose there are only finitely many primes

p_{1}, p_{2}, \dots, p_{k}

. Set

N = p_{1} p_{2} \dots p_{k} + 1

. Then

N

is not divisible by any

p_{i}

(dividing by

p_{i}

leaves remainder

1

). Yet

N \geq 2

, so

N

has a prime factor. This contradicts the assumption. □

2 The Fundamental Theorem of Arithmetic: existence

Theorem 4 (Fundamental Theorem of Arithmetic).

Every integer

n \geq 2

can be written as

n = p_{1}^{e_{1}} p_{2}^{e_{2}} \dots p_{k}^{e_{k}} (p_{1} < p_{2} < \dots < p_{k}, e_{i} \geq 1),

and this representation is unique up to the order of the factors.

We prove existence and uniqueness separately.

Proof.

We use strong induction on

n

. The base case

n = 2

holds because

2

is itself prime. For

n > 2

: if

n

is prime, it is its own prime factorization. If

n

is composite, write

n = ab

with

1 < a, b < n

. By the inductive hypothesis, both

a

and

b

have prime factorizations, and their product is a prime factorization of

n

. □

3 The uniqueness proof: this is where the substance lies

The proof of uniqueness hinges on the following lemma.

Theorem 5 (Euclid's lemma).

p

is prime and

p ∣ ab

, then

p ∣ a

p ∣ b

Proof.

Suppose

p ∤ a

. Since

p

is prime,

g cd (p, a) = 1

. By Bé

x, y

with

p x + a y = 1

. Multiplying both sides by

b

gives

p b x + ab y = b

. Now

p ∣ ab

implies

p ∣ ab y

, and clearly

p ∣ p b x

, so

p ∣ b

. □

Remark 6.

Euclid's lemma depends on Bé

Proof.

Suppose

n = p_{1} p_{2} \dots p_{s} = q_{1} q_{2} \dots q_{t}

. Since

p_{1} ∣ q_{1} q_{2} \dots q_{t}

, repeated application of Euclid's lemma gives

p_{1} ∣ q_{j}

for some

j

. Because

q_{j}

is prime,

p_{1} = q_{j}

. Cancel

p_{1}

from both sides and apply induction. □

4 A world where uniqueness fails: $Z [- 5]$

Uniqueness is not automatic. Consider the following example.

Example 7 (Failure of unique factorization in

Z [- 5]

In the ring

Z [- 5] = {a + b - 5 ∣ a, b \in Z}

, the integer

6

admits two genuinely different factorizations:

6 = 2 \times 3 = (1 + - 5) (1 - - 5) .

Remark 8.

Each of

2

3

1 + - 5

, and

1 - - 5

is irreducible in

Z [- 5]

(it cannot be factored further). This can be verified using the norm

N (a + b - 5) = a^{2} + 5 b^{2}

, which is multiplicative:

N (α β) = N (α) N (β)

. Since

N (2) = 4

, any nontrivial factorization

2 = α β

would require

4 = N (α) N (β)

with

N (α), N (β) > 1

. But

a^{2} + 5 b^{2} = 2

has no integer solutions, so no element of norm

2

exists. A similar argument applies to

3

Remark 9.

The root cause is that Euclid's lemma fails in

Z [- 5]

2 ∣ (1 + - 5) (1 - - 5) = 6

, yet

2 ∤ (1 + - 5)

and

2 ∤ (1 - - 5)

. In a ring where the Euclidean algorithm is unavailable, Bé

5 The Sieve of Eratosthenes

The classical algorithm for enumerating primes up to $N$ .

Theorem 10 (Sieve of Eratosthenes).

All primes up to

N

can be listed in

O (N lo g lo g N)

time.

Remark 11.

The algorithm is beautifully simple: starting from

2

, whenever an unmarked number is found, it is declared prime and all of its multiples are struck off. It suffices to process primes up to

N

(every composite

\leq N

has a prime factor

\leq N

). The running time follows from

\sum_{p \leq N} N / p \approx N ln ln N

(Mertens' theorem).

6 The linear sieve: striking each composite exactly once

Remark 12 (Linear sieve).

In the Sieve of Eratosthenes, a composite number may be struck off multiple times (for instance,

12

is hit as a multiple of both

2

and

3

). The linear sieve eliminates this redundancy by crossing off each composite through its smallest prime factor exactly once, achieving

O (N)

running time. As a bonus, it records the smallest prime factor of each number, enabling

O (lo g n)

factorization of any integer up to

N

7 Takeaway

Primes are the atoms of the integers, and there are infinitely many of them.
The Fundamental Theorem of Arithmetic asserts both the existence and the uniqueness of prime factorization.
Uniqueness depends on Euclid's lemma, which in turn depends on Bé
In $Z [- 5]$ , Euclid's lemma fails and unique factorization breaks down.
The Sieve of Eratosthenes runs in $O (N lo g lo g N)$ ; the linear sieve achieves $O (N)$ .

In the next article, we explore the "symmetry" of the world modulo a prime – Fermat's little theorem.

Number Theory Mathematics Between the Lines

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Why primes are the atoms of the integers: what the Fundamental Theorem of Arithmetic really says

Folio Official

March 1, 2026

1 The definition of a prime

Definition 1 (Prime number).

An integer

p \geq 2

is prime if its only positive divisors are

1

and

p

itself. An integer

\geq 2

that is not prime is called composite.

Remark 2.

Primes are the atoms of the integers. Just as molecules decompose into atoms in chemistry, integers decompose into primes. Unlike chemical atoms, however, there are infinitely many primes.

Theorem 3 (Infinitude of primes (Euclid)).

There are infinitely many primes.

Proof.

Suppose there are only finitely many primes

p_{1}, p_{2}, \dots, p_{k}

. Set

N = p_{1} p_{2} \dots p_{k} + 1

. Then

N

is not divisible by any

p_{i}

(dividing by

p_{i}

leaves remainder

1

). Yet

N \geq 2

, so

N

has a prime factor. This contradicts the assumption. □

2 The Fundamental Theorem of Arithmetic: existence

Theorem 4 (Fundamental Theorem of Arithmetic).

Every integer

n \geq 2

can be written as

n = p_{1}^{e_{1}} p_{2}^{e_{2}} \dots p_{k}^{e_{k}} (p_{1} < p_{2} < \dots < p_{k}, e_{i} \geq 1),

and this representation is unique up to the order of the factors.

We prove existence and uniqueness separately.

Proof.

We use strong induction on

n

. The base case

n = 2

holds because

2

is itself prime. For

n > 2

: if

n

is prime, it is its own prime factorization. If

n

is composite, write

n = ab

with

1 < a, b < n

. By the inductive hypothesis, both

a

and

b

have prime factorizations, and their product is a prime factorization of

n

. □

3 The uniqueness proof: this is where the substance lies

The proof of uniqueness hinges on the following lemma.

Theorem 5 (Euclid's lemma).

p

is prime and

p ∣ ab

, then

p ∣ a

p ∣ b

Proof.

Suppose

p ∤ a

. Since

p

is prime,

g cd (p, a) = 1

. By Bé

x, y

with

p x + a y = 1

. Multiplying both sides by

b

gives

p b x + ab y = b

. Now

p ∣ ab

implies

p ∣ ab y

, and clearly

p ∣ p b x

, so

p ∣ b

. □

Remark 6.

Euclid's lemma depends on Bé

Proof.

Suppose

n = p_{1} p_{2} \dots p_{s} = q_{1} q_{2} \dots q_{t}

. Since

p_{1} ∣ q_{1} q_{2} \dots q_{t}

, repeated application of Euclid's lemma gives

p_{1} ∣ q_{j}

for some

j

. Because

q_{j}

is prime,

p_{1} = q_{j}

. Cancel

p_{1}

from both sides and apply induction. □

4 A world where uniqueness fails: $Z [- 5]$

Uniqueness is not automatic. Consider the following example.

Example 7 (Failure of unique factorization in

Z [- 5]

In the ring

Z [- 5] = {a + b - 5 ∣ a, b \in Z}

, the integer

6

admits two genuinely different factorizations:

6 = 2 \times 3 = (1 + - 5) (1 - - 5) .

Remark 8.

Each of

2

3

1 + - 5

, and

1 - - 5

is irreducible in

Z [- 5]

(it cannot be factored further). This can be verified using the norm

N (a + b - 5) = a^{2} + 5 b^{2}

, which is multiplicative:

N (α β) = N (α) N (β)

. Since

N (2) = 4

, any nontrivial factorization

2 = α β

would require

4 = N (α) N (β)

with

N (α), N (β) > 1

. But

a^{2} + 5 b^{2} = 2

has no integer solutions, so no element of norm

2

exists. A similar argument applies to

3

Remark 9.

The root cause is that Euclid's lemma fails in

Z [- 5]

2 ∣ (1 + - 5) (1 - - 5) = 6

, yet

2 ∤ (1 + - 5)

and

2 ∤ (1 - - 5)

. In a ring where the Euclidean algorithm is unavailable, Bé

5 The Sieve of Eratosthenes

The classical algorithm for enumerating primes up to $N$ .

Theorem 10 (Sieve of Eratosthenes).

All primes up to

N

can be listed in

O (N lo g lo g N)

time.

Remark 11.

The algorithm is beautifully simple: starting from

2

, whenever an unmarked number is found, it is declared prime and all of its multiples are struck off. It suffices to process primes up to

N

(every composite

\leq N

has a prime factor

\leq N

). The running time follows from

\sum_{p \leq N} N / p \approx N ln ln N

(Mertens' theorem).

6 The linear sieve: striking each composite exactly once

Remark 12 (Linear sieve).

In the Sieve of Eratosthenes, a composite number may be struck off multiple times (for instance,

12

is hit as a multiple of both

2

and

3

). The linear sieve eliminates this redundancy by crossing off each composite through its smallest prime factor exactly once, achieving

O (N)

running time. As a bonus, it records the smallest prime factor of each number, enabling

O (lo g n)

factorization of any integer up to

N

7 Takeaway

Primes are the atoms of the integers, and there are infinitely many of them.
The Fundamental Theorem of Arithmetic asserts both the existence and the uniqueness of prime factorization.
Uniqueness depends on Euclid's lemma, which in turn depends on Bé
In $Z [- 5]$ , Euclid's lemma fails and unique factorization breaks down.
The Sieve of Eratosthenes runs in $O (N lo g lo g N)$ ; the linear sieve achieves $O (N)$ .

In the next article, we explore the "symmetry" of the world modulo a prime – Fermat's little theorem.

Number Theory Mathematics Between the Lines

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Why primes are the atoms of the integers: what the Fundamental Theorem of Arithmetic really says

1 The definition of a prime

2 The Fundamental Theorem of Arithmetic: existence

3 The uniqueness proof: this is where the substance lies

4 A world where uniqueness fails: $Z [- 5]$

5 The Sieve of Eratosthenes

6 The linear sieve: striking each composite exactly once

7 Takeaway

Share your expertise with the world

More from Folio Official

The Chinese Remainder Theorem: why simultaneous congruences can be merged

What does it mean to "divide evenly"? Why number theory begins with mod

Why the Euclidean algorithm finds the greatest common divisor: from subtraction to division

Number theory meets cryptography: why RSA works and what makes it secure

Why primes are the atoms of the integers: what the Fundamental Theorem of Arithmetic really says

1 The definition of a prime

2 The Fundamental Theorem of Arithmetic: existence

3 The uniqueness proof: this is where the substance lies

4 A world where uniqueness fails: $Z [- 5]$

5 The Sieve of Eratosthenes

6 The linear sieve: striking each composite exactly once

7 Takeaway

Share your expertise with the world

More from Folio Official

The Chinese Remainder Theorem: why simultaneous congruences can be merged

What does it mean to "divide evenly"? Why number theory begins with mod

Why the Euclidean algorithm finds the greatest common divisor: from subtraction to division

Number theory meets cryptography: why RSA works and what makes it secure

1 The definition of a prime

2 The Fundamental Theorem of Arithmetic: existence

3 The uniqueness proof: this is where the substance lies

4 A world where uniqueness fails:Z[−5​]

5 The Sieve of Eratosthenes

6 The linear sieve: striking each composite exactly once

7 Takeaway

Share your expertise with the world

More from Folio Official

The Chinese Remainder Theorem: why simultaneous congruences can be merged

What does it mean to "divide evenly"? Why number theory begins with mod

Why the Euclidean algorithm finds the greatest common divisor: from subtraction to division

Number theory meets cryptography: why RSA works and what makes it secure

1 The definition of a prime

2 The Fundamental Theorem of Arithmetic: existence

3 The uniqueness proof: this is where the substance lies

4 A world where uniqueness fails:Z[−5​]

5 The Sieve of Eratosthenes

6 The linear sieve: striking each composite exactly once

7 Takeaway

Share your expertise with the world

More from Folio Official

The Chinese Remainder Theorem: why simultaneous congruences can be merged

What does it mean to "divide evenly"? Why number theory begins with mod

Why the Euclidean algorithm finds the greatest common divisor: from subtraction to division

Number theory meets cryptography: why RSA works and what makes it secure

4 A world where uniqueness fails: $Z [- 5]$

4 A world where uniqueness fails: $Z [- 5]$