Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
if $a$ is not a multiple of $\gcd(b,c)$, can it be solved? – Sasha Sep 6 '12 at 20:48
up vote 1 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.