Prove that $ax \equiv 1 \bmod n \implies \gcd(a,n) = 1$.

Question

I'm trying to prove the following but having difficulties.

Suppose $a,x \in \mathbb{Z}$ and $n \in \mathbb{N}$ then prove if $ax \equiv 1 \mod n$ then $a$ is coprime to $n$.

I know what it means for the numbers to be coprime and using the congruence I can show that there exists $x,y$ that satisfies Bezout's lemma but I don't think that is sufficient here. Any help?

Answer 1

If $ax\equiv 1 \bmod n$ then there exists an integer $y$ such that $ax+ny=1$ in $\mathbb{Z}$. Hence $a$ and $n$ are coprime. Indeed, if $p\mid a$ and $p\mid n$ for some $p>1$, this would imply $p\mid 1$, a contradiction.