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!

• Do you know how to work with arithmetic mod n? In particular, since $\gcd(a,n)=1$, there is an integer $A$ so that $Aa \equiv 1\pmod n$. Given any integer $y$, can you solve for $x\pmod n$ so that the equation holds? – Ted Shifrin Nov 3 '19 at 5:37

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

• Sorry what do $\bar a$ or $\bar 1$ mean ? – AgentS Nov 3 '19 at 4:23
• Here $\overline a=\{a+kn:k\in \Bbb Z\}$. – Sumanta Nov 3 '19 at 4:25
• Ohk looks it replaces $a\mod n$ with $a+kn$. Got it thanks :) – AgentS Nov 3 '19 at 4:26
• Then $\bar 1$ is $1 + kn$ – AgentS Nov 3 '19 at 4:28
• Yeah. $\overline 1=\{1+kn : k\in \Bbb Z\}$. – Sumanta Nov 3 '19 at 4:28

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.