info prev up next book cdrom email home

Linear Congruence

A linear congruence

ax\equiv b\ \left({{\rm mod\ } {m}}\right)

is solvable Iff the Congruence

b\equiv 0\ \left({{\rm mod\ } {(a,m)}}\right)

is solvable, where $d\equiv (a,m)$ is the Greatest Common Divisor, in which case the solutions are $x_0$, $x_0+m/d$, $x_0+2m/d$, ..., $x_0+(d-1)m/d$, where $x_0 < m/d$. If $d=1$, then there is only one solution.

See also Congruence, Quadratic Congruence

© 1996-9 Eric W. Weisstein