Q: If $a \not\equiv 0\ (\mod m\ )$ while m is prime, can I say that : $(a,m) = 1$? It seems logical to me but I can't prove it.

A: This implication is only true if $m$ is prime.
If $m$ is composite number, then you can take $a$ such that $a$
is not divisible by $m$ but $a$ and $m$ share some common factor $d \gt 1$.
Example 1: $m = 20$, $a = 14$.
$d=2$ is a common factor but $a$ is not divisible by $m$
Example 2: $m = 11$.
Now if you pick an $a$ which is not divisible by $m$,
then for sure $a$ is also relatively prime with $m$.
That's because $m$ is prime in this case.

A: You can say $(a,m)\neq m$. That's it. Any other divisor of $m$ is possible to achieve by simply choosing that to be $a$
$a\equiv 0\pmod m$ means $a$ is a multiple of $m$. And $(a,m)=m$ means $a$ is a multiple of $m$. So if one isn't true, neither is the other.

A: Since $(a,m)$ divides the prime $\,m\,$ we infer $\,(a,m) = 1\,$ or $\,m\,$.
But $\,(a,m)=m\Rightarrow m\mid a,\,$ contra hypothesis. So $(a,m)=1$
