# Showing that $p$ is an odd prime $\iff$ $\forall a \in \Bbb N$ $gcd(a,p)=1$ or $gcd(a,p)=p$

Prove that for all natural numbers $$p>2$$, $$p$$ is prime if and only if for every natural number $$a$$, $$gcd(p,a)=1$$ or $$gcd(p,a)=p$$.

$$(\implies)$$ If $$gcd(p,a)=1$$ is only true if $$p$$ does not divide $$a$$. Then it is the case that $$p$$ and $$a$$ are relatively prime therefore we prove the right implication.

$$(\impliedby)$$ If $$gcd(p,a)=p$$ then $$p$$ divides $$a$$ and this contradicts the definition of a prime.

This proof is not correct.

The $$(\implies)$$ proof only shows that $$a,p$$ are coprime, not necessarily that $$p$$ is prime; it's also just hard to make sense of how any of this really ... helps.

The $$(\impliedby)$$ proof shows no contradiction. For example, $$3$$ is prime, and $$gcd(3,3^5) = 3$$

To correct the first proof, a direct proof is best. You want to show that if $$p>2$$ is prime, then for all natural $$a$$, $$gcd(a,p)=1$$ or $$gcd(a,p)=p$$. In other words, assume from the beginning that $$p$$ is prime, and show that the greatest common divisor between it and any other natural number is $$1$$ or itself.

You can break that up into cases where $$a$$ is not divisible by $$p$$ and where $$a$$ is divisible by $$p$$. You should be able to conclude, respectively, that the greatest common divisors are $$1$$ and $$p$$.

For the second proof, you want to assume, for any natural numbers $$a$$ and $$p>2$$, if $$gcd(a,p)=1$$ or $$gcd(a,p)=p$$, then $$p$$ is a prime number. Start with those two facts about the greatest common divisors, and show from there that $$p$$ must be a prime number.

You could go for a proof by contradiction by showing composite numbers can't satisfy both conditions, and then show a prime number can which follows from the first proof.

• ya I don't know how to prove this :/ – brucemcmc Mar 7 at 8:40