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!

Checking a proof of a basic property of prime numbers

  1. Dec 3, 2016 #1
    1. The problem statement, all variables and given/known data
    Prove: If p is prime and m, n are positive integers such that p divides mn, then either p divides n or p divides m.

    Is anyone willing to look through this proof and give me comments on the following: a) my reasoning within the strategy I chose (validity, any constraints or cases I might have missed), b) the strategy I chose (was it a good one, is there a better one, some other angle I might have taken), and c) my presentation (messiness, inelegance)?

    2. Relevant equations n/a


    3. The attempt at a solution
    Here's my proof.

    If p divides mn, then there must be some positive integer q such that mn = pq. Then (mn)/q = p is prime. The factors of p are m/q and n. Since p is prime, one of these factors must be equal to 1. Therefore either

    a) n = 1

    or

    b) m/q = 1.

    If a) holds, then mn = m = pq and we see that p divides m.

    If b) holds, then m = q, and so mn = qn = pq, which means p = n and so p divides n (with quotient of 1).

    Therefore, if p divides mn, then either p divides m or p divides n, as desired.
     
  2. jcsd
  3. Dec 3, 2016 #2

    rcgldr

    User Avatar
    Homework Helper

    or p divides both m and n.
     
  4. Dec 3, 2016 #3

    Math_QED

    User Avatar
    Homework Helper

    That's not nessecary in the proof. If p divides both m and n, p divides obviously m or n.
     
  5. Dec 3, 2016 #4

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You can't conclude that ##m/q## and ##n## are integer factors of ##mn/q##.

    ##q## might divide neither ##m## nor ##n##.
     
  6. Dec 3, 2016 #5

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    What results do you have available already? What properties are you allowed to use?
     
  7. Dec 3, 2016 #6
    The text I'm using has so far defined the greatest common divisor and gives the theorem (with proof) that two nonzero integers a and b have a unique positive greatest common divisor.

    I'll try to use these to make the proof. Thanks!
     
  8. Dec 3, 2016 #7
    I see! Thanks for the heads up!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Checking a proof of a basic property of prime numbers
  1. Prime Number Proof (Replies: 5)

  2. Prime number proof (Replies: 3)

Loading...