A calculus of the absurd

19.2 Modular arithmetic

Given that we now know that division really exists (as if there was ever any doubt), we can start to talk about remainders.

19.2.1 Core definitions

  • Definition 19.2.1 We say that for \(x, y, m \in \mathbb {Z}\) that

    \begin{equation} x \equiv _m y \end{equation}

    if and only if \(m | (x - y)\).

  • Theorem 19.2.1 For \(x, y, m \in \mathbb {Z}\), \(x \equiv _m y\) if and only if \(R_{m}(x) = R_m(y)\).

Proof: first we prove the “if” direction; suppose that \(x = a \times m + r\) and \(y = b \times m + r\) where we define \(r = R_m(x) = R_m(y)\). In this case

\begin{align} x - y &= a \times m + r - b \times m - r \\ &= (a - b) \times m \end{align}

and thus \(m | (x - y)\).

For the “only if” direction, things are marginally more hairy. Let us suppose that \(x \equiv _m y\), then

\begin{equation} m | (y - x) \iff y - x = km. \end{equation}

Here we will apply the division algorithm (Theorem 19.1.1), which tells us that we have unique \(R_m(a)\) and \(R_m(b)\) such that

\begin{align} x = am + R_m(x) & y = bm + R_m(y) & 0 \leqq R_m(x), R_m(y) < m \end{align}

Then, it follows from \(0 \leqq R_m(x), R_m(y) < m\) that

\begin{equation} -R_m(y) \leqq R_m(x) - R_m(y) < m - R_m(y) \end{equation}

which in turn implies that

\begin{equation} - m < R_m(x) - R_m(y) < m. \end{equation}

Therefore, we can write that

\begin{equation} x - y = am + R_m(x) - (bm + R_m(y)) \end{equation}

from which we can show that \(m | (R_m(x) - R_m(y))\); as \(m | (x - y)\) by definition there exists integer \(k\) such that \(x - y = km\), and thus that

\begin{equation} (k - a + b)m = R_m(x) - R_m(y). \end{equation}

Then as \(-m < R_m(x) - R_m(y) < m\) it must be true that

\begin{equation} R_m(x) - R_m(y) = 0m = 0 \end{equation}

and thus the desired equality holds.