Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Euclid Proof of Infinite Primes

  1. May 25, 2009 #1
    Near the end of Euclid's proof he says that if you multiply all our known primes from 2 to Pn and then add 1 to it, the number isn't divisible by any of our primes up to Pn, because it leaves the remainder 1. Why is that? How does he know that it will always leave the remainder 1? Couldn't adding 1 just make a slightly larger number that has a factor that might be 2 or Pn? If someone can set my stoopid brain straight I'd be very happy. Thanks.
  2. jcsd
  3. May 25, 2009 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    We have that 2,..,p_n is a supposed list of all primes and we have constructed


    By construction it is one more than a multiple of any known prime (i.e. 2,..,p_n).

    Or, let me put it this way, I have something that is a multiple of 2, and I add one to it. Is the result a multiple of 2?
  4. May 25, 2009 #3
    No, as far as I can tell by doing a few examples in my head. I can maybe see how 2n + 1 never yields a multiple of 2 since 2n is always even, and adding 1 makes it odd, thereby making it indivisible by 2. Your multiple of 2 example is really simple, so I can see easily how to prove that result, but I don't see how it is known that multiplying all the primes and adding 1 constructs a number such that it isn't a multiple of any known prime.
  5. May 25, 2009 #4
    To kind of clarify the problem I'm having: how do we know kn+1 is not divisible by k or any of the factors that make up k?
  6. May 25, 2009 #5


    User Avatar
    Science Advisor

    Because if you divide kn+ 1 by k you get a quotient of n with remainder 1.
  7. May 26, 2009 #6


    User Avatar
    Science Advisor
    Homework Helper

    Because kn is divisible by k (leaving a remainder of 0), so one more than that would leave a remainder of 1.
  8. May 26, 2009 #7

    where n is an integer.

    If p is a factor of k, then

    [tex]\frac{kn+1}{p}=n'+\frac{1}{k},[/tex] where n' is an integer.
  9. May 26, 2009 #8
    perhaps it would be easier to see it this way: if you cycle through the integers, a multiple of k will appear ever k integers starting with 0 then k then 2k, 3k, etc. If P is the product of all known primes, then it is divisible by every prime, so in order to get a number that's divisible by any factor of P (ie any prime) you need to add at least 2 (the smallest prime) but 1>2 so [tex]2\not| P[/tex]
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook