1
$\begingroup$

Given $N$, $a$, $b$ and condition that all are positive integers, how to find whether any positive integer $x$ exists such that $b|(N-ax)$.

And if any such $x$ exists how to calculate minimum value of $x$?

This looks elementary but somehow I am stuck.

  • 0
    Sorry pedja. i messed up with the order.2012-05-01
  • 0
    How much do you know about modular arithmetic?2012-05-01
  • 0
    upto modulo operator.2012-05-01
  • 1
    This is equivalent to solving $ax\equiv N\pmod{b}$. A well-known necessary and sufficient condition is $\gcd(b,a)|N$, in which case there are precisely $\gcd(b,a)$ solutions modulo $b$.2012-05-01

3 Answers 3