2
$\begingroup$

I've been trying this for a little while now,

if $ax+by = d, \ $ then $a'x+b'y=d$

where $x>0\ $ and $0 \leq b' \leq x\ $ and $a,b,a',b',x,y, \in \mathbb{Z}$

My first thought is:

$$ \begin{align} ax+by &= d \\ ax &= d - by \\ \end{align} $$ Implies that (since $x \neq 0 $ ), $$\begin{align} x &| d - by \\ d & \equiv by \pmod{x} \end{align} $$ I'm not sure that helps. I also thought maybe from, $ax = d - by,\ $ I could say,

$$ \begin{align} d - by &= qx +r, \ 0 \leq r \leq x \\ d &= by + qx + r \end{align} $$

But I can't see a way of pulling the information from $r$ which ideally I could somehow rewrite as $ry$ so that $b'= r$. Any hints? Thanks again. Again, not technically homework just a problem from a book.

  • 0
    $\LaTeX$ hint: `\pmod{x}` will produce appropriately spaced $\pmod{x}$.2012-07-09
  • 0
    O, Thanks! Didn't know that.2012-07-09

2 Answers 2

2

The "tell" of the problem is the condition $0\leq b'\lt x$. That suggests dividing something by $x$ and letting $b'$ be the remainder.

Indeed, divide $b$ by $x$. We can write $b=qx+b'$, with $0\leq b'\lt x$. Then $$d = ax+by = ax+(qx+b')y = ax +qyx + b'y = (a+qy)x + b'y.$$ Setting $a'=a+qy$, we are done.

  • 0
    Totally! I kept going in circles trying to find out ways to get that restriction in the right place... Thanks so much.2012-07-09
0

Hint $\rm\ mod\ x\!:\ b\,y\equiv d\ \Rightarrow\: (b\ mod\ x)\, y\equiv d$

  • 0
    can you suggest a reference for learning more about $(b \ $mod $x)$? :)2012-07-09
  • 0
    @IQ472: $b\bmod x$ is just the remainder of $b$ when divided by $x$. This is the "binary mod" or "remainder" operation. In computer science, it is often denoted by %. (PS. In $\LaTeX$, `\bmod` produces the "binary mod", and `\pmod` the "parenthesis mod").2012-07-09
  • 0
    @IQ472 $\rm\: b' := (b\ mod\ x)\ $ is the remainder of $\rm\,b,\,$ modulo $\rm\,x,\,$ i.e. $\rm\: b = q\,x + b'\,$ for $\rm\,0 \le b' < x,\:$ whose existence and uniqueness follows from the (Euclidean) [Division with Remainder Algorithm.](http://en.wikipedia.org/wiki/Euclidean_division)2012-07-09
  • 0
    o, ok so it can also be written as: $[d] = [[b][y]]$. All $[]_{x}$2012-07-09
  • 0
    @IQ472 There is no need to also reduce $\rm\,d\,$ and $\rm\,y\,$ modulo $\rm\,x\,$, only $\rm\,b\,$. To conclude the proof note $\rm\,mod\ x\!:\: b'y\equiv d\:\Rightarrow\: a'x + b'y = d\,$ for some $\rm\,a'\in\mathbb Z,\,$ as desired.2012-07-09
  • 0
    $b'y \equiv d$ implies $x| b'y - d$ implies $a'x = b'y -d$. Thanks a lot Bill (if you don't mind me calling you that :))2012-07-09
  • 0
    @IQ472 Yes, you've got it now. Generally I provide (generous) hints rather than full solutions, since I think one learns better by *discovering* the proof rather than *reading* it. But, as you can see, I'm always happy to provide further hints on request. For problems like this, it is essential to learn to think in terms of modular aithmetic, which is why I expressed the hint in that language.2012-07-09
  • 0
    I reallly appreciate all your help. Your hints are great. Previously in this problem, I just wasn't sure if you were using notation I hadn't really seen before. But overall, I really like this method you have shown me. Initially this was the first way I tried solving the problem. But I didn't notice I could use the result as you showed. So thanks!2012-07-09