Q: Prove: $gcd(a,n)=1, n \in \mathbb{N}, a \in \mathbb{Z} \implies \forall c \in \mathbb{Z}\ \exists m \in \mathbb{Z}\,:\, ma=c \pmod{n}$

Question

I was trying to prove the next simple statement ,without success thus far.

Suppose that $gcd(a,n)=1$, where $n \in \mathbb{N}$ and $a \in \mathbb{Z}$.

Show that for all $ c \in \mathbb{Z}$ there exists $m \in \mathbb{Z}$ such that $ma \equiv c \pmod{n}$.

Any ideas?

Answer 1

By Bezout's identity, there exists $l,k\in\mathbb{Z}$ such that $al+nk=\gcd(a,n)=1$, so $a(lc)+n(kc)=c$, which implies $a(lc)\equiv c\bmod n$

Answer 2

Since $\gcd(a,n)=1$, we know $a^{-1}\bmod n$ exists. For each $c\in\Bbb Z$, choose $m\in\Bbb Z$ such that $m\equiv ca^{-1}\pmod{n}$.

Answer 3

As $a$ and $n$ are coprime, consider the set $\{0a,1a,\dots,(n-1)a\}\mod n$.

This set is $\{0,\dots,n-1\}$, because if $m_i,m_j\in\mathbb{Z_n}$ and $m_i\ne m_j$, we would have $m_ia\equiv m_ja\equiv c\mod n\to (m_i-m_j)a\equiv 0\mod n\to (m_i-m_j)=0$, a contradiction.