Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
if $a$ is not a multiple of $\gcd(b,c)$, can it be solved? –  Sasha Sep 6 '12 at 20:48

1 Answer 1

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|improve this answer
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
    
Thank you both, this really helps! –  Ben Ruijl Sep 6 '12 at 21:12

Your Answer

 
discard

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.