Prime numbers and the fundamental theorem of arithmetic

Summary

This lesson studies the prime numbers, the atoms of the multiplication of the natural numbers. It proves that every natural number greater than $1$ has a prime divisor, presents the sieve of Eratosthenes and the reason why it suffices to sieve up to the square root, and proves with Euclid that the primes are infinitely many. It then proves Euclid’s lemma, according to which a prime that divides a product divides one of its factors, and with it the fundamental theorem of arithmetic: every natural number greater than $1$ can be written as a product of primes in exactly one way. From the factorization one derives the number of divisors of a natural number, the characterization of the perfect squares and the irrationality of the square root of every natural number that is not a perfect square.

Learning objectives

Distinguish the prime numbers from the composite ones and prove that every natural number greater than $1$ has a prime divisor.
Apply the sieve of Eratosthenes and justify why it suffices to cross out the multiples of the primes not greater than the square root of the bound.
Prove the infinitude of the primes, Euclid’s lemma, and the existence and uniqueness of the factorization into primes.
Use the factorization to count and list divisors, recognize perfect squares and prove the irrationality of square roots.

Prime numbers and composite numbers

In the lesson on divisibility and division with remainder we saw that every natural number $n$ is divisible by $1$ and by itself. Some natural numbers admit no divisors other than those two; they are the pieces from which, by multiplication, all the others are built.

Definition (prime number). A natural number $p$ is prime if $p > 1$ and its only divisors are $1$ and $p$ . A natural number $n > 1$ that is not prime is called composite: it can be written as $n = ab$ , with $1 < a < n$ and $1 < b < n$ . The number $1$ is neither prime nor composite.

The primes less than $50$ are the following fifteen:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

The number $2$ is the only even prime, because every other even number has the divisor $2$ , which is different from $1$ and from the number itself. The exclusion of $1$ is not a whim of the definition: if $1$ were prime, the factorization into primes would no longer be unique, because $6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3$ , and the central theorem of this lesson would have to be stated with an exception.

The well-ordering principle

The proofs of this lesson rest on a form of the principle of induction that is especially convenient for reasoning about divisors: the well-ordering principle, according to which every nonempty set of natural numbers has a least element. It was derived from strong induction in the lesson on summations, progressions and induction, and here it is used without repeating its proof.

Every natural number greater than 1 has a prime divisor

The first result of the lesson ensures that no natural number greater than $1$ escapes the primes: there is always one that divides it, and it is found among the smallest divisors.

PropositionThe least divisor greater than 1 is prime

Every natural number $n > 1$ has a prime divisor: the least divisor of $n$ greater than $1$ is prime. If, moreover, $n$ is composite, its least prime divisor $p$ satisfies $p^2 \leq n$ . The figure marks on the line the divisors of $n = 91 = 7 \cdot 13$ .

Proof

$\dato{D}{D = \{ d \in \mathbb{N} : d \mid n \wedge d > 1 \}}, \quad n \in D, \quad m = \min D$
The set of the divisors of $n$ greater than $1$ is not empty, because it contains $n$ itself; by the well-ordering principle, it has a least element $m$ .
$a \mid m \wedge m \mid n \rightarrow \resaltar{a \in D}, \quad \resaltar{a < m}$
If $m$ were composite, $m = ab$ with $1 < a < m$ , the factor $a$ would divide $m$ and, by the transitivity of divisibility, $n$ : it would be an element of $D$ less than $m$ , contrary to the choice of $m$ . Therefore, $m$ is prime.
$\dato{k}{n = pk, \quad k \in D}$
Now let $n$ be composite, and let $p$ be its least prime divisor, which is the least element of $D$ . We write $n = pk$ ; since $n$ is not prime, $k \neq 1$ , and $k$ also divides $n$ .
$p^2 = p \cdot p \leq \resaltar{p \cdot k} = n$
By the minimality of $p$ , we have $k \geq p$ , and the monotonicity of multiplication gives the bound.

Therefore, to decide whether a natural number $n$ is prime it suffices to test the primes $p$ with $p^2 \leq n$ : if none of them divides it, $n$ is prime. For example, for $221$ it suffices to test the primes up to $13$ , because $17^2 = 289 > 221$ : it is not divisible by $2$ , $3$ , $5$ , $7$ or $11$ , but it is divisible by $13$ , and $221 = 13 \cdot 17$ . On the other hand, $211$ is not divisible by any of the primes $2$ , $3$ , $5$ , $7$ , $11$ and $13$ , and since $17^2 = 289 > 211$ , the number $211$ is prime.

In the rest of this lesson

The sieve of Eratosthenes
The primes are infinitely many
Euclid’s lemma
The fundamental theorem of arithmetic
Consequences of the factorization
The divisors of a natural number
Perfect squares
Irrational square roots
Solved problems
A weak cryptographic key
The least natural number with twelve divisors
One hundred consecutive composite numbers
Infinitely many primes that leave remainder 3 when divided by 4
Euclid’s perfect numbers
Proposed problems
Primes of the form $n^4 + 4$
The doors of a corridor
A common divisor of the squares of the primes
A double square and a triple cube
The Mersenne primes