1. The problem statement, all variables and given/known data prove that p is prime iff for any integer "a" either (a,p)=1 or p divides a (where (a,p) denotes the gcd of a and p) 2. Relevant equations (a,b)= the greatest common factor of a and b 3. The attempt at a solution I had no trouble with proving the forward direction of the statement. But for the backward direction, here is what I have: for any integer "a", let either (a,p)=1 or p divide a Now assume that p is not prime. The following must hold true: either (6,4)=1 or 4 divides 6 Since both of these statements are false, this is a contradiction. Therefore p must be prime. Q.E.D. It seems okay to me to use an example at this point to arrive at the contradiction. Is this a legitimate way to prove the theorem?