← All text tools

Chinese remainder theorem calculator

Solve a system of congruences x = a mod n and get the smallest solution with the working, even when the moduli share factors.

  • Free
  • No sign-up
  • Works on any device

About Chinese remainder theorem calculator

The Chinese remainder theorem finds a number x that leaves given remainders on division by several moduli, for example x = 2 mod 3, x = 3 mod 5, x = 2 mod 7, which gives x = 23 mod 105. When the moduli are pairwise coprime the page builds the classic table of N_i = N / n_i and inverses y_i. When they share factors it merges the congruences two at a time using the greatest common divisor, or reports that no solution exists. Every answer is verified against each original congruence.

How to use Chinese remainder theorem calculator

  1. Write one congruence per line, as the remainder followed by the modulus, like 2 mod 3.
  2. Read the smallest non-negative solution and the modulus it repeats with.
  3. Study the working table, and check the verification line to confirm each remainder.

Why use this tool?

Also known as

Frequently asked questions

Do the moduli have to be coprime?

The simple formula needs pairwise coprime moduli. This page also handles other cases: a solution exists only when the remainders agree modulo the common factor of each pair.

How are the inverses y_i found?

y_i is the number that makes N_i x y_i leave remainder 1 modulo n_i. It is found with the extended Euclidean algorithm, and the table lists each one.

What does the answer x = 23 mod 105 mean?

Every number of the form 23 + 105t, for any whole t, satisfies all the congruences. 23 is the smallest non-negative one.

Is Chinese remainder theorem calculator free?

Yes. Chinese remainder theorem calculator on Toolipedia is free to use, with no sign-up and no watermark.

Is it safe to use?

Yes. Everything is worked out in your browser, and nothing you enter is sent to our server.

Does it work on my phone?

Yes. It works in any modern browser on Android and iPhone, as well as on tablets and computers. There's nothing to install.

Do I need an account?

No. Just open the page and use the tool. There's no sign-up and no email needed.

Can I put Chinese remainder theorem calculator on my own website?

Yes. Use the Embed on your site button under the tool to copy a short piece of code and paste it into your page. It is free, needs no account, and the tool keeps working inside your page.

Related tools