Please Login to access more options.

Exercise (Using The Division Algorithm)

For each pair of integers $a$ and $b$ below, find integers $q$ and $r$ such that $a=qb+r$ and $0\leq r<b$.

  1. Let $a=26$ and $b=7$.
  2. Let $a=-26$ and $b=7$.
  3. Let $a=435$ and $b=32$.
  4. Given $a$ and $b$, describe a general approach you could use to find the $q$ and $r$ promised from the division algorithm, and then show how to use your approach on another pair of integers.

Click to see a solution.

  1. Let $q=3$ and $r=5$. We then have $qb+r=3\cdot 7+5 = 21+5=26=a$. Also notice that $0\leq r<b$.
  2. It's tempting to try letting $q=-3$ and $r=-5$. However, this doesn't work since $r=-5$ is negative. We need $q$ and $r$ so that $a=qb+r$, or equivalently we need $a-qb=r<b$. So let's just pick many different values for $q$ until we get a nonnegative result for $a-qb$ that's less than $b$. We compute $$\begin{align} a-(1)b &=-26-7=-33, \\ a-(0)b &=-26-0=-26,\\ a-(-1)b &=-26+7=-19, \\ a-(-3)b &=-26+21=-5, \text{ and} \\ a-(-4)b &=-26+28=2. \end{align}$$ This shows that $q=-4$ and $r=2$ are our desired numbers.
  3. Let's just start picking values for $q$ until we obtain a value for $q$ so that $r=a-qb$ satisfies $0\leq r<b$. We obtain $$\begin{align} a-(10)b &=435-320>32, \\ a-(11)b &=435-352>32,\\ a-(12)b &=435-384>32,\\ a-(13)b &=435-416=19<32.\\ \end{align}$$ This means $q=13$ and $r=19$.
  4. Given $a$ and $b$, just start picking values for $q$ and compute $a-qb$. You want this number to be nonnegative and less than $b$. Increasing $q$ will cause the value $a-qb$ to drop. Decreasing $q$ will cause the value $a-qb$ to rise. So if you pick a value for $q$ and find $a-qb$ to be negative, then decrease your value of $q$ until you get a positive result. Similarly, if your initial choice for $q$ makes $a-qb$ positive, then increase your value of $q$ until you get a result lower than $b$.