TOPICS

Linear Congruence Equation

A linear congruence equation

 (1)

is solvable iff the congruence

 (2)

with is the greatest common divisor is solvable. Let one solution to the original equation be . Then the solutions are , , , ..., . If , then there is only one solution .

The solution of a linear congruence can be found in the Wolfram Language using Reduce[a*x == b, x, Modulus -> m].

Solution to a linear congruence equation is equivalent to finding the value of a fractional congruence, for which a greedy-type algorithm exists. In particular, (1) can be rewritten as

 (3)

which can also be written

 (4)

In this form, the solution can be found as Mod[b y, m] of the solution returned by the Wolfram Language function PowerMod[a, , m]. This is known as a modular inverse.

Two or more simultaneous linear congruences

 (5)
 (6)

are solvable using the Chinese remainder theorem.

Chinese Remainder Theorem, Congruence, Congruence Equation, Modular Inverse, Quadratic Congruence Equation

Explore with Wolfram|Alpha

More things to try:

References

Nagell, T. "Linear Congruences." §23 in Introduction to Number Theory. New York: Wiley, pp. 76-78, 1951.

Referenced on Wolfram|Alpha

Linear Congruence Equation

Cite this as:

Weisstein, Eric W. "Linear Congruence Equation." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/LinearCongruenceEquation.html