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

Homework Help: 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]

    [tex]\frac{p_{1}p_{2}...p_{n}}{p_{n}}+\frac{1}{p_{n}}=k[/tex]
    [tex]p_{1}p_{2}...p_{n-1}+\frac{1}{p_{n}}=k[/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].

    Thanks!
     
  2. jcsd
  3. Jan 30, 2010 #2

    Hurkyl

    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

    Hurkyl

    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)

    OR,

    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook