Proof by Contradiction Math Example 2

Follow the full solution, then compare it with the other examples linked below.

Example 2

medium
Prove by contradiction that there are infinitely many prime numbers.

Solution

  1. 1
    Assume for contradiction that there are only finitely many primes: p1,p2,…,pnp_1, p_2, \ldots, p_n.
  2. 2
    Consider N=p1⋅p2⋯pn+1N = p_1 \cdot p_2 \cdots p_n + 1.
  3. 3
    For each pip_i, dividing NN by pip_i leaves remainder 1, so no pip_i divides NN.
  4. 4
    But N>1N > 1, so NN must have a prime factor not in our list. This contradicts the assumption that all primes were listed.

Answer

There are infinitely many primes.\text{There are infinitely many primes.}
This is Euclid's classic proof. By constructing a number that no listed prime can divide, we force the existence of an unlisted prime, contradicting the finiteness assumption.

About Proof by Contradiction

Proof by contradiction (reductio ad absurdum) assumes the negation of what you want to prove, then derives a logical contradiction, thereby establishing that the original statement must be true.

Learn more about Proof by Contradiction →

More Proof by Contradiction Examples

Example 1 medium

Prove by contradiction that [formula] is irrational.

Example 3 hard

Prove by contradiction: There is no largest integer.

Example 4 medium

Prove by contradiction that there is no smallest positive rational number.

← All Proof by Contradiction Examples Proof by Contradiction Concept