Register to reply

What is high level mathematics really like?

by Nano-Passion
Tags: mathematics
Share this thread:
pmsrw3
#19
Jul24-11, 12:06 PM
P: 455
Quote Quote by RandomMystery View Post
I don't understand how this part is valid:

"If q is not prime then some prime factor p divides q. This factor p is not on our list: if it were, then it would divide P (since P is the product of every number on the list); but as we know, p divides P + 1 = q. Then p would have to divide the difference of the two numbers, which is (P + 1) − P or just 1. But no prime number divides 1 so there would be a contradiction, and therefore p cannot be on the list. This means at least one more prime number exists beyond those in the list."

1*2*3*4 = 24 = P
24+1=25 = q

25 is not prime... why would "p have to divide the difference of the two numbers, which is (P + 1) − P or just 1."
First, if you want to follow Euclid's logic, you should be using the product of primes, not of all integers. That doesn't make a big difference. It takes a little more work, but one can still find an example of your point. The first is 2*3*5*7*11*13+1 = 30031 = 59*509.

More important, remember that you're assuming that there is no prime greater than pn (which is 13 in the example). Euclid's reasoning shows that no prime <= pn divides q. Under the assumption that there IS no prime greater than pn, there must therefore be no prime that divides q. The example doesn't contradict this, because the smallest prime that divides 30031 is in fact bigger than 13.

And how does "no prime number divides 1 so there would be a contradiction, and therefore p cannot be on the list." prove that there must be at least one more prime number on that list?
You started by assuming that every prime was on the list. You showed that this leads to a contradiction. That means that the assumption was WRONG. If the assumption "all primes are on the list" is wrong, then there must be at least one prime not on the list. (It doesn't have to be q, though. That's what your example shows.)
RandomMystery
#20
Jul25-11, 07:20 PM
P: 69
Quote Quote by pmsrw3 View Post
First, if you want to follow Euclid's logic, you should be using the product of primes, not of all integers. That doesn't make a big difference. It takes a little more work, but one can still find an example of your point. The first is 2*3*5*7*11*13+1 = 30031 = 59*509.

More important, remember that you're assuming that there is no prime greater than pn (which is 13 in the example). Euclid's reasoning shows that no prime <= pn divides q. Under the assumption that there IS no prime greater than pn, there must therefore be no prime that divides q. The example doesn't contradict this, because the smallest prime that divides 30031 is in fact bigger than 13.


You started by assuming that every prime was on the list. You showed that this leads to a contradiction. That means that the assumption was WRONG. If the assumption "all primes are on the list" is wrong, then there must be at least one prime not on the list. (It doesn't have to be q, though. That's what your example shows.)
Thanks for the reply, it's cleared up some things and I think I get it now.

Euclid's proof shows that if P + 1 is not prime, then P + 1 can not be divided by a prime number in the finite set of prime numbers since when you divide P + 1 by a factor of P, that factor will end up dividing 1.

[itex]\frac{(P + 1)}{factor of P}= factor of P\times(something) + \frac{1}{factor of P}[/itex]


Register to reply

Related Discussions
What is advanced-level mathematics used for? General Math 26
Should I Take A-Level Further Mathematics? Academic Guidance 8
GCSE level math books (end of Junior high, first year high school i think) General Math 0
Beginning high school olympiad mathematics books Science & Math Textbooks 1
Good A-level mathematics textbooks? Academic Guidance 5