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.

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

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.

$\endgroup$
2
  • $\begingroup$ And what is GCD is 1? $\endgroup$ – Manoj R May 1 '12 at 14:11
  • $\begingroup$ 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$. $\endgroup$ – André Nicolas May 1 '12 at 14:30
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Hint :

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

for some integer $k$ .

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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