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 \[S=\{a-kb\, |\, k\in\mathbb{Z}\}\, .\] Here is the proof:

• \(S\) must be nonempty (why?), so the nonnegative piece of \(S\) must have the well-ordering principle apply. Call that piece \(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. There are a few ways to do it, but they basically all use some factoring argument, such as the fact that (for any integers \(x\) and \(y\)) if \(xy=0\) then \(x=0\) or \(y=0\) (or both). In that case, if \(bq=bq'\), then \(b(q-q')=0\) so (since \(b>0\)) we have that \(q-q'=0\), which means the quotient is unique.
• This means we just need 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.

As a scholium, which we won't use much immediately, 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 that a perfect square always leaves remainder \(r=0\) or \(r=1\) when divided by 4. But better is a proof!

• Take \(n=4q+r\). What happens if we square it, \((4q+r)^2\)?
• Algebraically, we get \(16q^2+8qr+r^2\). Clearly this is a multiple of 4 plus \(r^2\). So the only possible remainders are the remainders of \(r^2\), where \(r\) is already known to be less than 4!
• You can check these yourself to see that the only possibilities are the ones stated.

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 \[(mq+r)^2=m^2q^2+2mqr+r^2=m(mq^2+2qr)+r^2\, ,\] 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 them all. For \(m=6\):