WordGPT

Euclid: there are infinitely many primes

Exercise Ā· Level 3 (Medium)

Prove that the list of prime numbers never ends.

2,Ā 3,Ā 5,Ā 7,Ā 11,Ā 13, …2,\ 3,\ 5,\ 7,\ 11,\ 13,\ \ldots

wordgptpro.com

Solution

  1. Suppose there were only finitely many primes p1,…,pkp_1,\dots,p_k. Form the number

    N=p1p2⋯pk+1N=p_1p_2\cdots p_k+1
    (1)
  2. Dividing NN by any pip_i leaves remainder 1, so no prime on the list divides NN. But every number larger than 1 has a prime divisor, so NN has a prime factor that is not on the list. That contradicts the assumption.

  3. Example: 2ā‹…3ā‹…5ā‹…7ā‹…11ā‹…13+1=30031=59ā‹…5092\cdot3\cdot5\cdot7\cdot11\cdot13+1=30031=59\cdot509. The number itself need not be prime, but its prime factors 59 and 509 are new.

AnswerThereĀ areĀ infinitelyĀ manyĀ primes\text{There are infinitely many primes}

wordgptpro.com

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

  1. Suppose there were only finitely many primes p1,…,pkp_1,\dots,p_k. Form the number

    N=p1p2⋯pk+1N=p_1p_2\cdots p_k+1
    (1)
  2. Dividing NN by any pip_i leaves remainder 1, so no prime on the list divides NN. But every number larger than 1 has a prime divisor, so NN has a prime factor that is not on the list. That contradicts the assumption.

  3. Example: 2ā‹…3ā‹…5ā‹…7ā‹…11ā‹…13+1=30031=59ā‹…5092\cdot3\cdot5\cdot7\cdot11\cdot13+1=30031=59\cdot509. 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?

Related problems

More number theory problems

    Euclid: there are infinitely many primes: answer and solution | WordGPT