A calculus of the absurd

Chapter 19 Number theory

19.1 Division

19.1.1 Introduction to division

If you thought division was hard enough, then unfortunately it gets worse. Much worse.

Here’s a really infuriating question: consider some integers \(a\) and \(b\). Let’s suppose that \(b > 0\), in which case we can ask does \(a\) divide \(b\)? Does this question seem non-infuriating to you? Just you wait. Most people do know what this means intuitively, and it’s not impossible to write a formulation of division a bit like this,

This is simple enough, e.g. if \(a=12\) and \(b = 3\), it is a truth universally acknowledged¹²²¹²² Well, certainly more so than “a single man in possession of a good fortune, must be in want of a wife” - people say that maths books are dull and dry; clearly people who haven’t opened a copy of Pride and Prejudice. that in \(\mathbb {Z}\), \(12 = 4 \times 3 + 0\), so we can say that \(3\) divides \(12\) with remainder \(0\).

As usual, once we have found or defined a mathematical property, it is natural to ask for which kinds of objects it exists, how one finds the values in question, and whether the values in question are unique.

I have (and hopefully you do to!) an intuitive notion that we can divide every number with some remainder (this is something one learns in primary school), that this remainder is unique (well, I certainly can’t think of any divisions with multiple remainders for the same divisor) and that the quotient is unique.

There’s actually more we “know” about the remainder, specifically that \(0 \leqq r < b\) - this should make sense if you consider that if the remainder was greater than \(b\), we can just increase \(q\) by one, and decrement the remainder.

We can encode this in the following theorem

Proof: this proof is actually painful because there are so many random things flying around.

Here’s a sketch of what we will show

• • Prove that there are some \(r \geqq 0\) which satisfy the properties the remainder should have.

• • Prove that therefore there exists at least one \(r < b\) which satisfies the properties the remainder should have.

• • Prove that the remainder is therefore unique.

We start by defining a set \(S\) of all the possible remainders. This kind of thing is really useful because it allows us to “forget” specific things we’ve assumed about the structure of our problem in order to prove specific things.

\begin{equation} S = \{r: r = a - bq \} \end{equation}

Then, we would like to show that \(S\) contains some positive members. This is not too bad. We do a proof by exhaustion here; either \(a \geqq 0\) or \(a < 0\). In the first case, we have some \(r \in S\) where \(r \geqq 0\) because we can set \(q = 0\) which gives us

\begin{align} r &= a - b0 \\ &= a \end{align}

And in this case \(a \geqq 0\), so we have a desired \(r \in S\).

In the other case, where \(a < 0\), we can set \(q = a\), and then we have

\begin{align} r &= a - ba \\ &= a(1 - b) \end{align}

This is also greater than or equal to zero, as \(a < 0\) and as \(b > 0\), we must have that \(1 - b \geqq 0\) so \(r \geqq 0\).

Now for the second part of the proof, which is that there exists some \(r < b\) where \(r \in S\). Here, the use of the set becomes apparent, we can forget about all the random nonsense we had to pull in order to show that we have some \(r \geqq 0\), we just know that it is true. We use some more theorems, specifically the well-ordering principle (this literally just states that if we have a set of integers, and some of these integers are positive, then we also have a least positive integer), and let \(r\) be the least positive element in \(S\).

Now we consider our goal: \(r < b\). We pull a familiar technique slightly adapted from proving that \(a - b = 0\) to show that \(a = b\), and we will try to show that

\begin{equation} r - b < 0. \end{equation}

Let’s start with \(r - b\), which we know is

\begin{align} r - b &= a - bq - b \\ &= a - b(q + 1) \end{align}

Let \(r' = a - b(q+1)\). We know that \(r' \in S\)! Now, we also know that \(r' < r\) (this is because \(a - bq < a - b(q+1)\) as we know that \(b > 0\)), and \(r\) is the least positive element, so \(r'\) must be negative; that is \(r' < 0\), which means that

\begin{equation} r - b < 0. \end{equation}

This was our goal!

All that remains to show is that \(r\) and \(q\) are unique. We will employ the standard method (as outlined in Section 6.7), and assume that we have \(r, r' \in \mathbb {N}\) (the natural numbers, of course, include \(0\), so we are covering the case where the remainder is \(0\)), such that \(r \ne r'\) and \(0 \leqq r, r' < b\). We will also let \(q, q' \in \mathbb {Z}\) such that \(q \ne q'\). That sentence is certainly a mouthful; all I really mean is “assume that they are not unique, then we will show that this is absurd, so they must be unique”.

Let us consider the value \(r\),

\begin{align} r &= a - bq \end{align}

Now we will use some ingenuity, and WLOG¹²³¹²³ Without loss of generality assume that \(q' < q\) (this is really without loss of generality, because we can always swap \(r\) and \(r'\) and \(q\) and \(q'\) if \(q' > q\) - don’t forget that we assumed \(q \ne q'\)), which means (as \(q, q' \in \mathbb {Z}\)) that \(q' \geqq q + 1\)

\begin{align} r &\leqq a - b(q' + 1) \\ &\leqq a - bq' - b \\ &= r' - b \\ &< b - b \\ &= 0 \end{align}

The last step follows because \(r' < b\). This is absurd, as we assumed that \(r \geqq 0\), so it certainly cannot be less than zero. Therefore, the remainders and quotients are unique.