1
$\begingroup$

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

  • 1
    if$a$is not a multiple of $\gcd(b,c)$, can it be solved?2012-09-06

1 Answers 1

1

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.

  • 0
    Thank you both, this really helps!2012-09-06