Congruence solver: modular equations step by step

Linear congruences, systems by the Chinese remainder theorem, remainders of large powers and modular inverses, with step-by-step working and a check.

Examples: 3x ≡ 4 (mod 7) x ≡ 2 (mod 3); x ≡ 3 (mod 5); x ≡ 2 (mod 7) 3^100 mod 7 17^-1 mod 43 6x ≡ 4 (mod 10) x^2 ≡ 4 (mod 15) 123456789 mod 9

Loading the solver…

What you can type

A congruence of the first degree: 3x ≡ 4 (mod 7), including with the unknown on both sides: 5x + 3 ≡ 2x − 1 (mod 11).
A system, separated by semicolons or new lines: x ≡ 2 (mod 3); x ≡ 3 (mod 5).
The remainder of a power or an expression: 3^100 mod 7, (2^10 + 3^5) mod 7, 123456789 mod 9.
A modular inverse: 17^-1 mod 43 or inverse of 17 modulo 43.
A congruence of higher degree: x^2 ≡ 4 (mod 15), which the solver handles by trying every remainder (for moduli up to $20{,}000$).

The sign $\equiv$ can be replaced by an ordinary “$=$”, and “$(\mathrm{mod}\ 7)$” by the words “mod 7” or “modulo 7”. On a phone, the symbols are on the buttons under the field.

What a congruence is

The statement $a \equiv b \pmod m$ is read “$a$ is congruent to $b$ modulo $m$” and means that $a$ and $b$ leave the same remainder when divided by $m$, or, equivalently, that their difference is divisible by $m$. So $17 \equiv 5 \pmod 6$: both numbers leave remainder $5$, and $17 - 5 = 12$ is divisible by $6$. Gauss introduced the notation in his Disquisitiones Arithmeticae (1801).

It helps to think of a clock face with $m$ marks: numbers congruent modulo $m$ land on the same mark. A clock is arithmetic modulo $12$: fifteen hours after nine o’clock it will be $9 + 15 = 24 \equiv 0$, that is, midnight or noon again.

You can handle congruences almost like equations: add the same thing to both sides, multiply both sides by the same thing, replace any number by its remainder. “Almost”, because you can’t always divide both sides. That’s the main trap, discussed below.

How to solve $ax \equiv b \pmod m$

Move everything with the unknown to the left and the numbers to the right, and replace the coefficients by their remainders: you get $ax \equiv b \pmod m$.
Find $d = \gcd(a, m)$ by Euclid’s algorithm.
If $b$ isn’t divisible by $d$, there are no solutions.
If it is, divide everything by $d$ at once: $a$, $b$ and the modulus. Now the coefficient is coprime to the modulus.
Multiply both sides by the inverse of the coefficient, found by running Euclid’s algorithm backwards.

The GCD of the coefficient and the modulus. Everything that can be written as $ax - km$ is divisible by $d$.

The right-hand side. If $d \mid b$, there are exactly $d$ solutions modulo $m$: one solution $x_0$ modulo $m/d$ and its shifts $x_0 + \frac{m}{d}k$.

Example: $6x \equiv 4 \pmod{10}$. $\gcd(6, 10) = 2$, and $2 \mid 4$, so solutions exist. Divide everything by $2$: $3x \equiv 2 \pmod 5$. The inverse of $3$ modulo $5$ is $2$ ($3 \cdot 2 = 6 \equiv 1$), so $x \equiv 2 \cdot 2 = 4 \pmod 5$. Modulo $10$ that’s two solutions: $4$ and $9$. But $6x \equiv 5 \pmod{10}$ has no solutions: $6x - 10k$ is always even.

The inverse of $a$ modulo $m$ is a number $a^{-1}$ such that $a \cdot a^{-1} \equiv 1 \pmod m$. It exists exactly when $\gcd(a, m) = 1$, and it comes from Bézout’s identity: if $ax + my = 1$, then $ax \equiv 1$ and $x$ is the inverse. Multiplying by the inverse is the same as dividing by $a$; that’s why modulo a prime you can divide by anything except zero.

Systems: the Chinese remainder theorem

The treatise “Sunzi Suanjing” (3rd–5th century) has this problem: a number leaves remainder $2$ when divided by $3$, remainder $3$ when divided by $5$, and remainder $2$ when divided by $7$; find it. The answer is $23$, and there are no others, apart from numbers that differ from it by a multiple of $105$.

Coprime moduli. Then there’s a solution for any remainders $r_1$, $r_2$.

The unique solution from $0$ to $m_1 m_2 - 1$. The solver finds it by substitution: from the first congruence $x = r_1 + m_1 t$; substitute into the second and solve the linear congruence for $t$.

The new modulus. If the moduli aren’t coprime, the system isn’t always solvable, and the modulus of the answer is their LCM rather than their product.

Example: $x \equiv 2 \pmod 3$, $x \equiv 3 \pmod 5$. From the first, $x = 2 + 3t$. In the second: $2 + 3t \equiv 3$, that is, $3t \equiv 1 \pmod 5$, so $t \equiv 2$. Then $x = 2 + 3 \cdot 2 = 8$, and $x \equiv 8 \pmod{15}$.

With three or more congruences it’s the same: merge the first two into one, then add the third. The solver’s picture for two congruences is a “Chinese table”: the number $n$ sits in the row of its remainder modulo $m_1$ and the column of its remainder modulo $m_2$. When the moduli are coprime, every cell holds exactly one number, and that is the theorem.

Remainders of large powers

The number $3^{100}$ has $48$ digits, yet its remainder on division by $7$ can be found in your head. There are two tools.

Fermat’s little theorem (1640; the first published proof is Euler’s, 1736): if $p$ is prime and $a$ isn’t divisible by it, then $a^{p-1} \equiv 1 \pmod p$. Modulo $7$ we have $3^6 \equiv 1$, and $100 = 6 \cdot 16 + 4$, so $3^{100} = (3^6)^{16} \cdot 3^4 \equiv 3^4 = 81 \equiv 4$. For a composite modulus, $p - 1$ is replaced by Euler’s totient $\varphi(m)$, the number of integers from $1$ to $m$ that are coprime to $m$.

Fast exponentiation: write the exponent in binary, $100 = 64 + 32 + 4$, compute $a, a^2, a^4, a^8, \ldots$, each as the square of the one before, taking remainders at once, and multiply the ones you need. Instead of $99$ multiplications, six squarings and two multiplications are enough. This is how computers raise numbers to powers with exponents hundreds of digits long, and it’s what the RSA cipher runs on.

Worked examples

Example 1. $3x \equiv 4 \pmod 7$

$\gcd(3, 7) = 1$, so there’s one solution. The inverse of $3$ modulo $7$: $3 \cdot 5 = 15 = 2 \cdot 7 + 1$, so $3^{-1} \equiv 5$. Multiply both sides by $5$: $x \equiv 4 \cdot 5 = 20 \equiv 6 \pmod 7$.

Check: $3 \cdot 6 = 18 = 2 \cdot 7 + 4$. All the solutions are $x = 6 + 7k$: $\ldots, -1, 6, 13, 20, \ldots$

Example 2. Sunzi’s problem

$x \equiv 2 \pmod 3$, $x \equiv 3 \pmod 5$, $x \equiv 2 \pmod 7$. The first two congruences give $x \equiv 8 \pmod{15}$ (see above). Now $x = 8 + 15s$ and $8 + 15s \equiv 2 \pmod 7$. Since $15 \equiv 1$, we get $s \equiv 2 - 8 = -6 \equiv 1 \pmod 7$. So $x = 8 + 15 = 23$, and $x \equiv 23 \pmod{105}$.

Check: $23 = 3 \cdot 7 + 2 = 5 \cdot 4 + 3 = 7 \cdot 3 + 2$.

Example 3. The inverse of 17 modulo 43

Euclid’s algorithm: $43 = 2 \cdot 17 + 9$, $17 = 1 \cdot 9 + 8$, $9 = 1 \cdot 8 + 1$. Going backwards:

$$1 = 9 - 8 = 9 - (17 - 9) = 2 \cdot 9 - 17 = 2(43 - 2 \cdot 17) - 17 = 2 \cdot 43 - 5 \cdot 17.$$

So $17 \cdot (-5) \equiv 1 \pmod{43}$, and $17^{-1} \equiv -5 \equiv 38$. Check: $17 \cdot 38 = 646 = 15 \cdot 43 + 1$.

Example 4. $x^2 \equiv 4 \pmod{15}$

There’s no formula here like the one for linear congruences, so we try the remainders from $0$ to $14$: $x^2 \bmod 15$ equals $4$ for $x = 2, 7, 8, 13$. Four solutions to a quadratic congruence isn’t a mistake: the modulus is composite, the congruence has two solutions modulo $3$ and two modulo $5$ ($x \equiv \pm 2$), and the Chinese remainder theorem combines them in $2 \cdot 2 = 4$ ways. Modulo a prime, a congruence of degree $n$ has at most $n$ solutions.

Common mistakes

Dividing both sides without touching the modulus. $2x \equiv 2 \pmod 4$ does not give $x \equiv 1 \pmod 4$: the solution $x = 3$ is lost. If the common factor also divides the modulus, divide the modulus too: $x \equiv 1 \pmod 2$.
Dividing by a number not coprime to the modulus. Modulo $10$ you can’t “divide” by $6$: $6 \cdot 2 \equiv 6 \cdot 7 \equiv 2$, although $2 \not\equiv 7$. First divide by the GCD, then multiply by the inverse.
Reducing the exponent by the modulus. $3^{100} \bmod 7$ is not $3^{100 \bmod 7} = 3^2$. The exponent is reduced modulo $p - 1$ (or $\varphi(m)$), not modulo $m$, and only if the base is coprime to the modulus.
Leaving a negative remainder. $-7 \bmod 3 = 2$, because $-7 = 3 \cdot (-3) + 2$. A remainder modulo $m$ is always taken from $0$ to $m - 1$ (calculators and programming languages sometimes disagree here).
Taking the product of the moduli in a system when they aren’t coprime. For $x \equiv 1 \pmod 4$, $x \equiv 3 \pmod 6$ the answer is $x \equiv 9 \pmod{12}$, not modulo $24$; and the system $x \equiv 1 \pmod 4$, $x \equiv 2 \pmod 6$ has no solutions at all: the first demands an odd $x$, the second an even one.
Looking for an inverse that doesn’t exist. $6$ has no inverse modulo $9$: $6x$ is always divisible by $3$ and can’t leave remainder $1$.