$n>1$ is prime $\!\iff\!$ for all $a\!:\ (a,n)=1\,$ or $\,n\mid a$ It seems like it's obvious because if $n$ is prime then its gcd with every number is $1$... But I understand that by intuition and don't know how to formally prove it... I'm confused.
 A: If $n$ is prime, then clearly we have for all $a$
$$\gcd(n,a) = 1 \mbox{ or } n$$
because $\gcd(n,a)$ divides $n$. Moreover
it is $1$ if and only if $n$ does not divide $a$.
On the contrary, if $n$ has this property, let $k$ be a divisor of $n$. Then $\gcd(n,k) = k$. But now we have $k=1$ or $n | k$, so $n$ has no proper divisors. This means that $n$ is prime.
A: It is just a translation of the common definition "$n$ is prime iff $n$ has no nontrivial divisors" from divisor form into gcd form, $ $ i.e. the equivalent: $ $ "$n$ is prime iff $n$ has no $\rm non\color{#c00}{trivial}$ gcds".
To prove this claim, first notice that: $\ \color{#0a0}{n\mid a}\iff (n,a) = n,\,$ so our statement becomes
$$\begin{align} n>1\ \text{ is prime }\iff\, (n,a)\! =\! \color{#c00}{ 1}\ \ {\rm or}\ \ {\overbrace{(n,a) \!=\! \color{#c00}n}^{\large \color{#0a0}{n\,\mid\, a}}}\ \ \text{ for all integers }\, a\end{align}\qquad $$
i.e. if and only if  the only gcds $\,n\,$ has are $\:\!\color{#c00}{{\rm trivial\!:\ 1\  or}\ n}$. This is true if $n$ is prime since such gcds divide $\,n\,$ so are $1$ or $\,n.\,$ Conversely, if $n$ is composite then it has divisor $\,a\,$ that is nontrivial, i.e. $\,1 < a < n.\,$ But $\ a = (n,a)\,$ so $\, 1 < (n,a) < n,\,$ so $\,n\,$ has a nontrivial gcd $\,(n,a).$
A: If $n$ is not prime, then it is composite: $n=ab$. What is $(n,a)$?
Is $\frac{n}{(n,a)}$ an integer? What does that say about $n$ when $(n,a)\neq 1,n$?
