[Math] Linear Diophantine equation modulo $n$

Question

Is there a way to find all solutions $(x,y)$ to the equation: $a x + b y = c\pmod n$ for fixed integers $a,b,c$ and $n$?

Regards,
Leon

Answer 1

So, $ax+by=c+d\cdot n$ where $d$ is any integer

Now, if $(a,b)=g$ does nor divide $(c,d\cdot n),$ for any $d$ there will be no solution.

If $g$ divides $(c,d\cdot n)$ let $\frac aA=\frac bB=\frac cC=\frac {d\cdot n}D=g$

So, we $Ax+By=C+D$ where $(A,B)=1$

Using Bézout's Lemma, we can find integers $u,v$ such that $Au+Bv=1$

So, we have $Ax+By=(Au+Bv)(C+D)$

$\implies A\{x-u(C+D)\}=B\{v(C+D)-y\}$

$\implies \frac{B\{v(C+D)-y\}}A=x-u(C+D)$ which is an integer

$\implies A$ divides $B\{v(C+D)-y\}$

$\implies A$ divides $\{v(C+D)-y\}$ as $(A,B)=1$

$\implies v(C+D)-y=A\cdot m$ where $m$ is any integer

$\iff y=v(C+D)-A\cdot m$