Linear Congruence Equation

A linear congruence equation

 ax=b (mod m)

is solvable iff the congruence

 b=0 (mod d)

with d=GCD(a,m) is the greatest common divisor is solvable. Let one solution to the original equation be x_0<m/d. Then the solutions are x=x_0, x_0+m/d, x_0+2m/d, ..., x_0+(d-1)m/d. If d=1, then there is only one solution <m.

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

 x=b/a (mod m),

which can also be written

 x/b=1/a (mod m).

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

Two or more simultaneous linear congruences

 x=a (mod m)
 x=b (mod n)

are solvable using the Chinese remainder theorem.

See also

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

Explore with Wolfram|Alpha


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.

Subject classifications