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

  1. Sep 26, 2007 #1


    User Avatar

    1. The problem statement, all variables and given/known data
    I'm starting an introductory course in "Advanced math" and need a little homework guidance please.

    The question: Let a, b, and q be natural numbers, and q > 1. Prove that if q has the property: q divides a or q divides b whenever q divides ab, then q is prime.

    2. Relevant equations

    3. The attempt at a solution

    Ok. First I'm assuming that this proof can't be too hard especially for one of the first assignments and is probably a standard one to assign new students in this subject so I apologize if this has been asked before. A little nudge in the right direction would be helpful. I think that I should try to prove the contrapositive. So assume q is not prime but then I am a little confused on what exactly ~(p) would be. Any help would be appreciated
  2. jcsd
  3. Sep 26, 2007 #2


    User Avatar

    Since a and b are both composite, let ab= mnjk, where two factors of mnjk is a and the other two is b. If p is prime and it divides ab = mnjk, then taking any combination of two of m,n,j, or k to be one factor and two to be the other, it is evident that one of the two factors must be divisible by p. Now prove the converse.
  4. Sep 26, 2007 #3


    User Avatar
    Science Advisor
    Homework Helper

    I like your contrapositive idea. The contrapositive is that if q is NOT prime, then there is an a and b such that q divides ab but q does not divide a or b. If q is NOT prime, i.e. composite, what's a good choice for a and b? bel, the OP doesn't have to prove the converse. That's harder and requires unique prime factorization.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook