# Find $q$ and $r$ with $0\leq r\leq |b|$, such that $a=qb+r$

Find $q$ and $r$, with $0\leq r\leq |b|$, such that $a=qb+r$ for

• $a=115,\ b=26$
• $a=400,\ b=-17$
• $a=-312,\ b=-64$

Sadly I missed the class where the prof went over this, so I have no idea what to do. Can somebody point me in the direction of the name of a process or theorem or something so that I can find out how to do it?

Thanks..

-
Hmmm. I understand how the Euclidean algorithm works for finding relative primality and the GCD of two numbers... Is this similar? It didn't appear to be when I first read it. – agent154 Mar 12 '13 at 14:46
Yes. Very similar. This is a single iteration in Euclid's algorithm for findsing the gcd. – Jyrki Lahtonen Mar 12 '13 at 15:15
This is the integer division algorithm with quotient $\rm\,q\,$ and remainder $\rm\,r.\:$ Yes, the division algorithm is the inductive step in the Euclidean algorithm for the gcd. – Math Gems Mar 12 '13 at 18:02

You should have dealt with the case when $a \ge 0$ and $b > 0$ in school.

When $a < 0$ and $b > 0$ divide first $-a$ by $b$ $$-a = b q + r, \qquad 0 \le r < b,$$ then consider $$a = b (-q) -r$$ If $r = 0$, then you're done. If $0 < r < b$, then $$a = b (-q -1) + b - r, \qquad 0 < b - r < b.$$ Finally, if $b < 0$, divide $a$ by $-b$ $$a = (-b) q + r = b (-q) + r, \qquad 0 \le r < -b = \vert b \rvert,$$ done.

-

Hint:

If $(q_0,r_0)$ is the solution to $a=qb+r$ then $(q_0-k,r_0)$ is the solution to $a-kb = qb+r$. In fact $q = \frac{a-r}{b}$ and because $0\leq r < |b|$ we have $0\leq\left|\frac{a}{b}-q\right|<1$.

Good luck ;-)

-