# Solving $a + b x = c y$ in the integer domain for general $a$

I have the following equation:

$\frac{a + b x}{c} \in \mathbb{N}$ where $a,b,c,x \in \mathbb{N}$.

and I want to find all x that satisfy these requirements. This should be the same as:

$a + b x = c y,~~~ y \in \mathbb{N}$

This looks like a linear Diophantine equation, but Bézout's identity cannot be used since $a$ is not necessarily $\gcd(b, c)$.

How can I solve for $x$?

-
if $a$ is not a multiple of $\gcd(b,c)$, can it be solved? – Sasha Sep 6 '12 at 20:48

It's equivalent to asking when $bx\equiv -a\pmod{c}$.

In the case $b$ and $c$ are coprime, the problem would be easy, since $x\equiv -ab^{-1}$.

This seems to be decent introduction to solving linear modular equations.

-
If $b$ and $c$ are not coprime then it follows that $\gcd(b,c)$ divides $a$. Therefore, if $a$ is not a multiple of $\gcd(b,c)$ there is no solution. If it is a multiple, just divide the equation throughout by $\gcd$ and the problem is reduced to your answer. – Marek Sep 6 '12 at 21:02
Thank you both, this really helps! – Ben Ruijl Sep 6 '12 at 21:12