Euclid's proof of infinitude of primes.

Al-Allo · 2013-08-09 03:49:23

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

bobbym · 2013-08-09 04:20:50

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

Al-Allo · 2013-08-09 04:24:22

yes

bobbym · 2013-08-09 04:25:49

And we assumed that it was all of them?

Al-Allo · 2013-08-09 04:28:39

Yes also

bobbym · 2013-08-09 04:30:05

And that Pn was this hypothetical largest priime?

Al-Allo · 2013-08-09 04:31:10

Yup again

bobbym · 2013-08-09 04:32:10

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

Al-Allo · 2013-08-09 04:35:09

Yes, I agree

bobbym · 2013-08-09 04:35:54

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

Al-Allo · 2013-08-09 04:37:56

Yes !

bobbym · 2013-08-09 04:41:44

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?

Al-Allo · 2013-08-09 04:46:04

yeah

bobbym · 2013-08-09 04:46:22

Are you sure?

Al-Allo · 2013-08-09 04:49:01

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)

bobbym · 2013-08-09 04:52:34

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?

Al-Allo · 2013-08-09 04:53:47

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.

bobbym · 2013-08-09 04:55:09

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

Al-Allo · 2013-08-09 04:57:26

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)

bobbym · 2013-08-09 05:01:42

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!

Al-Allo · 2013-08-09 05:07:25

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 ?

bobbym · 2013-08-09 05:10:49

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.

Al-Allo · 2013-08-09 05:14:03

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

bobbym · 2013-08-09 05:16:10

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.

Al-Allo · 2013-08-09 05:19:03

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)

Math Is Fun Forum

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

Euclid's proof of infinitude of primes.

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

Re: Euclid's proof of infinitude of primes.

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

Re: Euclid's proof of infinitude of primes.

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

Re: Euclid's proof of infinitude of primes.

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

Re: Euclid's proof of infinitude of primes.

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

Re: Euclid's proof of infinitude of primes.

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

Re: Euclid's proof of infinitude of primes.

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

Re: Euclid's proof of infinitude of primes.

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

Re: Euclid's proof of infinitude of primes.

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

Re: Euclid's proof of infinitude of primes.

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

Re: Euclid's proof of infinitude of primes.

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

Re: Euclid's proof of infinitude of primes.

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

Re: Euclid's proof of infinitude of primes.

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

Re: Euclid's proof of infinitude of primes.

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

Re: Euclid's proof of infinitude of primes.

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

Re: Euclid's proof of infinitude of primes.

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

Re: Euclid's proof of infinitude of primes.

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

Re: Euclid's proof of infinitude of primes.

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

Re: Euclid's proof of infinitude of primes.

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

Re: Euclid's proof of infinitude of primes.

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

Re: Euclid's proof of infinitude of primes.

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

Re: Euclid's proof of infinitude of primes.

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

Re: Euclid's proof of infinitude of primes.

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

Re: Euclid's proof of infinitude of primes.

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

Re: Euclid's proof of infinitude of primes.

Board footer