Primes and the Fundamental Theorem of Arithmetic — The Atomic Decomposition of Integers

We define prime numbers and establish their basic properties, including Euclid's proof of the infinitude of primes. We then give a rigorous proof of the fundamental theorem of arithmetic (existence and uniqueness of prime factorization), and discuss the sieve of Eratosthenes and the Miller--Rabin primality test.

Folio Official

March 1, 2026

1 Definition and Basic Properties of Primes

Definition 1 (Prime number).

An integer

p \geq 2

is called a prime if its only positive divisors are

1

and

p

itself. An integer

n \geq 2

that is not prime is called composite.

Lemma 2 (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 ∣ p b

and

p ∣ ab

, so

p ∣ (p b x + ab y) = p ∣ b

. □

Corollary 3.

p

is prime and

p ∣ a_{1} a_{2} \dots a_{n}

, then

p ∣ a_{i}

for some

i

2 The Infinitude of Primes

Theorem 4 (Euclid).

There are infinitely many primes.

Proof.

Suppose, for contradiction, that

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

is a complete list of all primes. Set

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

. Since

N \geq 2

, it has at least one prime factor

p

. This

p

must equal some

p_{i}

. But then

p ∣ N

and

p ∣ p_{1} \dots p_{n}

, so

p ∣ (N - p_{1} \dots p_{n}) = p ∣ 1

. This contradicts

p \geq 2

. □

3 The Fundamental Theorem of Arithmetic

Theorem 5 (Fundamental theorem of arithmetic).

Every integer

n \geq 2

can be written as a product of primes (existence). Moreover, this representation is unique up to the ordering of the factors (uniqueness):

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) .

Proof.

Existence. We proceed by strong induction on

n

. The base case

n = 2

holds since

2

is prime. For

n > 2

: if

n

is prime, we are done. If

n

is composite, write

n = ab

with

1 < a, b < n

. By the inductive hypothesis, both

a

and

b

are products of primes, so

n

is as well.

Uniqueness. Suppose

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

with

p_{1} \leq \dots \leq p_{s}

and

q_{1} \leq \dots \leq q_{t}

. We argue by induction on

s

. If

s = 1

, then

n = p_{1}

is prime, forcing

t = 1

and

q_{1} = p_{1}

. For

s \geq 2

: since

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

, Euclid's lemma gives

p_{1} ∣ q_{j}

for some

j

. Since

q_{j}

is also prime,

p_{1} = q_{j}

. Dividing both sides by

p_{1}

yields

p_{2} \dots p_{s} = q_{1} \dots q_{j - 1} q_{j + 1} \dots q_{t}

. By the inductive hypothesis,

s - 1 = t - 1

and the remaining prime factors agree up to reordering. □

4 The Sieve of Eratosthenes

Remark 6.

The sieve of Eratosthenes is a classical method for listing all primes up to

n

. One writes down the integers from

2

n

and, for each prime

p

with

p^{2} \leq n

, strikes out the multiples

p^{2}, p^{2} + p, \dots

. The surviving numbers are precisely the primes. The time complexity is

O (n lo g lo g n)

Theorem 7.

Every composite number

n

has a prime factor at most

n

Proof.

Write

n = ab

with

1 < a \leq b < n

. Then

a^{2} \leq ab = n

, so

a \leq n

. Any prime factor of

a

is at most

a \leq n

. □

5 The Miller–Rabin Primality Test

Definition 8.

For an odd integer

n > 2

, write

n - 1 = 2^{s} d

with

d

odd. An integer

a

with

g cd (a, n) = 1

is called a strong probable prime witness for

n

a^{d} \equiv 1 (mod n)

a^{2^{r} d} \equiv - 1 (mod n)

for some

r \in {0, 1, \dots, s - 1}

Theorem 9.

n

is prime, then every

a

with

g cd (a, n) = 1

is a strong probable prime witness. If

n

is composite, then at most

1/4

of the integers

a

with

1 \leq a \leq n - 1

are strong probable prime witnesses.

Remark 10.

Based on this theorem, testing

k

randomly chosen bases

a

yields a probability of at most

4^{- k}

that a composite number passes as prime. With

k = 20

, this probability falls below

1 0^{- 12}

, which is more than sufficient for practical purposes.

Number Theory Algebra Textbook Primes Fundamental Theorem of Arithmetic

Folio Official

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

1 followers·107 articles

Primes and the Fundamental Theorem of Arithmetic — The Atomic Decomposition of Integers

Folio Official

March 1, 2026

1 Definition and Basic Properties of Primes

Definition 1 (Prime number).

An integer

p \geq 2

is called a prime if its only positive divisors are

1

and

p

itself. An integer

n \geq 2

that is not prime is called composite.

Lemma 2 (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 ∣ p b

and

p ∣ ab

, so

p ∣ (p b x + ab y) = p ∣ b

. □

Corollary 3.

p

is prime and

p ∣ a_{1} a_{2} \dots a_{n}

, then

p ∣ a_{i}

for some

i

2 The Infinitude of Primes

Theorem 4 (Euclid).

There are infinitely many primes.

Proof.

Suppose, for contradiction, that

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

is a complete list of all primes. Set

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

. Since

N \geq 2

, it has at least one prime factor

p

. This

p

must equal some

p_{i}

. But then

p ∣ N

and

p ∣ p_{1} \dots p_{n}

, so

p ∣ (N - p_{1} \dots p_{n}) = p ∣ 1

. This contradicts

p \geq 2

. □

3 The Fundamental Theorem of Arithmetic

Theorem 5 (Fundamental theorem of arithmetic).

Every integer

n \geq 2

can be written as a product of primes (existence). Moreover, this representation is unique up to the ordering of the factors (uniqueness):

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) .

Proof.

Existence. We proceed by strong induction on

n

. The base case

n = 2

holds since

2

is prime. For

n > 2

: if

n

is prime, we are done. If

n

is composite, write

n = ab

with

1 < a, b < n

. By the inductive hypothesis, both

a

and

b

are products of primes, so

n

is as well.

Uniqueness. Suppose

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

with

p_{1} \leq \dots \leq p_{s}

and

q_{1} \leq \dots \leq q_{t}

. We argue by induction on

s

. If

s = 1

, then

n = p_{1}

is prime, forcing

t = 1

and

q_{1} = p_{1}

. For

s \geq 2

: since

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

, Euclid's lemma gives

p_{1} ∣ q_{j}

for some

j

. Since

q_{j}

is also prime,

p_{1} = q_{j}

. Dividing both sides by

p_{1}

yields

p_{2} \dots p_{s} = q_{1} \dots q_{j - 1} q_{j + 1} \dots q_{t}

. By the inductive hypothesis,

s - 1 = t - 1

and the remaining prime factors agree up to reordering. □

4 The Sieve of Eratosthenes

Remark 6.

The sieve of Eratosthenes is a classical method for listing all primes up to

n

. One writes down the integers from

2

n

and, for each prime

p

with

p^{2} \leq n

, strikes out the multiples

p^{2}, p^{2} + p, \dots

. The surviving numbers are precisely the primes. The time complexity is

O (n lo g lo g n)

Theorem 7.

Every composite number

n

has a prime factor at most

n

Proof.

Write

n = ab

with

1 < a \leq b < n

. Then

a^{2} \leq ab = n

, so

a \leq n

. Any prime factor of

a

is at most

a \leq n

. □

5 The Miller–Rabin Primality Test

Definition 8.

For an odd integer

n > 2

, write

n - 1 = 2^{s} d

with

d

odd. An integer

a

with

g cd (a, n) = 1

is called a strong probable prime witness for

n

a^{d} \equiv 1 (mod n)

a^{2^{r} d} \equiv - 1 (mod n)

for some

r \in {0, 1, \dots, s - 1}

Theorem 9.

n

is prime, then every

a

with

g cd (a, n) = 1

is a strong probable prime witness. If

n

is composite, then at most

1/4

of the integers

a

with

1 \leq a \leq n - 1

are strong probable prime witnesses.

Remark 10.

Based on this theorem, testing

k

randomly chosen bases

a

yields a probability of at most

4^{- k}

that a composite number passes as prime. With

k = 20

, this probability falls below

1 0^{- 12}

, which is more than sufficient for practical purposes.

Number Theory Algebra Textbook Primes Fundamental Theorem of Arithmetic

Folio Official

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

1 followers·107 articles

Primes and the Fundamental Theorem of Arithmetic — The Atomic Decomposition of Integers

1 Definition and Basic Properties of Primes

2 The Infinitude of Primes

3 The Fundamental Theorem of Arithmetic

4 The Sieve of Eratosthenes

5 The Miller–Rabin Primality Test

Share your expertise with the world

More from Folio Official

Introduction to Algebraic Integers — Extending the Notion of Integer

Arithmetic Functions and Multiplicative Functions — Functions on the Integers

Chebyshev's Estimates: 0.92 x/ln x < π(x) < 1.11 x/ln x and the Prime Number Theorem

Continued Fractions and Diophantine Approximation — The Theory of Rational Approximation

Primes and the Fundamental Theorem of Arithmetic — The Atomic Decomposition of Integers

1 Definition and Basic Properties of Primes

2 The Infinitude of Primes

3 The Fundamental Theorem of Arithmetic

4 The Sieve of Eratosthenes

5 The Miller–Rabin Primality Test

Share your expertise with the world

More from Folio Official

Introduction to Algebraic Integers — Extending the Notion of Integer

Arithmetic Functions and Multiplicative Functions — Functions on the Integers

Chebyshev's Estimates: 0.92 x/ln x < π(x) < 1.11 x/ln x and the Prime Number Theorem

Continued Fractions and Diophantine Approximation — The Theory of Rational Approximation