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.

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.

share|improve this question
    
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
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$. –  Arturo Magidin May 1 '12 at 19:08

3 Answers 3

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.

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

share|improve this answer

Hint :

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

for some integer $k$ .

share|improve this answer

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.