- #1
AlexChandler
- 283
- 0
Homework Statement
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)
Homework Equations
(a,b)= the greatest common factor of a and b
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?