Proving that if gcd(a,n)=gcd(b,n)=1, then ax+by = c (modn) has exactly n different solutions mod n.

Question

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!

Answer 1

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

Answer 2

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.