# Infinite Primes Proof

• Mar 31st 2005, 08:41 PM
Yankee77
Infinite 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 PM
Matrix
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 AM
Artriste
Euclid'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 PM
hpe
Inifinitely 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 AM
theprof
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 PM
Artriste
I give up
Quote:

Originally Posted by hpe
:confused:
Challenge - are there infinitely many primes in the arithmetic progression 3, 7, 11, 15, 19, 23, 27, 31, ... ? Why / why not?

I would guess that the answer is yes. But you have stumped me. Care to enlighten us hpe?
• Apr 9th 2005, 09:19 PM
theprof
Quote:

Originally Posted by hpe
@ Artriste -
Challenge - are there infinitely many primes in the arithmetic progression 3, 7, 11, 15, 19, 23, 27, 31, ... ? Why / why not?

the aritmetic sequence of terms 3,7,11,15,... can be writtenas 3+4n (n=0,1,2,3...) and GCD(3,4) = 1. So contains infinitely many primes because of Dirichlet Theorem.
http://mathworld.wolfram.com/DirichletsTheorem.html

bye
• Apr 11th 2005, 08:40 AM
hpe
Inifinitely 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