Let's start off with the division algorithm. This says that if you divide an integer \(a\) by a positive integer \(b\), you will always get an integer remainder \(r\) that is nonnegative, but less than \(b\). Equally important, there is only one way to write this – that is, there is a unique remainder under these circumstances.

The proof is below in Subsection 2.1.2.

Using this is really easy to do for small examples like \(a=13,b=3\) by division. \begin{equation*}13=4\cdot 3+1\text{ so }q=4\text{ and }r=1\end{equation*} For bigger values it's nice to have it implemented in Sage.

The first element is the quotient, the second the remainder. We can check that this algorithm works by multiplying and adding back together.

The discussion in the previous note actually turns out to be an enduring argument in number theory, too. Do we only care about positive numbers, or nonnegative ones as well? We saw this in the stamps example, since one could send a package for free under certain circumstances (campus mail), but might not care about that case. Similarly, are we required to use at least one of each type of stamp, or is it okay (as in our problem) to not use one type?

The neat thing about the division algorithm is that it is not hard to prove but still uses the Well-Ordering Principle; indeed, it depends on it. The key set is the set of all possible remainders of \(a\) when subtracting multiples of \(b\), which we call \begin{equation*}S=\{a-kb\, |\, k\in\mathbb{Z}\}\, .\end{equation*} Here is the proof:

• \(S\) must be nonempty (why?), and call the nonnegative piece \(S'=S\cap \mathbb{N}\). (Why must this also be nonempty?)

• The well-ordering principle must apply to \(S'\). Give the name \(r\) to the smallest element of \(S'\), which must be writeable as \(r=a-bq\) (that's the definition of being in \(S'\subset S\), after all).

• Now, if \(r\geq b\), we could have subtracted another copy of \(b\) while keeping the remainder in \(S'\); hence, we must have that \(r<b\). (Note that \(r\) is the smallest nonnegative such number.)

• These elements \(r\) and \(q\) must be unique. First let's observe that the \(r\) is unique, which would follow if the least element of a well-ordered set is unique. But think about that! If \(r\) and \(r'\) are both least elements of \(S\), then in particular they are less than (or equal to) each other – the definition of equality.

• Finally, we will need a factoring argument, the fact that (for any integers \(x\) and \(y\)) if \(xy=0\) then \(x=0\) or \(y=0\) (or both). Since we have shown \(r=r'\), then \(bq=bq'\). Hence \(b(q-q')=0\) so (since \(b>0\)) we have that \(q-q'=0\), which means the quotient is unique.

It's worth actually trying out this proof with some \(a\) and \(b\), say with \(a=26\) and \(b=3\).

As a scholium (see Exercise 2.5.1) note that if \(b<0\) there can still be a positive remainder, but here we would need \(0\leq r<|b|\) in the theorem.

It's kind of fun to prove interesting things about powers with this fact, and likely you did in a previous course. Here is some pattern for remainders of perfect squares modulo 4, for instance.

This certainly provides strong numerical evidence for the following proposition. But better is a proof!

One cool thing about this proof is that if we just change the proof from using \(n=(4q+r)^2\) to one using \(n=(mq+r)^2\), we can essentially do the same thing for several divisions at once. If the number we divide by is \(m\), then \begin{equation*}(mq+r)^2=m^2q^2+2mqr+r^2=m(mq^2+2qr)+r^2\, ,\end{equation*} hence all that matters for the final remainder is \(r^2\), since the rest is already divisible by \(m\).

But we know that there are only \(b\) possibilities for \(r\), so it's easy to check all their squares. For \(m=6\):

This verifies that \(r=0,1,3,4\) are the only possible remainders of perfect squares when you divide by six.