Proof by Contradiction: Infinite Primes
Explore Euclid's classic proof that there are infinitely many prime numbers.
Explore Euclid's classic proof that there are infinitely many prime numbers.
Follow a proof by contradiction that begins by assuming there are only finitely many primes and then constructs an impossible consequence.
In a proof by contradiction, we assume the opposite of what we want to prove and show that this assumption leads to an impossibility.
After completing this lesson you should be able to:
Assume, for contradiction, that there are only finitely many primes:
pā, pā, ā¦, pā.
Form the number N = pāpāā¦pā + 1.
Dividing N by any listed prime leaves remainder 1, so none of them divides N.
Therefore, N is prime or has a prime factor not in the list.
This contradicts the assumption that the list contained every prime.
Hence, there are infinitely many prime numbers.
Why can none of the listed primes divide N = pāpāā¦pā + 1?
Ask Mathiation AI to explain any step or help you practise another question from this topic.