Homework Help

what is the mathematical proof that there are infinitely many primes?

user profile pic

kimsteinberg | (Level 1) Salutatorian

Posted August 22, 2012 at 9:34 PM via web

dislike 2 like

what is the mathematical proof that there are infinitely many primes?

1 Answer | Add Yours

user profile pic

embizze | High School Teacher | (Level 1) Educator Emeritus

Posted August 23, 2012 at 4:51 AM (Answer #1)

dislike 1 like

Here is a proof based on Euclid (this is not the way Euclid proved the theorem):

Prove that there are infinitely many primes.

 

We assume that there are a finite number of primes. Create the following number:

`P=p_1*p_2*...*p_n+1` where `p_i` is a prime number, and n the assumed number of primes. Thus this is the product of every known prime plus 1.

By the fundamental theorem of arithmetic `P` can be written uniquely as the product of primes. But none of the known primes divides `P` as they all leave a remainder of 1. Thus either `P` itself is prime, or there is a new prime that divides `P` .

This contradicts our assumption that there is a finite group of primes; there fore the number of primes is infinite.

 

Sources:

Join to answer this question

Join a community of thousands of dedicated teachers and students.

Join eNotes