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!

  • $\begingroup$ 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? $\endgroup$ – 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$.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.