Calculators
Linear Congruence Calculator
Solve ax ≡ b (mod m) with exact integer arithmetic, including all solutions and cases with no solution, privately in your browser.
Solve ax ≡ b (mod m). Enter signed integers a and b and a positive modulus m, each up to 100 digits. Calculations stay in your browser.
How to solve a linear congruence
A linear congruence ax ≡ b (mod m) asks which integers x make ax and b have the same remainder modulo m. Let d = gcd(a, m). Solutions exist exactly when d divides b. The extended Euclidean algorithm finds a coefficient t such that at ≡ d (mod m). A solution is x₀ = t(b/d) reduced modulo m/d, and all integer solutions are x = x₀ + (m/d)k. There are d distinct solution residues modulo m. For example, 6x ≡ 8 (mod 14) gives x = 6 + 7k, with residues 6 and 13 modulo 14. In contrast, 6x ≡ 5 (mod 14) has no solution. If a is zero, every integer works when m divides b; otherwise none do. Modulus 1 accepts every integer. Enter up to 100 digits per input with optional minus signs for a and b; m must be positive. Leading zeros and surrounding whitespace are accepted; plus signs, decimal points, separators and scientific notation are rejected. Browser BigInt arithmetic preserves every digit without uploading or storing inputs. Large solution sets are shown as a formula rather than enumerated.
Frequently Asked Questions
Everything you need to know about this tool, how it works, and privacy.
When does a linear congruence have a solution?
Exactly when gcd(a, m) divides b. Otherwise no integer x satisfies the congruence.
How many solutions are there?
If solutions exist, there are gcd(a, m) distinct residues modulo m. All integer solutions differ by multiples of m/gcd(a, m).
Can a or b be negative or zero?
Yes. Both may be signed integers or zero. For a = 0 every integer works if m divides b; otherwise there are no solutions. Modulus 1 always accepts every integer.
Are large results exact and private?
Yes. Browser BigInt arithmetic supports up to 100 digits per input without uploads. Results use a formula so very large solution sets do not need to be listed.