Is p Prime if gcd(a, p) = 1 or p Divides a?

[AlexChandler]

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?

 

[gb7nash]

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?

No. You want to show this works for all (a,p). You're on the right track wanting to show by contradiction, but try this instead:

Case 1: Let (a,p) = 1, p does not divide a and assume to contrary that p is not prime. So p = xy, x,y > 1. How can we get a contradiction?

Case 2: Let (a,p) != 1, p divide a and assume to contrary that p is not prime. So p = xy, x,y > 1. How can we get a contradiction?

 

[AlexChandler]

Ok thank you. That seems a much better way to prove this. However, I am still not seeing the logical flaw in the argument I used. If you let "(a,p)=1 or p divide a", and assume that p is not prime, isn't an example of a contradiction enough to conclude that the assumption was false?

 

[gb7nash]

I see what you're talking about now.

This unfortunately won't work. You've shown that you obtain a contradiction only for that example (which is good). However, assuming that we did it your way, how do we know that there don't exist examples where there's not a contradiction and the example satisfies all three statements?

By keeping things general, you'll be able to show that you'll obtain a contradiction for every time you choose p to not be prime.

 

[BrianMath]

Ok thank you. That seems a much better way to prove this. However, I am still not seeing the logical flaw in the argument I used. If you let "(a,p)=1 or p divide a", and assume that p is not prime, isn't an example of a contradiction enough to conclude that the assumption was false?

I think this only works when you're making a statement about all non-primes having those properties. That is, your counterexample must be against a statement that says "for all non-prime p, (a,p)=1 or p divides a". However, in your statement, you're only assuming that there might exist one such p that isn't prime with those properties, and so a counter example would not show that the statement is wrong (just that the p you chose doesn't fit the description; there are still infinitely many p to choose from that aren't prime that might fit your requirements).

Against a "for all" statement, such as for all f that are continuous at any number of points, f is differentiable at those points, you can provide a counter example (f(x) = |x| works here) and that takes care of the problem.
However, for a "there exists" statement, such as "\exists \delta \; s.t.\; \forall \varepsilon > 0, |x-x_0| < \delta \implies |f(x)-L|<\varepsilon
If you just pick \delta = 100, it probably wouldn't work for the implication, but would that disprove that limit, or would there still be a possibility that \delta = 99 would work? If not, would 98? 97? etc