Smallest solution
Modulus
Moduli

    Equations

    More about the Chinese remainder theorem

    Chinese remainder theorem solver

    Count a pile of things by threes and 2 are left over, by fives and 3 are left, by sevens and 2 are left: there are 23 of them, or 128, or 233, one answer every 105. That is the problem from the Sunzi Suanjing that gave the Chinese remainder theorem its name. Type any system of congruences x ≡ a (mod n), with as many equations and as large numbers as you like, and see the answer, the working with your numbers and a picture of why it works. When the equations cannot all hold, the solver names the two that clash and shows why. Type the equations x ≡ a (mod n), one per row: a is the remainder and n the modulus. Add a row with Add equation, or press Enter in the last modulus, and remove one with ×. Whole numbers of up to 200 digits work, and a may be negative. Or choose a worked example. The tiles show the smallest solution and how often it repeats; below them are the first positive solutions and a check of every equation. The picture marks the numbers that satisfy each equation, and the column where every row has a mark is the solution; the remainder table shows two equations at once. The working is written out with your numbers, by the textbook construction or by substitution.

    How it works

    1. Type the equations x ≡ a (mod n), one per row, or pick a worked example such as Sunzi's problem, the basket of eggs or the Julian Period.
    2. Read the smallest solution, the modulus it repeats with and the first positive solutions, each checked against every equation.
    3. Follow the working step by step, by the construction or by substitution, and switch the picture between the number line and the remainder table.

    How the construction works

    When no two moduli share a factor, the solution can be built directly. Multiply the moduli: for Sunzi's problem N = 3 × 5 × 7 = 105. For each equation take Nᵢ = N / nᵢ, a multiple of every other modulus: 35, 21 and 15. Then find the inverse yᵢ of Nᵢ mod nᵢ with the extended Euclidean algorithm: 35 leaves 2 when divided by 3, and 2 × 2 = 4 ≡ 1 (mod 3), so y₁ = 2; 21 and 15 leave 1, so their inverses are 1. Now x = 2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1 = 233, and 233 mod 105 = 23. Each term fits its own equation and is a multiple of the other moduli, so the sum fits them all.

    When the moduli share a factor

    A system whose moduli share factors can still have a solution. Two equations x ≡ a (mod m) and x ≡ b (mod n) can both hold exactly when a − b is a multiple of gcd(m, n), and the solution then repeats every lcm(m, n) instead of every m × n. Two buses that leave at minutes 5 and 11, every 12 and every 18 minutes, meet at minute 29 and every 36 minutes after that, because 11 − 5 = 6 is a multiple of gcd(12, 18) = 6. But x ≡ 1 (mod 4) and x ≡ 4 (mod 6) can never both hold: the first makes x odd and the second makes it even. A whole system has a solution exactly when every pair of its equations has one, and that is how the solver finds the two that clash.

    Frequently asked questions

    What does the Chinese remainder theorem say?

    If no two of the moduli n₁, n₂, … have a common factor, then for any remainders a₁, a₂, … there is exactly one x from 0 to N − 1 with x ≡ aᵢ (mod nᵢ) for every i, where N is the product of the moduli. Every other solution differs from it by a multiple of N: for Sunzi's problem the solutions are 23, 128, 233 and so on, one every 105.

    Why is it called Chinese?

    The oldest known problem of this kind is in the Sunzi Suanjing, a Chinese arithmetic book written between the 3rd and 5th centuries: counted by threes, fives and sevens, a number of things leaves 2, 3 and 2. Qin Jiushao gave a general method for such problems in 1247, and Carl Friedrich Gauss stated the theorem in its modern form in 1801.

    What if the moduli are not coprime?

    Then there may be no solution, and when there is one, it repeats every least common multiple of the moduli instead of every product. Two equations agree when their remainders are the same mod the gcd of their moduli. The egg puzzle uses 2, 3, 4, 5, 6 and 7, which share factors, and still has a solution: 301, repeating every 420.

    How does RSA use the Chinese remainder theorem?

    Decrypting an RSA message means computing c^d mod n, where n = p × q. It is faster to compute c^d mod p and c^d mod q separately, with the exponent reduced mod p − 1 and q − 1, and to join the two results with the theorem. With numbers half as long, each of the two powers takes about an eighth of the work, so decryption is about four times faster, and most RSA software does it this way.

    How large can the numbers be?

    Up to 20 equations, with numbers of up to 200 digits each. The solver works with exact whole numbers in your browser, so the answer is exact however long it is, and nothing is sent anywhere.

    Ready to try it?

    Open PictorX in your browser — no install, no credit card required to start.

    Go to Editor