Practice question · Multiple choice
Euclid proved there are infinitely many primes by assuming a finite list and building N = p₁p₂…pₖ + 1. Why does that one construction settle it?
Hints
- Divide N by any prime on the list. What is the remainder, and why?
- Careful: N need not be prime. 2·3·5·7·11·13 + 1 = 59 × 509.
Show the answer
B. Because N leaves remainder 1 on every prime in the supposedly complete list
Why
Every listed prime leaves remainder 1, so none divides N, and N has some prime factor, which is therefore missing from a list assumed to hold them all. Option 2 is the standard misremembering: N is often composite, and the argument never needed it to be prime.
Practise Proof by Contradiction and Contrapositive
The app has 5 more questions on this lesson, and keeps your place in the course. Mathematics I is free to start.
More questions on Proof by Contradiction and Contrapositive
- Order the steps of the classic proof by contradiction that the square root of 2 is irrational.
- Sort each opening line by the proof technique it belongs to.
- Select every statement that is a CORRECT negation of the one shown beside it.
- Proof by contrapositive and proof by contradiction both begin by assuming a negation. What distinguishes…
- A conditional and its contrapositive always have the same truth value.