# 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

$$x \equiv _m y$$

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

$$m | (y - x) \iff y - x = km.$$

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

$$-R_m(y) \leqq R_m(x) - R_m(y) < m - R_m(y)$$

which in turn implies that

$$- m < R_m(x) - R_m(y) < m.$$

Therefore, we can write that

$$x - y = am + R_m(x) - (bm + R_m(y))$$

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

$$(k - a + b)m = R_m(x) - R_m(y).$$

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

$$R_m(x) - R_m(y) = 0m = 0$$

and thus the desired equality holds.