1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prime Number Proof Help.

  1. Jan 30, 2010 #1
    Let [tex]p_{1}, p_{2},...,p_{n}[/tex] be primes. Show that [tex]p_{1} p_{2}...p_{n}+1[/tex] is divisible by none of these primes.

    Let [tex]p_{1}, p_{2},...,p_{n}[/tex] be primes
    Let [tex]k \in N[/tex]
    Assume [tex]p_{1}p_{2}...p_{n}+1=kp_{n}[/tex]


    This is a contradiction because the left side will not be a natural number.

    My issue is that this seems to only prove [tex]p_{1} p_{2}...p_{n}+1[/tex] is not divisible by [tex]p_{n}[/tex] and not all [tex]p_{1}, p_{2},...,p_{n}[/tex].

  2. jcsd
  3. Jan 30, 2010 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    That sounds right.

    So, can you modify the proof to make it work for, say, p1?

    Or, can you find a way to use what this argument proves to prove the general theorem?
  4. Jan 30, 2010 #3
    To make it work for [tex]p_{1}[/tex] I can just use [tex]p_{1}[/tex] instead of [tex]p_{n}[/tex], I guess. I don't know if that helps me see what to do...

    I was thinking of writing something like what I had, but instead of [tex]p_{n}[/tex] on the right I would have [tex]p_{x}[/tex] where [tex]x\in{1,2,...,n}[/tex], but that seems weird.
  5. Jan 30, 2010 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    That sounds perfectly reasonable -- you want to write a proof that works simultaneously for each of the px's, so you have to use a variable.

    Incidentally, the other method I was hinting at is substitution. Substitute into the original argument the list of primes
    p1, ..., pk-1, pn, pk+1, ..., pn-1, pk
  6. Jan 30, 2010 #5
    I guess you are doing the proof of infinite primes.(=

    By using euclidean algorithm , you can conclude the gcd of [tex]p_{1}p_{2}...p_{n}+1[/tex] with [tex]p_{i}
    [/tex] for i=1,2,3...n will be 1 with a sound argument (hint: recall co-prime)


    By using modular , [tex]p_{1} p_{2}...p_{n}+1\equiv1(modp_{i})[/tex] for i=1,2,3...n, recalling 1 is not a prime , you may draw a conclusion that suffices to prove your proposition.
    Last edited: Jan 30, 2010
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Threads - Prime Number Proof Date
Checking a proof of a basic property of prime numbers Dec 3, 2016
Prime number proof Sep 28, 2013
Euclid's Proof for Prime Numbers Dec 25, 2010
Relatively Prime Numbers proof Feb 13, 2007
Prime Number Proof Feb 6, 2007