Prove that $n$ is prime $\iff \forall a\in\mathbb{Z}(\gcd(a,n)=1\lor n\mid a)$

Question

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\mid 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.

Answer 1

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