How to Use Induction in a Proof About Prime Numbers

The phrase “proof by induction with a prime number” does not specify a single theorem. One standard result that combines induction and primes is the existence part of the fundamental theorem of arithmetic: every integer greater than 1 can be written as a product of primes. The proof uses strong induction, because a composite number can be split into smaller integers.

This proves existence of a prime factorization; it does not by itself prove that the factorization is unique. It also illustrates an important point: induction is usually performed over consecutive integers, not over the prime numbers alone.

The statement to prove

For each integer $n\ge 2$, let $P(n)$ be the statement:

$n$ is a product of one or more prime numbers.

A prime number counts as a product with just one factor. For example, $7$ is the product consisting of the single prime $7$.

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

Proof by strong induction

Base case: $n=2$. The number $2$ is prime, so it is already a product of primes. Thus $P(2)$ holds.

Induction hypothesis. Fix an integer $n\ge 2$ and assume that $P(k)$ holds for every integer $k$ with $2\le k\le n$. In other words, assume every integer from $2$ through $n$ is a product of primes.

Induction step. Consider $n+1$.

• If $n+1$ is prime, it is itself a product of primes, so $P(n+1)$ holds.
• If $n+1$ is composite, then there are integers $a,b$ such that

$$n+1=ab,$$

with $2\le a\le n$ and $2\le b\le n$. The upper bounds follow because each factor is at least $2$, so neither factor can equal or exceed $n+1$. By the induction hypothesis, both $a$ and $b$ can be written as products of primes. Multiplying those two prime products gives a prime product equal to $n+1$. Therefore $P(n+1)$ holds.

In either case, $P(n+1)$ follows from the induction hypothesis. Strong induction now gives $P(n)$ for every integer $n\ge 2$.

Worked example: factoring 12 within the proof

The induction step does not require you to guess a prime factorization of $n+1$ immediately. It is enough to split a composite number into smaller factors.

For $12$, write

$$12=3\cdot 4.$$

Both factors are smaller than $12$ and at least $2$. The induction hypothesis says that each has a prime factorization: $3$ is prime, and $4=2\cdot2$. Combining them gives

$$12=3\cdot2\cdot2.$$

All the factors are prime, as required. The argument works for any composite $n+1$: its factors are smaller, so the induction hypothesis covers them.

Why strong induction is useful here

Ordinary induction assumes only that $P(n)$ is true when proving $P(n+1)$. That is not enough for the factorization argument: a factor of $n+1$ might be much smaller than $n$, rather than equal to $n$. Strong induction lets you use the claim for every smaller integer, which is exactly what the proof needs.

You can also formulate this with ordinary induction by proving a stronger statement or by adjusting the induction step, but strong induction is the direct and clearest method.

Common mistakes

• Inducting only over primes. Prime numbers are not consecutive: for instance, the prime after $3$ is $5$. A usual induction step from one prime to the “next prime” does not automatically cover composite integers in between. If your claim concerns only primes, it may need a different argument or an induction parameter that ranges over all integers.
• Assuming every number is prime. The induction step must handle both cases. If $n+1$ is prime, use it as a one-factor product; if it is composite, split it into smaller factors.
• Using the hypothesis outside its range. In the composite case, verify that each factor lies between $2$ and $n$. This is what makes the induction hypothesis applicable.
• Claiming uniqueness from this proof. The argument shows that a prime factorization exists. To show it is unique up to rearranging the factors, one also needs a result such as Euclid’s lemma: if a prime divides a product, it divides at least one factor.

If the intended claim involves a particular prime—for example, a divisibility statement about powers or factorials—the exact statement matters. Induction may be useful, but the base case and induction step depend on what is being proved.