Solving a linear diophantine equation in $\mathbb{Z}_{n}$

Question

Let $Z_{n} = \{ 0, 1, 2, \cdots, n-1 \}$, essentially, it is the set of all possible remainders under division by $n$.

Let $\mathbf{a,b,c,n \neq 0}$. I need to find and prove necessary and sufficient conditions on integers $\mathbf{a,b,c,n}$ for which the linear diophantine equation $\mathbf{ax+by=c}$ is solvable in $\mathbf{Z_{n}}$. I.e., I need to find necessary and sufficient conditions for the existence of $x$, $y$ $\in Z_{n}$ such that $ax+by=c$ is true.

To begin, I thought that it would be better then to replace $x$ and $y$ with their congruence classes modulo $n$: $ax+by = c \, \implies \, a[x]_{n}\, +_{n} \, b[y]_{n} = c \, \implies \, [ax]_{n}\,+_{n}\,[by]_{n} = c \, \implies \, [ax+by]_{n} = c \, \implies \, ax+by \equiv c \mod n.$

My conjecture is that $ax+by=c$ is solvable in $Z_{n}$ if and only if $\gcd(a,b,n)=c$, but I'm not sure how to show this, primarily because of the difficulty "translating" number theoretic properties to the case of three integers.

Could somebody please tell me if I'm correct in my conjecture, and get me (at least) started with the proof?

Thank you.

Answer 1

Here is your answer.

You want sufficient and necessary conditions that $ax+by \equiv c \mod n$ is solvable.

Note that this is equivalent to the existence of integers $x,y,z$ such that $ax+by+nz = c$. Hence, $c$ must be a multiple of $\gcd(a,b,n)$.

Now, suppose that $c$ is a multiple of $\gcd(a,b,n)$. Then, $c=ax+by+nz$ for some $x,y,z$, so again the congruence is solvable.

Hence the condition is very simple:

$ax+by \equiv c \mod n$ is solvable $\iff \gcd(a,b,n) | c$.

To give an example, let $n=7$, $a=12$,$b=6$,$c=4$. We have to solve $12x+6y \equiv 4 \mod 7$.

According to what I said, we have that there exist integers $x,y,z$ such that $12x+6y+7z=4$. Finding such integers is not difficult, in fact you can notice that with $x=1,y=1,z=-2$, we have $12x+6y \equiv 4 \mod 7$. Here, the condition $\gcd(a,b,n) | c$ is satisfied as $1 | 4$.

An example where the condition is not satisfied, is $a=b=4,n=8$ and $c=7$.

Suppose that we are trying to solve $4x+4y \equiv 7 \mod 8$. Then we want integers $x,y,z$ such that $4x+4y+8z=7$. However, $4$ divides the right side while $4$ does not divide the right side. Hence this congruence can't be solved.

You were close in stating equality, however, $c$ could be a multiple of the $\gcd$. In fact this is the exact condition.