next up previous contents
Next: How to do it Up: The classical sets of Previous: Modular Arithmetic   Contents

Solving Congruences

We wish to solve equations of the form $ a x \equiv b \pmod{m}$ given $ a,b \in \mathbb{Z}$ and $ m \in \mathbb{N}$ for $ x \in \mathbb{Z}$. We can often simplify these equations, for instance $ 7 x \equiv 3 \pmod{5}$ reduces to $ x \equiv 4 \pmod{5}$ (since $ 21 \equiv 1$ and $ 9 \equiv 4
\pmod{5}$). This equations are not always soluble, for instance $ 6 x \equiv 4
\pmod{9}$, as $ 9 \nmid 6 x - 4$ for any $ x \in \mathbb{Z}$.

Subsections

root 2002-06-10