A linear congruence equation

(1)

is solvable iff the congruence

(2)

is solvable, where is the greatest common divisor. Let one solution to the original equation be . Then the solutions are , , , ..., . If d = 1, then there is only one solution . The solution of a linear congruence can be found in Mathematica 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 x can be found as Mod[b y, m] of the solution y returned by the Mathematica command y=PowerMod[a, -1, 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

search