info prev up next book cdrom email home

Linear Congruence

A linear congruence

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

is solvable Iff the Congruence

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

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
1999-05-25