The Division Algorithm

~ cfreddy10

Hello! This post belongs to a series called Number Theory. Before reading this post, I recommend going to that page and making sure you have the prerequisite material. You should be familiar with Set Theory Part 1, Set Theory Part 2, Quantifiers, Modulo and Equivalence Relations, and Divisibility and Prime Numbers.

Before I introduce the division algorithm, I need to introduce an axiom of the natural numbers. For those unfamiliar, an axiom is a statement that we accept to be true. Mathematics works largely by taking a set of axioms and proving things from them.

This axiom is called the Well-Ordering Principle and states that for any subset of \mathbb{N} , there exists a smallest element.

This seems obvious, but note that it is not true for some other infinite sets. We’ll explore that in the problems at the end of this post.

Now that we’ve established that axiom, let’s define the Division Algorithm. It states that \forall a, b \in \mathbb{Z} \ni b > 0, \exists ! q, r \in \mathbb{Z} \ni a = b * q + r and 0 \leq r < b .

This is a loaded statement, let’s try and break it down a little. So we pick two integers, a, b . Then we can find unique (that what ! means) q, r where a = b * q + r and 0 \leq r < b .

You may be wondering why we use the variable names q and r . We call q the quotient and r the remainder.

A lot of this is very similar to modulo arithmetic. If we look at a modulo b , then it’s equivalent to r . Make sure you see how these topics are connected as we will be using them together frequently.

I’m going to prove this statement, but not as precisely as some of you might be looking for. If you want more rigour, I suggest reading this page for a fantastic, more detailed proof. Here, I’ll just lay out the framework. Just to note, I label things a little differently in my proof, but the ideas are the same.

We’re going to define a set A = \{ a - k * b | (a - k * b) \geq 0, k \in \mathbb{Z} \} . Notice that these numbers are all positive, so by the Well-Ordering Principle, there is a smallest number. Set q to be the smallest value of k , and set r = a - q *b. Then a = q * b + r .

This produces our q and r , but we have to check a few things before we are done.

First, let’s show that 0 \leq r < b . From this construction, r cannot be negative. If r \geq b , then there would be a smaller value of k that we could find. So 0 \leq r < b .

Second, let’s show that these values are unique. Say you have q_{1}, q_{2}, and r_{1}, r_{2} where a = q_{1} * b + r_{1} = q_{2} * b + r_{2} .

Without loss of generality, assume that r_{2} \geq r_{1} . This is a common proof strategy, since I have two arbitrary values, it makes no difference which one I say is greater than or equal to the other.

Now, rearranging the equation gives r_{2} - r_{1} = b * ( q_{1} - q_{2} ) . We know that 0 \leq r_{1}, r_{2} < b , and that r_{2} - r_{1} is positive. The only way for b to divide this value is for r_{2} - r_{1} = 0 , so r_{2} = r_{1} , and consequently q_{1} = q_{2} .

This is a common method to show that value(s) are unique. Assume there are two different sets, then show that they’re equal.

Consquences of the division algorithm are everywhere, and this will be showing up a lot in the future. Be sure tha you understand what was presented here and do the practice problems! Be sure to ask me any questions you have.

Problems

  1. There is not a Well-Ordering Principle for \mathbb{Z} , can you give an example of a subset to show why this is?
  2. Come up with q, r for the following pairs in the form (a, b) : (16, 5), (5,16), (3, 7), (-10,3), (16,8) .
  3. What do you notice if 0 \leq a < b or if b | a .
  4. How can we use the division algorithm to show that every number is either even or odd?

That’s all for now! Check back to my main post Number Theory, for other posts in this topic. A good post to read after this would be The Fundamental Theorem of Arithmetic, as long as you’ve read Divisibility and Prime Numbers

Unknown's avatar

Published by cfreddy10

I'm a student at Hope College - a small, liberal arts college in West Michigan. I study math and physics - when I'm not struggling through problem sets, I can be found reading, hiking with friends, running, and listening to music!

Leave a comment