gcd and lcm - Show that a positive integer $n in mathbb{N}$ is prime if and only if $gcd(n,m)=1$ for all $0

Show that a positive integer $n \in \mathbb{N}$ is prime if and only if $\gcd(n,m)=1$ for all $0

I know that I can write $n=km+r$ for some $k,r \in \mathbb{Z}$ since $n>m$

and also that $1=an+bm$. for some $a,b \in \mathbb{Z}$

Further, I know that $n>1$ if I'm to show $n$ is prime.

I'm not sure how I would go about showing this in both directions though.

Answer

Hint: If $d$ divides $n$, then $gcd(d,n)=d$.