I have heard that Euclid wrote a proof demonstrating that there are infinite prime numbers. Is it true?

Printable View

- Mar 31st 2005, 08:41 PMYankee77Infinite Primes Proof
I have heard that Euclid wrote a proof demonstrating that there are infinite prime numbers. Is it true?

- Mar 31st 2005, 09:36 PMMatrix
Euclid proved that there are infinitely many prime numbers. This is one of the first proofs known which uses the method of contradiction to establish a result. Euclid also gives a proof of the Fundamental Theorem of Arithmetic: Every integer can be written as a product of primes in an essentially unique way.

- Apr 1st 2005, 08:10 AMArtristeEuclid's infinite primes
Assume there are a finite number, n, of primes, the largest being pn. Consider the number that is the product of these, plus one: N = p1...pn+1. By construction, N is not divisible by any of the pi. Hence it is either prime itself, or divisible by another prime greater than pn, contradicting the assumption.

2 + 1 = 3,**is prime**

2*3 + 1 = 7,**is prime**

2*3*5 + 1 = 31,**is prime**

2*3*5*7 + 1 = 211,**is prime**

2*3*5*7*11 + 1 = 2311,**is prime**

2*3*5*7*11*13 + 1 = 30031 = 59*509

2*3*5*7*11*13*17 + 1 = 510511 = 19*97*277

2*3*5*7*11*13*17*19 + 1 = 9699691 = 347*27953

2*3*5*7*11*13*17*19*23 + 1 = 223092871 = 317*703763

2*3*5*7*11*13*17*19*23*29 + 1 = 6469693231 = 331*571*34231

2*3*5*7*11*13*17*19*23*29*31 + 1 = 200560490131,**is prime**

As you can see Euclids logic does produce primes at first but not always. It is a brilliant peice of logic however it does not prove the infinitude of primes.

-Artriste - Apr 7th 2005, 09:25 PMhpeInifinitely many primes
@ Artriste -

Euclid proved that you can never run out of primes, so there must be infinitely many of them. To be sure, he didn't actually give a formula to produce all possible primes, but that's not necessary to show that there are infinitely many.

:confused:

Challenge - are there infinitely many primes in the arithmetic progression 3, 7, 11, 15, 19, 23, 27, 31, ... ? Why / why not? - Apr 8th 2005, 04:14 AMtheprof
I have heard that Euclid wrote a proof demonstrating that there are infinite prime numbers. Is it true?

Yes it is.

He proved that if you write down all known primes, you can always get a greater one, that is: "prime numbers are infinite."

Proof

Suppose 2,3,5,7,11 are the only primes you know.

You write a bigger number in this way:

N=2x3x5x7x11+1

This number is not a multiple of 2, 3, 5, 7 or 11 because performing division you always have remainder one. Therefore:

a. N is prime itself;

b. N is a multiple of a prime grater than 11.

In both cases you have the proof that exists a prime number grater than the greatest you suppesed to have found, so they are infinite.

bye - Apr 9th 2005, 03:28 PMArtristeI give upQuote:

Originally Posted by**hpe**

- Apr 9th 2005, 09:19 PMtheprofQuote:

Originally Posted by**hpe**

http://mathworld.wolfram.com/DirichletsTheorem.html

bye - Apr 11th 2005, 08:40 AMhpeInifinitely many primes
Hi theprof -

I had an elementary proof in mind for the fact that**yes, there are infinitely many primes in the set {3,7,11,15,...}.**

So, here goes:

Suppose there are only finitely many such primes, say a, b, ..., p, q. They are all of the form 4n+3, that is, they leave a remainder of 3 when divided by 4. The first one is a=3, the last one ... who knows.

Multiply them all together and call the product x, i.e. x = abcd....pq.

Now consider - as an aside - what happens when you multiply two odd numbers together:

If they are both of the form 4n+3, say 4n+3 and 4m+3, the product is (4n+3)(4m+3) = 16mn + 12m + 12n + 9 = 4(4mn + 3m + 3n + 2) + 1. So the product is of the form 4k+1.

If they are both of the form 4n+1, say 4n+1 and 4m+1, the product is (4n+1)(4m+1) = 16mn + 4m + 4n + 1 = 4(4mn + m + n) + 1. So the product is also of the form 4k+1.

If one is of the form 4n+3, and the other of the form 4m+1, the product is (4n+3)(4m+1) = 16mn + 12m + 4n + 3 = 4(4mn + 3m + n) + 3. So in this case the product is of the form 4k+3.

Back to the product x. All factors are of the form 4n+3 with different n, so there are__two cases__:

- If the number of factors is even, then abcd...pq = (ab)(cd)...(pq). Each parenthesis term is of the form 4n+1, so the whole product is of the form 4N+1, with a humongous number N.

- If the number of factors is odd, then abcd...pq = (ab)(cd)...p)q. Each parenthesis term is of the form 4n+1, and there is one extra factor of the form 4n+3. So the the whole product is of the form 4M+3, with a gigantic number M.

**In the first case, consider the value y=x+2.**

This number cannot be evenly divisible by any prime number of the form 4n+3, i.e. by a, b, c, ..., p, q, since it will leave a remainder of 2 when divided by any of them. So all its prime factors must be of the other flavor, namely of the form 4n+1. However, y = x+2 = 4N+3, and when you multiply factors of the form 4n+1 together, you can never get a result of the form 4N+3. So y doesn't have any prime factors at all - which is absurd.

**In the second case (an odd number of factors), consider the value y=3x+2.**

This number cannot be evenly divisible by any prime number of the form 4n+3, i.e. by a, b, c, ..., p, q, since it will leave a remainder of 2 when divided by any of them. So all its prime factors must be of the other flavor, namely of the form 4n+1. However, y = 3x+2 = 3(4M+3)+2 = 12M + 11 = 4(3M+2) + 3 = 4K+3, and as before, when you multiply factors of the form 4n+1 together, you can never get a result of the form 4K+3. So y doesn't have any prime factors at all - which is equally absurd.

If you believe that there are only finitely many prime numbers of the form 4n+3, you are forced to absurd conclusions - which proves there must be infinitely many of them