Modular arithmetic
Solve linear congruence equations
Enter the coefficients of ax ≡ b (mod m) and get more than just the solution: the full procedure, including the greatest common divisor, a solvability check, the modular inverse and the family of solutions.
Go to the solverCalculation
Solve your equation
Enter the coefficients and press "Solve" to see the procedure.
Fundamentals
What is a congruence equation?
A linear congruence equation modulo m is defined as an equation of the form
with a, b ∈ ℤ and m ≥ 2.
Solvability condition
The equation has a solution if and only if gcd(a, m) divides b. In that case, it has exactly d = gcd(a, m) distinct solutions modulo m.
Structure of the solutions
If x₀ is a solution, all and only the solutions have the form x ≡ x₀ (mod m/d), i.e. x₀ + k·(m/d) for k = 0, 1, …, d−1.
Download the theory as PDFVideo lesson
A video explanation of the procedure, on the same YouTube channel.