A linear congruence equation
is solvable iff the congruence
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
which can also be written
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
are solvable using the Chinese remainder
See alsoChinese Remainder Theorem
, Modular Inverse
Explore with Wolfram|Alpha
ReferencesNagell, T. "Linear Congruences." §23 in Introduction
to Number Theory. New York: Wiley, pp. 76-78, 1951.
on Wolfram|AlphaLinear Congruence Equation
Cite this as:
Weisstein, Eric W. "Linear Congruence Equation."
From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/LinearCongruenceEquation.html