1
$\begingroup$

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!

$\endgroup$
1
  • $\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$ Commented Nov 3, 2019 at 5:37

2 Answers 2

2
$\begingroup$

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

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

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .