Linear Congruence Solver
Solve linear congruences of the form ax ≡ b (mod m) quickly and easily with our interactive solver. Understand solutions and modular arithmetic concepts.
Solution
Understanding Linear Congruence
A linear congruence is a congruence relation of the form $$ax \equiv b \pmod{m}$$, where a, b, and m are integers, and x is a variable. Solving a linear congruence means finding all integer values of x that satisfy this relation.
Key Concepts:
- Modulus (m): The integer m is called the modulus. The congruence is 'modulo m'.
- Solutions: A linear congruence may have no solutions, one solution modulo m, or multiple solutions modulo m. The number of solutions depends on the greatest common divisor (gcd) of a and m.
- GCD Condition: A solution exists if and only if the gcd(a, m) divides b. If it does, there are gcd(a, m) incongruent solutions modulo m.
Formula for Solutions: If a solution exists, and $$d = gcd(a, m)$$, then the solutions are given by: $$ x \equiv x_0 + k \cdot rac{m}{d} \pmod{m} $$ where $$x_0$$ is a particular solution, and $$k = 0, 1, 2, ..., d-1$$.
This tool helps you quickly find these solutions. Enter the coefficients a, b, and the modulus m to get the results.
Learn more about linear congruence at Wikipedia.