A calculus of the absurd

17.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.

17.2.1 Core definitions
  • Definition 17.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 17.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 17.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.