Solving Congruences Modulo m

To solve a congruence of the form ax≡b $\left(\vphantom{ \limfunc{mod}m}\right.$$\limfunc$modm$\left.\vphantom{ \limfunc{mod}m}\right)$, multiply both sides by a-1$\limfunc$modm to get x = b/a$\limfunc$modm.

The congruence 17x≡23 $\left(\vphantom{ \limfunc{mod}127}\right.$$\limfunc$mod127$\left.\vphantom{ \limfunc{mod}127}\right)$ has a solution x = 91, as the following steps illustrate.


$\blacktriangleright$ Evaluate

23/17$\limfunc$mod127 = 91


Check this result by substitution back into the original congruence.


$\blacktriangleright$ Evaluate

17⋅91 $\limfunc$mod127


= 23

Note that, since 91 is a solution to the congruence 17x≡23  $\left(\vphantom{ \limfunc{mod}127}\right.$$\limfunc$mod127$\left.\vphantom{ \limfunc{mod}127}\right)$, additional solutions are given by + 127n, where n is any integer. In fact, x≡91 $\left(\vphantom{ \limfunc{mod}127}\right.$$\limfunc$mod127$\left.\vphantom{ \limfunc{mod}127}\right)$ is just another way of writing x = 91 + 127n for some integer n.