Section2.1The Division Algorithm

Let's start off with the division algorithm. This basically 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\). The second part is that there is only one way to write this - that is, there is a unique remainder under these circumstances.

The proof is below in 2.1.1.

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

We can check that this algorithm works by multiplying and adding back together.

That is, \(281376=9702\cdot 29+18\).
Remark2.1.2

Sage note:
Notice that to access the first and second parts of the answer (the quotient and remainder), we use square brackets, and that we ask for the 0th and 1st parts!
In Python (the programming language behind Sage), as in many other languages, counting begins at zero. This actually turns out to be an enduring argument in number theory, too - do we only care about positive numbers, or nonnegative ones? We even 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.

Subsection2.1.1Proof of the Division Algorithm

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.
It's worth actually trying out this proof with some \(a\) and \(b\), say with \(a=26\) and \(b=3\).

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.

Subsection2.1.2Uses of the Division Algorithm

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.

Remark2.1.3

Sage note:
The syntax "for i in [0..10]:" just means we want to do the next command for integers from 0 to 10. The rest of it (all the percent symbols and so forth) replaces things so it formats right.

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\):

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