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