Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫  π  -¹ ² ³ °

You are not logged in.

## #1 2013-08-09 03:49:23

Al-Allo
Member
Registered: 2012-08-23
Posts: 324

### Euclid's proof of infinitude of primes.

Hi, I'm having trouble with euclid's proof :

http://imageshack.us/photo/my-images/703/uhvj.jpg/

I'm having a problem with the last paragraph... If m is a product of primes, and q is one of those primes taken randomly, then we should be able to divide m by q to obtain the rest of the primes(p1,p2,etc.). But we established earlier that we CANNOT divide evenly, because we will have a remainder of one (By the way, I wonder where it comes from...)So now, I understand that this is a contradiction, but I'm not sure of following the ''we have a contradiction with the assumption that this list included all prime numbers." I'm not having the same conclusion about it, how does this prove that the list doesn't have ALL primes, even if we can't divide evenly? If it really contained all the primes, should we be supposed to divide it without a remainder, is it because primes are missing that it won't divide ??? Thank you for your help !

Can somebody help me ?? Thank you

Offline

## #2 2013-08-09 04:20:50

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

### Re: Euclid's proof of infinitude of primes.

Wasn't that given that p was a list of the primes assuming that such a list exists and  is finite?

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

## #3 2013-08-09 04:24:22

Al-Allo
Member
Registered: 2012-08-23
Posts: 324

yes

Offline

## #4 2013-08-09 04:25:49

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

### Re: Euclid's proof of infinitude of primes.

And we assumed that it was all of them?

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

## #5 2013-08-09 04:28:39

Al-Allo
Member
Registered: 2012-08-23
Posts: 324

Yes also

Offline

## #6 2013-08-09 04:30:05

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

### Re: Euclid's proof of infinitude of primes.

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

## #7 2013-08-09 04:31:10

Al-Allo
Member
Registered: 2012-08-23
Posts: 324

Yup again

Offline

## #8 2013-08-09 04:32:10

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

### Re: Euclid's proof of infinitude of primes.

You agree that m is bigger than this Pn and that it is odd?

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

## #9 2013-08-09 04:35:09

Al-Allo
Member
Registered: 2012-08-23
Posts: 324

Yes, I agree

Offline

## #10 2013-08-09 04:35:54

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

### Re: Euclid's proof of infinitude of primes.

This m then is either prime or a product of primes ( composite ) , yes?

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

## #11 2013-08-09 04:37:56

Al-Allo
Member
Registered: 2012-08-23
Posts: 324

Yes !

Offline

## #12 2013-08-09 04:41:44

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

### Re: Euclid's proof of infinitude of primes.

Let's take them one at a time. Can m be a prime? It cannot because the largest prime in the universe is Pn and m is bigger that that.  To say m is a prime would be a contradiction to what we assumed, that Pn is the biggest. Yes?

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

## #13 2013-08-09 04:46:04

Al-Allo
Member
Registered: 2012-08-23
Posts: 324

yeah

Offline

## #14 2013-08-09 04:46:22

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

### Re: Euclid's proof of infinitude of primes.

Are you sure?

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

## #15 2013-08-09 04:49:01

Al-Allo
Member
Registered: 2012-08-23
Posts: 324

### Re: Euclid's proof of infinitude of primes.

Yes, because if we assumed m to be prime, then it would mean that our list wasn't complete and there was a new prime that juste showed up, which wasn't in it(the complete list)

Last edited by Al-Allo (2013-08-09 04:49:37)

Offline

## #16 2013-08-09 04:52:34

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

### Re: Euclid's proof of infinitude of primes.

We can see that m must now be a product of primes.

But m is not a product of any of the primes in our list,yes?

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

## #17 2013-08-09 04:53:47

Al-Allo
Member
Registered: 2012-08-23
Posts: 324

### Re: Euclid's proof of infinitude of primes.

I don't understand, what do you mean by : But m is not a product of any of the primes in our list,yes?

I say yes, it is a product of p1,p2,pn.

Offline

## #18 2013-08-09 04:55:09

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

### Re: Euclid's proof of infinitude of primes.

m is not a a product of p1p2...pn because m would leave a remainder of 1 when divided by p1p2...pn

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

## #19 2013-08-09 04:57:26

Al-Allo
Member
Registered: 2012-08-23
Posts: 324

### Re: Euclid's proof of infinitude of primes.

Yes, for sure it would leave a remainder. Then, if m is a product of primes, what are those primes ???

Last edited by Al-Allo (2013-08-09 04:57:41)

Offline

## #20 2013-08-09 05:01:42

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

### Re: Euclid's proof of infinitude of primes.

That is the point, whatever they are they are not in our list which contains all the primes up to and including Pn.

But if they are primes and they are not in our list we have an incomplete list. This is not possible because if there is a Pn then our list is complete.

This m is not a prime and it is not a product of primes in our list. We have a contradiction with what we assumed to be correct in the beginning. m is not possible.

Conclusion by contradiction, there is no largest prime!

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

## #21 2013-08-09 05:07:25

Al-Allo
Member
Registered: 2012-08-23
Posts: 324

### Re: Euclid's proof of infinitude of primes.

Ok, just another thing :
Now suppose m is a product of primes. Let q be one of the primes in this product. Then m is divisible by q. But weve already seen that m is not divisible by any of the numbers in the list p1, p2, . . . , pn,

Why is he saying that m/q. I'm guessing that he's taking a prime "q" not in this list, because like we said, none of the primes in our lists divide m. And knowing that any number must be divided, he divides m/q and it works. Is it correct ?

Offline

## #22 2013-08-09 05:10:49

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

### Re: Euclid's proof of infinitude of primes.

He picks a q because m is not a prime, so it must be a product of primes. We can call one of them q.

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

## #23 2013-08-09 05:14:03

Al-Allo
Member
Registered: 2012-08-23
Posts: 324

### Re: Euclid's proof of infinitude of primes.

Ok, but it's not part of our list p1,p2,etc (the q) right ?

Offline

## #24 2013-08-09 05:16:10

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

### Re: Euclid's proof of infinitude of primes.

Of course not, none of them divides m! This q is weird it is a prime but it is not in the list of all the primes?! q is also impossible.

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

## #25 2013-08-09 05:19:03

Al-Allo
Member
Registered: 2012-08-23
Posts: 324

### Re: Euclid's proof of infinitude of primes.

Ok, but now m/q work yes or no ??? If it is outside the list, than it should divide m, because every number is divisible.(And we don't have that remainder of 1)

Last edited by Al-Allo (2013-08-09 05:19:49)

Offline