1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    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!

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