Proving that if gcd(a,n)=gcd(b,n)=1, then ax+by = c (modn) has exactly n different solutions mod n. I am taking an undergraduate course in basic Number Theory, and I came across this question in my textbook:
Show that if $\text{gcd}(a,n)=\text{gcd}(b,n)=1$, then $ax+by\equiv c(\text{ mod }n) $ has exactly $n$ different solutions $\text{mod }n$.
I understand that $ax \equiv\  b(\text{ mod }n)$ has a non-empty solution set if $\text{gcd}(a,n)$ divides $b$.
I am struggling to understand how to show there are exactly n different solutions to $ax+by \equiv c(\text{ mod }n)$. 
Any help would be appreciated, thanks!
 A: The equation $ax+by=c$ takes the form $\overline a\cdot\overline x+\overline b\cdot\overline y=\overline c$ in $\Bbb Z_n$.
But, by assumption $\text{gcd}(a,n)=1$, so that, $aa'+nn'=1$ for some $a',n'\in \Bbb Z$. In $\Bbb Z_n$ this can be written as $\overline a\cdot \overline{a'}+\overline n\cdot \overline{n'}=\overline 1\implies\overline a\cdot \overline{a'}+\overline 0\cdot \overline{n'}=\overline 1\implies\overline a\cdot \overline{a'}=\overline 1$. That is $\overline a$ is invertible in $\Bbb Z_n$.  
So $\overline a\cdot\overline x+\overline b\cdot\overline y=\overline c$  reduces to an equation $AX+BY=C$ in $\Bbb Z_n$, where $A$ is invertible in $\Bbb Z_n$. Clearly for a given $Y\in \Bbb Z_n$ we have unique $X\in\Bbb Z_n$, namely $X=A^{-1}(C-BY)\in \Bbb Z_n$, for which $AX+BY=C$ holds.
That is we have exactly $n$-many distinct solution in $\Bbb Z_n$. 
A: Let $c = k +(c-k)$, $k=0,... ,n-1$. Since $(a,n)=(b,n)=1$, it holds that


*

*$ax \equiv k \mod n$

*$by \equiv c-k \mod n$
have unique solutions modulo $n$, namely


*

*$x \equiv a^{\varphi(n)-1}k \mod n$

*$y \equiv b^{\varphi(n)-1}(c-k) \mod n$
Hence, $ax + by \equiv k + (c-k) \mod n$ has $n$ different solutions.
