$n>1$ is prime $\!\iff\!$ for all $a\!:\ (a,n)=1\,$ or $\,n\mid a$

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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