Modular Arithmetic

Definition 6.7.1   If $a$ and $b \in \mathbb{Z}$, $m \in \mathbb{N}$ we say that $a$ and $b$ are ``congruent mod(ulo) $m$'' if $m \mid a - b$. We write $a \equiv b \pmod{m}$.

It is a bit like $=$ but less restrictive. It has some nice properties:

• $a \equiv a \pmod{m}$,
• if $a \equiv b \pmod{m}$ then $b \equiv a \pmod{m}$,
• if $a \equiv b \pmod{m}$ and $b \equiv c \pmod{m}$ then $a \equiv c \pmod{m}$.

Also, if $a_1 \equiv b_1 \pmod{m}$ and $a_2 \equiv b_2 \pmod{m}$

• $a_1 + a_2 \equiv b_1 + b_2 \pmod{m}$,
• $a_1 a_2 \equiv b_1 a_2 \equiv b_1 b_2 \pmod{m}$.

Lemma 6.7.2   For a fixed $m \in \mathbb{N}$, each integer is congruent to precisely one of the integers

$$\{0, 1, \dots, m-1 \}.$$

Proof. Take $a \in \mathbb{Z}$. Then $a = q m + r$ for $q,r \in \mathbb{Z}$ and $0 \le r < m$. Then $a \equiv r \pmod{m}$. $\qedsymbol$

If $0 \le r_1 < r_2 < m$ then $0 < r_2 - r_1 < m$, so $m \nmid r_2 - r_1$ and thus $r_1 \not\equiv r_2 \pmod{m}$.

Example 6.7.3   No integer congruent to $3 \pmod{4}$ is the sum of two squares.

Proof. [Solution] Every integer is congruent to one of $0,1,2,3 \pmod{4}$. The square of any integer is congruent to 0 or $1 \pmod{4}$ and the result is immediate. $\qedsymbol$

Similarly, using congruence modulo 8, no integer congruent to $7 \pmod{8}$ is the sum of 3 squares.