next up previous contents
Next: Systems of congruences Up: Solving Congruences Previous: Solving Congruences   Contents

How to do it

The equation $ a x \equiv b \pmod{m}$ can have no solutions if $ (a,m)
\nmid b$ since then $ m \nmid a x - b$ for any $ x \in \mathbb{Z}$. So assume that $ (a,m) \mid b$. We first consider the case $ (a,m) = 1$. Then we can find $ x_0$ and $ y_0 \in \mathbb{Z}$ such that $ a x_0 + m y_0 = b$ (use the Euclidean algorithm to get $ x'$ and $ y' \in \mathbb{Z}$ such that $ a x' + m y' = 1$). Then put $ x_0 = b x'$ so $ a x_0 \equiv b \pmod{m}$. Any other solution is congruent to $ x_0 \pmod{m}$, as $ m \mid a(x_0 - x_1)$ and $ (a,m) = 1$. So if $ (a,m) = 1$ then a solution exists and is unique modulo $ m$.

root 2002-06-10