TAOCP 1.2.1 Exercise 5

Let $P(n)$ be the statement: “Every integer $m$ with $2 \le m \le n$ may be written as a product of one or more prime numbers.

taocpmathematicsalgorithmsvolume-1medium

Section 1.2.1: Mathematical Induction

Exercise 5. [21] A prime number is an integer $> 1$ that has no positive integer divisors other than 1 and itself. Using this definition and mathematical induction, prove that every integer $> 1$ may be written as a product of one or more prime numbers. (A prime number is considered to be the “product” of a single prime, namely itself.)

Verified: yes
Solve time: 38s

Let $P(n)$ be the statement:

“Every integer $m$ with $2 \le m \le n$ may be written as a product of one or more prime numbers.”

We will prove $P(n)$ for all integers $n \ge 2$ by mathematical induction.

For the basis step, consider $P(2)$. The only integer $m$ satisfying $2 \le m \le 2$ is $m=2$. Since 2 is prime, it is itself a product consisting of one prime number. Hence $P(2)$ is true.

Now assume that $P(n)$ is true for some integer $n \ge 2$. We must prove $P(n+1)$.

The statement $P(n+1)$ asserts that every integer $m$ with $2 \le m \le n+1$ may be written as a product of one or more primes.

If $2 \le m \le n$, this follows immediately from the inductive hypothesis $P(n)$.

It remains to consider $m=n+1$.

There are two cases.

First, suppose that $n+1$ is prime. Then $n+1$ itself is a product of one prime number, namely $n+1$.

Second, suppose that $n+1$ is not prime. By the definition of prime number, there exist integers $a$ and $b$ such that

$$ n+1=ab, $$

with

$$ 1<a<n+1,\qquad 1<b<n+1. $$

Since $a<n+1$ and $b<n+1$, we have

$$ 2\le a\le n,\qquad 2\le b\le n. $$

By the inductive hypothesis, $a$ may be written as a product of primes, and $b$ may be written as a product of primes. Multiplying these two prime factorizations together yields a representation of $n+1=ab$ as a product of one or more prime numbers.

Thus every integer $m$ with $2 \le m \le n+1$ may be written as a product of one or more prime numbers. Hence $P(n+1)$ is true.

By mathematical induction, $P(n)$ holds for all integers $n \ge 2$. Therefore every integer greater than 1 may be written as a product of one or more prime numbers.

This completes the proof.

∎