Exercise · ZW-INFINITUDE-OF-PRIMES-002 · ★☆☆ Basic
State the idea of Euclid's proof by contradiction.
Choose one option.
Show answer
- C. Assume there are finitely many primes and reach a number with a prime outside the list
Explanation
The proof assumes a complete finite list and builds a number that contradicts it. The option about the form 4k+1 describes a different result, not this proof.
Review the concept: Infinitude of primes
The infinitude of primes is Euclid's theorem stating that the set of prime numbers is infinite: given any finite list of primes \(p_1,\dots,p_n\), there is a prime not on it.
\[p\mid p_1p_2\cdots p_n+1\ \Longrightarrow\ p\neq p_i\ \text{for all } i\]
More practice problems: infinitude of primes
- ZW-INFINITUDE-OF-PRIMES-001 Which statement summarizes Euclid's theorem about primes?
- ZW-INFINITUDE-OF-PRIMES-003 What number is constructed in Euclid's proof from the primes 2, 3 and 5?
- ZW-INFINITUDE-OF-PRIMES-004 According to Euclid's argument, what property does N = p_1 p_2 cdots p_n + 1 have with respect to t…
- ZW-INFINITUDE-OF-PRIMES-005 Which statement about the list 2, 3, 5, 7 is correct?
- ZW-INFINITUDE-OF-PRIMES-006 Compute N = 2· 3· 5· 7· 11 + 1 and determine its smallest prime divisor.
- ZW-INFINITUDE-OF-PRIMES-007 What is the remainder of 2· 3· 5· 7· 11· 13 + 1 when divided by 7?
- ZW-INFINITUDE-OF-PRIMES-008 If p_1,dots,p_n are primes and N = p_1cdots p_n + 1, which statement about N is true?
- ZW-INFINITUDE-OF-PRIMES-009 Using the list 2, 3, 5, 7, 11, what is the constructed number and a prime not in the list?