Congruence Solver and the Chinese Remainder Theorem

After reading this you can solve any single linear congruence ax \equiv b \pmod{m}, count how many solutions it has, and stitch several congruences into one using the Chinese Remainder Theorem.

What a congruence solver does

A congruence ax \equiv b \pmod{m} asks: for which integers x does ax leave the same remainder as b when divided by m? It is an equation, but instead of one answer it usually has a whole family of answers spaced m apart, or a subfamily spaced more widely.

Here is a quick hook. Solve 6x \equiv 4 \pmod{10}. Try each residue from 0 to 9. You find 6 \cdot 4 = 24 \equiv 4 and 6 \cdot 9 = 54 \equiv 4. So x = 4 and x = 9 both work, and every integer congruent to those mod 10 works too. That is two solution classes, not one, and the solver reports both.

The second job is systems. Given several conditions like "remainder 2 mod 3, remainder 3 mod 5, remainder 2 mod 7", the Chinese Remainder Theorem (CRT) combines them into a single congruence with a single answer mod the product of the moduli.

When to use it, and when not

Use the linear mode when you have exactly one modular equation and want every x that satisfies it. Use the CRT mode when you have several remainder facts about the same unknown, one per modulus, and you want the unknown itself.

Two limits are worth stating up front. First, a linear congruence has a solution only when \gcd(a, m) divides b. If it does not, there is no x at all. Second, the clean version of CRT needs the moduli to be pairwise coprime. When they share factors, a solution may still exist, but only if the overlapping conditions agree.

The formula and the intuition

Let g = \gcd(a, m). The congruence ax \equiv b \pmod{m} behaves in exactly one of these ways.

Here g \nmid b means g does not divide b. When g does divide b, reduce the whole congruence by g:

Now a/g and m/g are coprime, so a/g has a modular inverse. Multiply by it to get one base solution x_0. The full set of classes mod m is then

The intuition: dividing by g shrinks the problem to a coprime one that always has a unique inverse. Lifting back up spreads that single answer into g equally spaced classes across the original modulus. In the hook example g = \gcd(6,10) = 2 divides 4, so you get 2 classes, 4 and 9, spaced m/g = 5 apart.

The Chinese Remainder Theorem

Suppose you want x with x \equiv r_i \pmod{m_i} for several moduli that are pairwise coprime. Let M = m_1 m_2 \cdots m_n. Then a unique solution exists mod M, and you can build it directly.

Read the pieces: M_i is the product of all moduli except m_i, so it is divisible by every other modulus and leaves the i-th condition free to be set. The inverse y_i tunes M_i so that M_i y_i \equiv 1 \pmod{m_i}. Each term contributes the correct remainder in its own modulus and contributes 0 in all the others.

Worked example: reproducing the demo

Reading and interpreting the results

For a linear congruence, the number that matters most is the count of solution classes, which equals \gcd(a, m) when a solution exists. The table below shows how the same right side can produce a different number of classes depending on a and m.

Notice the pattern. When g = 1, there is exactly one class, the tidy case. When g grows and still divides b, the classes multiply and sit m/g apart. When g does not divide b, the answer set is empty, as in the third row where 4 does not divide 6.

For a CRT system, the result is a single class x \equiv x_0 \pmod{M}. Read x_0 as the smallest nonnegative solution and M as the period at which solutions repeat. In the demo, x_0 = 23 and M = 105, so the full solution set is \{23, 128, 233, \dots\} and their negatives.

Common mistakes

The errors below account for most wrong answers.

Reporting one solution when there are several

If \gcd(a, m) = g \gt 1 and it divides b, you get g classes, not one. For 6x \equiv 4 \pmod{10} the answers are both 4 and 9.

Forcing an inverse that does not exist

You can only "divide by a" when \gcd(a, m) = 1. When it is not 1, reduce by g first, then invert.

Applying CRT to non-coprime moduli blindly

The formula above assumes pairwise coprime moduli. For moduli like 6 and 4 (shared factor 2), a solution exists only if the two conditions agree mod \gcd(6,4) = 2.

Skipping verification

Always substitute the reported x back into every original congruence. A single arithmetic slip in an inverse is easy to catch this way.

Related tools

Congruence problems sit next to several other discrete topics on this site. The Prime Number Tools help you factor a modulus and confirm which moduli are coprime, which is the first thing CRT needs. The Base-N Arithmetic page is handy when a modulus is a power of a base and you want to read remainders straight off digits. For logic problems rather than number problems, the Truth Table Generator and the Set Calculator cover the neighboring ground.

Related tools

Truth Table Generator

Full truth tables plus DNF/CNF simplification.

Prime Number Tools

Primality tests, the nth prime, prime ranges and π(x).

Set Calculator

Union, intersection, differences and power sets.

Base-N Arithmetic

Add, subtract, multiply and divide directly in any base.

Linear Diophantine Equations

Integer solutions of ax + by = c with the general formula.

3D Solid Geometry Calculator

Volume and surface area of spheres, cones, prisms and more.