Proving the Primality of a Natural Number with Divisibility Property

[ar6]

Homework Statement

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.

Homework Equations

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

 

[bel]

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.

 

[Dick]

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.