Mathematics I / Primes and the Fundamental Theorem of Arithmetic
Practice question · Put in order

Order the steps of Euclid's proof that there are infinitely many primes.

Hints
  1. A proof by contradiction opens by assuming the opposite of what you want.
  2. The contradiction is not that N is prime, it is that N needs a prime that was not listed.
Show the answer
  1. Assume for contradiction that the primes are just p1, p2, ..., pk
  2. Form N by multiplying all of them together and adding 1
  3. Observe that N leaves remainder 1 on division by each pi
  4. So no pi divides N, yet N has some prime factor
  5. That prime factor is missing from the list, contradicting the assumption
Why

Assume finiteness, build a number that dodges every listed prime, then note it still has SOME prime factor, which must therefore be new. The subtle point is that N need not itself be prime, it only needs a prime factor outside the list.

Read the lesson: Primes and the Fundamental Theorem of Arithmetic →

Practise Primes and the Fundamental Theorem of Arithmetic

The app has 5 more questions on this lesson, and keeps your place in the course. Mathematics I is free to start.

Start Mathematics I free Get it onGoogle Play

More questions on Primes and the Fundamental Theorem of Arithmetic