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

You are not logged in.

- Topics: Active | Unanswered

**Al-Allo****Member**- Registered: 2012-08-23
- Posts: 320

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

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 95,961

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

Offline

**Al-Allo****Member**- Registered: 2012-08-23
- Posts: 320

yes

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 95,961

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

Offline

**Al-Allo****Member**- Registered: 2012-08-23
- Posts: 320

Yes also

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 95,961

And that Pn was this hypothetical largest priime?

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

Offline

**Al-Allo****Member**- Registered: 2012-08-23
- Posts: 320

Yup again

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 95,961

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

Offline

**Al-Allo****Member**- Registered: 2012-08-23
- Posts: 320

Yes, I agree

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 95,961

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

Offline

**Al-Allo****Member**- Registered: 2012-08-23
- Posts: 320

Yes !

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 95,961

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

Offline

**Al-Allo****Member**- Registered: 2012-08-23
- Posts: 320

yeah

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 95,961

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

Offline

**Al-Allo****Member**- Registered: 2012-08-23
- Posts: 320

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

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 95,961

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

Offline

**Al-Allo****Member**- Registered: 2012-08-23
- Posts: 320

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

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 95,961

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

Offline

**Al-Allo****Member**- Registered: 2012-08-23
- Posts: 320

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

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 95,961

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

Offline

**Al-Allo****Member**- Registered: 2012-08-23
- Posts: 320

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 weve 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

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 95,961

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

Offline

**Al-Allo****Member**- Registered: 2012-08-23
- Posts: 320

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

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 95,961

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

Offline

**Al-Allo****Member**- Registered: 2012-08-23
- Posts: 320

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