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$.
Not sure about my proof:
$(\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.