Exercise · ZW-INFINITUDE-OF-PRIMES-008 · ★★☆ Intermediate
If \(p_1,\dots,p_n\) are primes and \(N = p_1\cdots p_n + 1\), which statement about \(N\) is true?
Choose one option.
Show answer
- A. \(N\) has some prime divisor not in the list
Explanation
Every prime divisor of \(N\) must lie outside the list, since none of the \(p_i\) divides it. The always-prime option is false, as the case \(2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13+1\) shows.
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-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-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-009 Using the list 2, 3, 5, 7, 11, what is the constructed number and a prime not in the list?