next up previous contents
Next: Euler's Phi Function Up: Solving Congruences Previous: How to do it   Contents

Systems of congruences

We consider the system of equations

$\displaystyle x$ $\displaystyle \equiv a \mod{m}$    
$\displaystyle x$ $\displaystyle \equiv b \mod{n}.$    

Our main tool will be the Chinese Remainder Theorem.

Theorem 6.8.1 (Chinese Remainder Theorem)   Assume $ m,n \in \mathbb{N}$ are coprime and let $ a,b \in \mathbb{Z}$. Then $ \exists x_0$ satisfying simultaneously $ x_0 \equiv a \pmod{m}$ and $ x_0 \equiv b \pmod{n}$. Moreover the solution is unique up to congruence modulo $ mn$.

Proof. Write $ c m + d n = 1$ with $ m,n \in \mathbb{Z}$. Then $ cm$ is congruent to 0 modulo $ m$ and $ 1$ modulo $ n$. Similarly $ dn$ is congruent to $ 1$ modulo $ m$ and 0 modulo $ n$. Hence $ x_0 = a d n + b c m$ satifies $ x_0 \equiv a \pmod{m}$ and $ x_0 \equiv b \pmod{n}$. Any other solution $ x_1$ satisfies $ x_0 \equiv x_1$ both modulo $ m$ and modulo $ n$, so that since $ (m,n) = 1$, $ m n \mid x_0 - x_1$ and $ x_1 \equiv
x_0 \pmod{mn}$. $ \qedsymbol$

Finally, if $ 1 < (a,m)$ then replace the congruence with one obtained by dividing by $ (a,m)$ -- that is consider

$\displaystyle \frac{a}{(a,m)} x \equiv \frac{b}{(a,m)} \mod{\frac{m}{(a,m)}}.
$

Theorem 6.8.2   If $ p$ is a prime then $ (p-1)! \equiv -1 \pmod{p}$.

Proof. If $ a \in \mathbb{N}$, $ a \le p-1$ then $ (a,p) = 1$ and there is a unique solution of $ a x \equiv 1 \pmod{p}$ with $ x \in \mathbb{N}$ and $ x \le p-1$. $ x$ is the inverse of $ a$ modulo $ p$. Observe that $ a =
x$ iff $ a^2 \equiv 1 \pmod{p}$, iff $ p \mid (a+1)(a-1)$, which gives that $ a = 1$ or $ p - 1$. Therefore the elements in $ \{2, 3, 4, \dots,
p-2 \}$ pair off so that $ 2 \times 3 \times 4 \times \dots \times
(p-2) \equiv 1 \pmod{p}$ and the theorem is proved. $ \qedsymbol$


next up previous contents
Next: Euler's Phi Function Up: Solving Congruences Previous: How to do it   Contents
root 2002-06-10