next up previous contents
Next: Solving Congruences Up: The classical sets of Previous: Applications of prime factorisation   Contents

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: Also, if $ a_1 \equiv b_1 \pmod{m}$ and $ a_2 \equiv 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

$\displaystyle \{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.
next up previous contents
Next: Solving Congruences Up: The classical sets of Previous: Applications of prime factorisation   Contents
root 2002-06-10