I need to prove that given $n\in\mathbb{N}$ ($n>1$), $n$ is prime $\iff \forall a\in\mathbb{Z}(gcd(a,n)=1\lor n\mid a)$.

I proved the first part, assuming that $n$ is prime and proving that for every $a$, $gcd(a,n)=1$ or $n|a$, but I'm struggling with the proof of the second part.. I assumed that for every $a$, $gcd(a,n)=1\lor n\mid a$, and then assumed that $n$ is not prime: from here we know that there exists $1<d<n$ such that $d\mid n$.. And I don't know how to proceed from here.

Thanks in advance.


Better to prove the contrapositive. Suppose that $n$ is not prime, and find an appropriate $a$ that breaks the other expression. This almost writes itself; if not prime then $n=cd$ for some $c,d$ that are neither $1$ nor $n$.

  • $\begingroup$ Ah >.<, thanks. $\endgroup$ – Daniel Oct 30 '13 at 13:59

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.