Chinese Remainder Theorem Calculator

Welcome to Omni's Chinese remainder theorem calculator, where we'll study (surprise, surprise) the Chinese remainder theorem. In essence, the statement tells us that it is always possible to find a unique (in some sense) solution to a set of remainder equations, also called congruences. It is closely related to the Euclidean algorithm and Bézout's identity, which are essential in proving the Chinese remainder theorem and used in examples. Don't worry; we'll get to the latter as well.

First, however, let's start slow and dedicate the first section to the basics.

You know how all of mathematics deals with numbers? Well, apparently not. The big-headed mathematicians figure out more and more ways to analyze and describe things from their wildest imaginations, and more often than not, you don't see any digits in the formulas they're proving.

Number theory is the last island on this vast sea of unrecognizable symbols. It is a field of mathematics that concerns itself with integers, i.e., numbers like 0, 1, 42, or -273. That's right – it doesn't even bother with fractions! It seems like a pretty narrow field, doesn't it? Surely, they must have discovered everything there was to it by now, right?

Well, we encourage you to google the Riemann conjecture to see how far mathematicians can go when left to themselves.

Anyway, we don't need to trouble ourselves with such high mathematics today. What we will need, though, is one of the basic number-theoretic operations: modulo. However, before we define it, let's recall the definition of a remainder.

The remainder of a divided by b is the integer r between 0 and b-1, which remains as the extra "undivided" part (the one that would give a fraction) from the operation. Symbolically speaking, it must satisfy the equation:

a = k·b + r

with k some integer.

For instance, if we wish to divide 17 by 5, we know that we can fit three 5-s in 17, and we'll have 2 left standing. The 2 is the remainder. We then have 17 = 3·5 + 2.

Now, we're ready to define the modulo operation (see modulo calculator).

Equivalently, we can say that a is congruent to b mod n. There is no difference between the two statements; they're just different name variants. We can write the relation symbolically like so:

a ≡ b (mod n)

We call such expressions congruences. They prove extremely handy because, in many respects, they behave like ordinary equations. For instance, we can add or subtract any number from both sides or multiply (but not divide, mind you!) by an arbitrary integer.

The Chinese remainder theorem deals with a set (or system) of congruences that describe an unknown variable. We'll see the statement soon enough, but for now, let's just say that it allows us to solve such problems and gives a straightforward algorithm on how to do it. However, to get a good grip on the concept, we'll first need to go through its two main ingredients: the Euclidean gcd algorithm and Bézout's identity.

The Euclidean gcd algorithm is a sequence of operations that lets you find the greatest common divisor (see GCF calculator) (sometimes called the greatest common factor) of two numbers. Let's go through it step by step.

Say that you have two integers: x and y, and say that x > y. To find their gcd, we'll define four sequences a_n, b_n, k_n, and r_n. As the starting point, we take a₁ = x and b₁ = y. Also, let n = 1, and from now on, we will follow the instructions below.

1. Define k_n to be the largest integer multiple of b_n that is smaller or equal to a_n (i.e., the floor of a_n / b_n).

2. Let r_n be the remainder of the division a_n / b_n (i.e., r_n = a_n − k_n·b_n).

3. If r_n = 0, the algorithm finishes and b_n = gcd(x,y). If not, set a_n+1 = b_n and b_n+1 = r_n, and repeat from point 1. with n increased by 1.

At each step of the algorithm, we have:

a_n = k_n·b_n + r_n

which will be a crucial property in a minute. However, before we move on, let's see the algorithm in practice.

We'll try to find gcd(1785, 546). First of all, let's see how the consecutive elements of the sequences look in our case.

We can translate each row into an equation a_n = k_n·b_n + r_n for corresponding n-s:

1785 = 3·546 + 147

546 = 3·147 + 105

147 = 1·105 + 42

105 = 2·42 + 21

42 = 2·21 + 0

In the fifth step, we got r₅ = 0, so gcd(1785,546) = b₅ = 21.

The algorithm is useful in itself as a tool for finding the greatest common divisor of two numbers. However, it also proves helpful when seeking other mathematical properties, such as Bézout's identity.

Bézout's identity (also called Bézout's lemma; not to be confused with Bézout's theorem, which deals with dividing polynomials (cf. polynomial division calculator) is a small theorem that lets us connect two numbers using their gcd. Instead of going into detail, let's see the statement itself.

💡 If a and b are non-zero, then there exist integers k and l such that k·a + l·b = gcd(a,b).

Hopefully, the symbols are explanatory in themselves. Still, as an example, let's see how to find such k and l for a = 1785 and b = 546. We'll use the Euclidean gcd algorithm that we've calculated in the previous section. In particular, the five equations we wrote under the table will prove most helpful.

First, let's take the second to last one and move the 2·42 to the left side. That gives:

21 = 105 - 2·42

Note how we don't multiply the numbers; we leave them be.

Next, we take the equation above the previously used one and similarly, move the 1·105 to the left:

42 = 147 - 1·105

Now, we substitute that in the previous equation:

21 = 105 - 2·42 = 105 - 2·(147 - 1·105) = 105 - 2·147 + 2·105 = -2·147 + 3·105

We repeat the moving and substitution for the next equation:

105 = 546 - 3·147

21 = -2·147 + 3·105 = -2·147 + 3·(546 - 3·147) = 3·546 - 11·147

and for the last:

147 = 1785 - 3·546

21 = 3·546 - 11·147 = 3·546 - 11·(1785 - 3·546) = -11·1785 + 36·546

All in all, we obtain -11·1785 + 36·546 = 21, so we have the form mentioned in Bézout's identity with k = -11 and l = 36.

Note how even though a and b were positive, the numbers k and l need not be. Also, there may be nothing too complicated in terms of calculations here. Still, arguably, the process is tricky in itself, and there are more than enough places where we can make mistakes. And we don't want that to happen, do we?

It may seem like we've spent ages on two mathematical algorithms, and yet, there's still one more to go: the infamous Chinese remainder theorem. We hope you're ready for some more fancy mathematics because here it comes!

The Chinese remainder theorem gathers all that we've learned in today's article: the modulo operation, congruent expressions, the Euclidean gcd algorithm, and Bézout's identity. But all that comes in applying the theorem, so why don't we start with the statement?

💡 Let n₁, n₂, ...,n_k be pairwise coprime positive integers (i.e., the gcd of every pair is 1). Then for any integers a₁, a₂, ...,a_k the set of congruences x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂), ..., x ≡ a_k (mod n_k) has a unique solution modulo n₁·n₂·...·n_k.

Now let's translate from brainy to common language.

The Chinese remainder theorem states that whenever we have an unknown number, but we know its remainders when divided by a few coprime integers, we can find what that number is.

The next section is all about the Chinese remainder theorem in examples, but before we see how to handle numeric exercises, let's go through the general case.

Suppose that we have k congruent expressions:

x ≡ a₁ (mod n₁)

x ≡ a₂ (mod n₂)

⋮

x ≡ a_k (mod n_k)

To find x, we follow the steps below.

1. Define N = n₁·n₂·...·n_k and let m₁ = N / n₁, m₂ = N / n₂, ..., m_k = N / n_k.

2. Use Bézout's identity to find pairs (u₁,v₁), (u₂,v₂), ..., (u_k,v_k) such that u₁·n₁ + v₁·m₁ = 1, u₂·n₂ + v₂·m₂ = 1, ... , u₁·n₁ + v_k·m_k = 1. (Note that the 1-s are, in fact, the GCDs of n-s and m-s. This is because, in the theorem, we assumed n-s to be coprime.)

3. Define e₁ = v₁·m₁, e₂ = v₂·m₂, ..., eₖ = _k·m_k. (Observe that by point 2., we have e₁ ≡ 1 (mod n₁), e₂ ≡ 1 (mod n₂), ... , e_k ≡ 1 (mod nₖ). Such numbers v_n and mₙ are often called mutual modulo inverses.)

4. The solution is x = a₁·e₁ + a₂·e₂ + ... + a_k·e_k modulo N.

On the one hand, we see that finding the answer boils down to following only four steps. On the other, we've seen in the previous section that point 2. is, in general, no walk in the park. Especially if we have many equations (i.e., congruent expressions) to begin with.

Alright, we officially declare the end of theory for this article! *audible sigh of relief*

With all this time spent with definitions, formulas, and algorithms, we believe it's high time we see a full-out Chinese remainder theorem example, don't you think?

Say that your mom bought a few handfuls of sweets and would like to give them away to you and your three siblings. However, she knows all too well how her children hate when we give one more than the others, so she quickly counts the candies.

Oh, bother! If all kids got the same number, there would be one sweet left. She figures that she could invite the little girl next door, but then after dividing, there would be two left. And if she invited both the girl and her big brother to raise the blood sugar of the whole lot, there would be three left. Oh, how troublesome!

So how many candies did she buy?

Let's see how we can translate this very real-life scenario into mathematical language. More precisely, we'll use congruences, and, as you might have guessed, our Chinese remainder theorem calculator will come in handy.

Denote the number of candies by x. Firstly, the mother realized that if she gave her three children an equal number of sweets, one would be leftover. This means that if we divide x by 3, we'll obtain a remainder of 1. In other words, x must be congruent to 1 modulo 3, i.e.,

x ≡ 1 (mod 3)

Next, if she invited the girl next door, then if she gave the candies to the four children, two will be left. This gives:

x ≡ 2 (mod 4)

Lastly, if the girl's brother joined in the game (amounting to five kids in total), three candies would be left. Therefore,

x ≡ 3 (mod 5)

This way, we've obtained a system of three congruences. It's starting to look similar to what we had in the above section, doesn't it?

First of all, let's see how easy the task is when we have Omni's Chinese remainder theorem calculator. There, we begin by choosing the right option under "Number of equations" (in our case, it's 3). The calculator will show you three congruent expressions with the symbols that we use in the fields below. For instance, the first one is

x ≡ a₁ (mod n₁)

We look back at the equations we had and input accordingly:

a₁ = 1, n₁ = 3

Similarly, for the other two congruences, we get:

a₂ = 2, n₂ = 4

a₃ = 3, n₃ = 5

Once we give the last number, the Chinese remainder theorem calculator will spit out the answer underneath. Also, note that if the input numbers didn't meet the assumptions of the theorem (e.g., if the n-s weren't coprime or if any of the numbers were a decimal fraction), the tool would inform you of the error.

We all know that you're super curious about how many candies mom bought, but we need you to be a bit more patient. After all, we didn't read through this whole article just to learn how to input digits into the Chinese remainder theorem calculator. We learned how to use the theorem ourselves, and use it we will right now!

Recall the instructions given in the above section. They tell us to begin by defining the numbers N and m₁, m₂, and m₃. We use the formulas and get:

N = n₁·n₂·n₃ = 3·4·5 = 60

m₁ = N / n₁ = 60 / 3 = 20

m₂ = N / n₂ = 60 / 4 = 15

m₃ = N / n₃ = 60 / 5 = 12

Next, we'll need the pairs (u₁,v₁), (u₂,v₂), and (u₃,v₃). For that, we begin by applying the Euclidean algorithm to the pairs (n₁,m₁), (n₂,m₂), and (n₃,m₃). (Below, we only write the consecutive equations given by the process.)

For (n₁,m₁) = (3,20):

20 = 6·3 + 2

3 = 1·2 + 1

2 = 2·1 + 0;

for (n₂,m₂) = (4,15):

15 = 3·4 + 3

4 = 1·3 + 1

3 = 3·1 + 0;

and for (n₃,m₃) = (5,12):

12 = 2·5 + 2

5 = 2·2 + 1

2 = 2·1 + 0.

Now, we recall Bézout's identity to find (u₁,v₁), (u₂,v₂), and (u₃,v₃). (Again, we only write the equations. Recall from the corresponding section the step-by-step instruction on how to obtain the desired pairs.)

For (n₁,m₁) = (3,20):

1 = 3 - 1·2 = 3 - 1·(20 - 6·3) = 7·3 + (-1)·20

so (u₁,v₁) = (7,-1).

For (n₂,m₂) = (4,15):

1 = 4 - 1·3 = 4 - 1·(15 - 3·4) = 4·4 + (-1)·15

so (u₂,v₂) = (4,-1).

For (n₃,m₃) = (5,12):

1 = 5 - 2·2 = 5 - 2·(12 - 2·5) = 3·5 + (-2)·12

so (u₃,v₃) = (3,-2).

Next, we get e₁, e₂, and e₃ using the according formulas:

e₁ = v₁·m₁ = (-1)·20 = -20

e₂ = v₂·m₂ = (-1)·15 = -15

e₃ = v₃·m₃ = (-2)·12 = -24

Lastly, we use them to find our solution:

x = a₁·e₁ + a₂·e₂ + a₃·e₃ = 1·(-20) + 2·(-15) + 3·(-24) = -122.

However, clearly, mom didn't buy -122 candies. We have to remember that our solution is unique modulo N = 60. This means that if we add any multiple of 60 to our result, the resulting number will also satisfy our congruences. Therefore, for a more reasonable value (and such as the Chinese remainder theorem calculator shows), let's add the 60 three times to our -122:

-122 + 3·60 = 58

Voilà! That's how many sweets we could expect.

Hmm... Should we really invite the kids next door? Why don't we just eat them with our siblings and let Mom have that one last candy? Surely, it can't be too many calories, can it?