Bootstrap
  C.R.T. .com
It doesn't have to be difficult if someone just explains it right.

Welcome to ChineseRemainderTheorem.com!

×

Modal Header

Some text in the Modal Body

Some other text...

Use the calculator below to get a step-by-step calculation of the Chinese Remainder Theory. Just enter the numbers you would like and press "Calculate" .


This removes all numbers from the textboxes, such that you can fill in your own.

This fills all textboxes with random numbers. If you fill in random numbers yourself, it is very likely that those numbers do not have a solution. To avoid disappointment, use this button instead! It only uses random numbers that do have a solution.

This button is similar to the "Clear everything" button, but only clears the left column.
This is useful if you want your equations to be of the form x ≡ a (mod m) rather than bx ≡ a (mod m).
In that case, it can be especially useful after using the random numbers button.

Do you want to use more equations? Go ahead and use this button. It adds another row that you can fill in. Not sure what numbers to put in this newly added row? Use the random numbers button again!

Do you have too many rows? Use one of these buttons to remove a row. You can always add a row again using the yellow "Add a row" button.

Are you ready to view a full step-by-step Chinese Remainder Theorem calculation for the numbers you have entered? Then use this button!

Want to know more?


Transform the equations

You used one or more of the fields on the left, so your equations are of the form bx ≡ a mod m.
We want them to be of the form x ≡ a mod m, so we need to move the values on the left to the right side of the equation.
For a more detailed explanation about how this works, see this part of our page about how to execute the Chinese Remainder algorithm.

First, we calculate the inverses of the leftmost value on each row:

nbqr t1t2t3
4097180409010
7184091309101
409309110001-1
309100391-14
1009111-14-45
91904-45409
So our multiplicative inverse is -45 mod 409 ≡ 364
Source: ExtendedEuclideanAlgorithm.com

nbqr t1t2t3
76934222101-22
34211131-2223
211318-2223-45
1381523-4568
8513-4568-113
531268-113181
3211-113181-294
2120181-294769
So our multiplicative inverse is -294 mod 769 ≡ 475
Source: ExtendedEuclideanAlgorithm.com

nbqr t1t2t3
58316638501-3
166851811-34
858114-34-7
8142014-7144
4140-7144-583
So our multiplicative inverse is 144 mod 583 ≡ 144
Source: ExtendedEuclideanAlgorithm.com

Click on any row to reveal a more detailed calculation of each multiplicative inverse.

Now that we now the inverses, let's move the leftmost value on each row to the right of the equation:

x ≡ 791 × 718-1 (mod 409) ≡ 791 × 364 (mod 409) ≡ 397 (mod 409)
x ≡ 695 × 34-1 (mod 769) ≡ 695 × 475 (mod 769) ≡ 224 (mod 769)
x ≡ 129 × 166-1 (mod 583) ≡ 129 × 144 (mod 583) ≡ 503 (mod 583)


Now the actual calculation

  1. Find the common modulus M
    M = m1 × m2 × ... × mk = 409 × 769 × 583 = 183365743
  2. We calculate the numbers M1 to M3
    M1=M/m1=183365743/409=448327,   M2=M/m2=183365743/769=238447,   M3=M/m3=183365743/583=314521
  3. We now calculate the modular multiplicative inverses M1-1 to M3-1
    Have a look at the page that explains how to calculate modular multiplicative inverse.
    Using, for example, the Extended Euclidean Algorithm, we will find that:

    nbqr t1t2t3
    4094483270409010
    448327409109663101
    4096363101-6
    6331211-613
    311310-613-409
    So our multiplicative inverse is 13 mod 409 ≡ 13
    Source: ExtendedEuclideanAlgorithm.com

    nbqr t1t2t3
    7692384470769010
    23844776931057101
    76957132801-13
    5728211-1327
    281280-1327-769
    So our multiplicative inverse is 27 mod 769 ≡ 27
    Source: ExtendedEuclideanAlgorithm.com

    nbqr t1t2t3
    5833145210583010
    314521583539284101
    58328421501-2
    2841518141-237
    151411-237-39
    14114037-39583
    So our multiplicative inverse is -39 mod 583 ≡ 544
    Source: ExtendedEuclideanAlgorithm.com
  4. Now we can calculate x with the equation we saw earlier
    x = (a1 × M1 × M1-1   +   a2 × M2 × M2-1   + ... +   ak × Mk × Mk-1)   mod M
    =  (397 × 448327 × 13 +
       224 × 238447 × 27 +
       503 × 314521 × 544)   mod 183365743
    = 153105048 (mod 183365743)


    So our answer is 153105048 (mod 183365743).


Verification

So we found that x ≡ 153105048
If this is correct, then the following statements (i.e. the original equations) are true:
718x (mod 409) ≡ 791 (mod 409)
34x (mod 769) ≡ 695 (mod 769)
166x (mod 583) ≡ 129 (mod 583)

Let's see whether that's indeed the case if we use x ≡ 153105048.