How this calculation works
A common divisor of a and m must also divide b. When it does, divide all three values by that divisor, use the reduced coefficient inverse, then lift one solution into every residue class of the original modulus.
a·x ≡ b (mod m); solutions exist iff gcd(a,m) divides bA worked example
6x ≡ 8 (mod 14) has gcd 2, so reduce to 3x ≡ 4 (mod 7). Its solutions modulo 14 are 6 and 13.
Good to know
Whole non-negative a and b up to one billion and modulus 2 through one billion. The full solution count is exact; at most 20 residues are displayed when there are many.
Reference: MIT OpenCourseWare: Theory of Numbers lecture notes (opens in a new tab) ↗
A common divisor decides solvability
The equation 6x ≡ 8 (mod 14) is equivalent to asking when 6x−8 is a multiple of 14. Because gcd(6,14)=2 divides 8, solutions exist. If that gcd did not divide the right-hand side, no integer x could make the difference a multiple of the modulus.
Divide by the common divisor to obtain 3x ≡ 4 (mod 7). Three has inverse five modulo seven, so x ≡ 6 (mod 7). Within one full modulus 14, the two residues are 6 and 13.
The Chinese remainder theorem calculator combines two residue conditions, while this solver handles a coefficient times one unknown.
The result can describe more than one residue
A modular inverse exists for the coefficient precisely when it is coprime to the modulus. In that special case this solver reports one residue, which is why it can also solve a simple inverse question.
When the gcd is larger, the reduced equation has one residue class modulo the smaller modulus. Lifting it yields exactly gcd(a,m) different residues modulo the original modulus. The table shows at most twenty but the count remains exact.
Do not divide a congruence casually
Dividing a, b and m by a number that does not divide all three can change the solution set. First compute the gcd, then check whether it divides b. The gcd calculator can help inspect the same common-divisor relationship separately.
The Chinese remainder theorem calculator combines two congruences with different coprime moduli. It does not solve this coefficient equation for you; decide which form matches your problem first.
A few questions, answered
Why might there be no solution?
The gcd of the coefficient and modulus does not divide the requested remainder.
Are all integer solutions printed?
No. Integers repeat modulo m; the table lists distinct residues in one modulus, capped at twenty.
What if a is zero?
Either every residue solves 0x ≡ 0, or none solve 0x ≡ b when b is not divisible by the modulus.