# Given $N$, $a$, and $b$, does there exist an $x$ such that $b$ divides $N-ax$?

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.

• Sorry pedja. i messed up with the order. – Manoj R May 1 '12 at 13:30
• How much do you know about modular arithmetic? – anon May 1 '12 at 13:38
• upto modulo operator. – Manoj R May 1 '12 at 13:39
• 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$. – Arturo Magidin May 1 '12 at 19:08

You need to consider a couple of things, one of which is an elementary fact about the greatest common divisor. If $b|(N-ax)$, then $yb=N-ax$ for some $y\in\mathbb{Z}$ by definition $\Rightarrow ax+by=N$.

Now we need that basic fact I mentioned. If $(a,b)=N$, then $\exists\;x,y\in\mathbb{Z}$ such that $ax+by=N$ where $(a,b)$ indicates the greatest common divisor of $a$ and $b$. Notice that this means if the GCD of $a$ and $b$ is a factor of $N$, we can also find such an $x$. To actually find the coefficients $x$ and $y$, use the Euclidean algorithm "in reverse". The details are usually present in most elementary number theory texts. Let me know if you have problems filling in the rest.

• And what is GCD is 1? – Manoj R May 1 '12 at 14:11
• The result says that if $c$ and $d$ are relatively prime, there exist $u$ and $v$ such that $cu+dv=1$. (See Extended Euclidean Algorithm.) If $e=\gcd(a,b)$, and $e$ divides $N$, let $N=eM$. Find $u,v$ such that $(a/e)u+(b/e)v=1$, then multiply both sides by $N$. On the right we get $N$. On the left we get $(a/e)uMe+(b/e)vMe=a(Mu)+b(Mv)$. Set $x=Mu$, $y=Mv$. – André Nicolas May 1 '12 at 14:30

Hint $\rm\ \exists\: x\!:\ b\ |\ n-ax\iff \exists\: x,y\!:\ ax+by = n.\:$ Note that the set S of integers $\rm\:n\:$ of this form are closed under subtraction: $\rm\:N = a X + b Y,\ n = ax+by\:$ $\Rightarrow$ $\rm\:N-n = a(X-x)+b(Y-y).$ By this post we deduce that every element of S is a multiple of the least positive element of S, which equals $\rm\:gcd(a,b).\:$ Thus a solution $\rm\:x\:$ exists iff $\rm\:gcd(a,b)\ |\ n,\:$ and, if so, solutions can be found by scaling the solution for $\rm\:n = \gcd(a,b)$ via the extended Euclidean algorithm.

Hint :

$$N-ax \equiv 0 \pmod b \Rightarrow N-ax=kb \Rightarrow x=\frac{N-kb}{a}$$

for some integer $k$ .