Exercise · ZW-INFINITUDE-OF-PRIMES-004 · ★☆☆ Basic
According to Euclid's argument, what property does \(N = p_1 p_2 \cdots p_n + 1\) have with respect to the primes in the list?
Choose one option.
A It leaves remainder 1 when divided by each of them B It equals the sum of the primes C It is always a perfect square D It is divisible by all of them Show answer A. It leaves remainder 1 when divided by each of them← Back to the question
Explanation Dividing \(N\) by any prime in the list leaves remainder 1, so none of them divides it. The option of total divisibility is the opposite of what happens.
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-002 State the idea of Euclid's proof by contradiction.ZW-INFINITUDE-OF-PRIMES-003 What number is constructed in Euclid's proof from the primes 2, 3 and 5?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?