Thread: Infinite Primes Proof

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

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.

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

@ 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.


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

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

Originally Posted by hpe

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?

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

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