# Homework Help: Proof about primes and gcd

1. Jul 17, 2011

### AlexChandler

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?

2. Jul 17, 2011

### gb7nash

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?

3. Jul 17, 2011

### 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?

4. Jul 17, 2011

### 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.

5. Jul 17, 2011

### BrianMath

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