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
    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
    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