Linear Congruence Solver
This page was created on August 1, 1998. Applet © 1998 by J. L. Pe.

Your browser needs to be Java-capable to see this applet.

This applet solves the linear congruence aX = b (mod n), where a, X, b, n are integers with a, n > 0. Recall that x = y (mod z) means x - y is divisible by z. It can be shown that aX = b (mod n) has a solution X if and only if d = gcd(a, n) (greatest common divisor of a and n) divides b. Whenever this congruence has a solution, it has d solutions mod n. In fact, the d solutions modulo n can be generated from one solution X (mod n) by repeatedly adding, until d solutions have been obtained, n' = n/d to X and reducing mod n. See A Concise Introduction to the Theory of Numbers by Alan Baker (Cambridge University Press) for an excellent treatment of this topic.

This program is simple but, nonetheless, useful in several fundamental computations in the theory of numbers. For example, the only "trial and error" part of the solution of simultaneous congruences by the Chinese Remainder Theorem involves the solution of individual linear congruences.


Back to math.java.lablet.