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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.