Zahri-Edu University

Equation Solver › Number theory

solver.zahri-edu.net

Modular equations and the Chinese remainder theorem

ax ≡ b (mod n)

Linear congruences ax ≡ b (mod n) with all solutions, and systems of congruences by the Chinese remainder theorem.

Problem
Linear congruence a x ≡ b (mod n)
System of congruences

Used when “System of congruences” is chosen.

Press Solve.

Method

For ax ≡ b (mod n), let g = gcd(a, n). Solutions exist iff g | b; then they form g classes modulo n, found from the modular inverse of a/g modulo n/g. For a system, the congruences are merged one by one with the extended Euclidean algorithm; this works even when the moduli are not pairwise coprime, giving a solution modulo their least common multiple, or reporting that none exists.

Computed in your browser with double-precision arithmetic; nothing is sent to a server. Check results by substituting them back.

Other solvers