Proof That Every Integer Greater Than 1 Is a Product of Primes

The standard statement is that every integer greater than 1 can be expressed as a product of primes. A short proof uses strong induction: when a number is not prime, it can be split into smaller positive factors, and the induction hypothesis factors those smaller numbers.

This proves that a prime factorization exists. It does not prove that the factorization is unique; uniqueness is a separate part of the fundamental theorem of arithmetic.

Proof by strong induction

Recall that a prime is an integer greater than 1 whose only positive divisors are 1 and itself. A composite integer greater than 1 is one that is not prime.

We prove the statement for all integers $n \ge 2$.

Base case: The number 2 is prime, so it is itself a product of primes: it has one factor, 2.

Inductive step: Suppose that every integer from 2 through $n$ can be written as a product of primes. Consider $n+1$.

There are two possibilities:

1. If $n+1$ is prime, it is already a product of primes, with just one factor.

2. If $n+1$ is composite, then there are integers $a$ and $b$ such that

   $n+1=ab,$

   where $1<a<n+1$ and $1<b<n+1$. Since $a$ and $b$ are integers, both are at most $n$. The induction hypothesis therefore says that each is a product of primes. Multiplying those two prime products gives a product of primes equal to $n+1$.

In either case, $n+1$ is a product of primes. Strong induction now proves the claim for every integer $n \ge 2$.

Worked example: factor 360

The proof works by repeatedly splitting composite numbers into smaller factors. For example,

$360=36\cdot 10.$

Both factors are smaller than 360. Split them further:

$36=6\cdot 6=(2\cdot 3)(2\cdot 3), \qquad 10=2\cdot 5.$

Putting the factors together gives

$360=2\cdot 3\cdot 2\cdot 3\cdot 2\cdot 5=2^3\cdot 3^2\cdot 5.$

Every factor at the end is prime. The inductive proof does not require choosing a particular way to split the number; it only needs the fact that a composite number has factors strictly smaller than itself.

Why strong induction is useful here

In ordinary induction, the hypothesis often gives the statement only for $n$ when proving it for $n+1$. That is not enough for this argument: a composite number $n+1$ may split into factors such as 4 and 6, neither of which has to equal $n$.

Strong induction gives a stronger hypothesis: the claim holds for every integer from the base case through $n$. That covers any factors $a$ and $b$ of $n+1$, because each lies between 2 and $n$. Strong induction is equivalent in power to ordinary induction, but it is the natural form for arguments that reduce a number to any smaller cases.

What about 1, zero, and negative integers?

The phrase “every integer” needs a small qualification:

• Positive integers greater than 1: These are the numbers covered by the proof.
• The number 1: It is not prime and is not a product of one or more primes. Under the convention that an empty product equals 1, it can be included as a product with no factors.
• Zero: It cannot be written as a product of primes, since a product of primes is nonzero.
• Negative integers: A negative integer can be written as $-1$ times a product of primes. The factor $-1$ is a unit, not a prime.

Thus, the usual precise version of the lemma is about positive integers greater than 1. Some texts state it for all positive integers by adopting the empty-product convention for 1.

Common mistakes

• Stopping after saying “factor it.” The proof must explain why the factors can be handled: they are positive integers strictly smaller than the number being proved, so the induction hypothesis applies.
• Using only the weak induction hypothesis. Knowing the claim for $n$ alone may not cover both factors of $n+1$. State the strong induction hypothesis clearly.
• Claiming uniqueness from this proof. The argument shows that a prime factorization exists. To prove it is unique up to the order of factors, one also needs a result such as Euclid’s lemma: if a prime divides a product, it divides at least one factor.
• Including 1 as a prime. By the standard definition, a prime is greater than 1. Treating 1 as prime would also undermine the usual uniqueness statement, since arbitrary factors of 1 could be inserted into a factorization.