Sign up ×

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?


share|cite|improve this question
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

2 Answers 2

up vote 2 down vote accepted

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.

share|cite|improve this answer


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

share|cite|improve this answer

Your Answer


