Euclid: there are infinitely many primes
Need a hint?
Suppose the list were finite, multiply all the primes together and add 1. What can divide that number?
If pāā¦pā were all the primes, then pāĀ·ā¦Ā·pā + 1 would have a prime factor outside the list, which is impossible. (Euclid, about 300 BC.)
How to work it out
Suppose there were only finitely many primes . Form the number
(1)Dividing by any leaves remainder 1, so no prime on the list divides . But every number larger than 1 has a prime divisor, so has a prime factor that is not on the list. That contradicts the assumption.
Example: . The number itself need not be prime, but its prime factors 59 and 509 are new.
LaTeX source of the formulas on this page
\[ \text{There are infinitely many primes} \]
\[ N=p_1p_2\cdots p_k+1 \]Questions
What is the answer to: Euclid: there are infinitely many primes?
If pāā¦pā were all the primes, then pāĀ·ā¦Ā·pā + 1 would have a prime factor outside the list, which is impossible. (Euclid, about 300 BC.)
What is the key idea?
The product plus one leaves remainder 1 on division by every prime in the list.
Is there a hint?
Suppose the list were finite, multiply all the primes together and add 1. What can divide that number?