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