# Chinese Remainder Theorem

The Chinese remainder theorem is an excellent example of how mathematics in China began early and has continued strong until the present day. However, the theory came up relatively late in the game compared to the history of Chinese mathematics as a whole. After all, the field of math emerged in the 11th century BC in China, and the theorem only came into being in the 3rd century AC! Since then, people have used the Chinese remainder theorem to solve various problems, create proofs, and even develop algorithms. And that’s what I will be talking about in more detail here.

The Chinese remainder theorem states that a linear system of congruence equations with pairwise relatively prime moduli has a unique solution modulo the product of the moduli of the system.

Now, I know that’s a lot of words to throw at you, especially if you are new to the topic. But once you get familiar with the definitions of those words and see some examples of the Chinese remainder theorem, it’s sure to click. It’s a relatively simple idea. It’s just putting into the language of math that can make it look a bit tricky.

Once you understand the basic concepts, you will see that the Chinese remainder theorem and its proof are useful in resolving many elementary problems. To start you off, I will go over a simple example below. I’ll then branch into various cases, proofs, an algorithm, and also provide some additional resources for further exploration of the Chinese remainder theorem.

## Chinese Remainder Theorem Example

One useful application of the theorem is to find information about a group of objects through small manipulations. For example, if I manipulate objects several times, but in different little ways, I can then answer specific questions about those objects without further manipulation. Read below for a real-world example:

Before getting into any real math or equations, I want to take a step back and imagine a simple case of the Chinese remainder theorem.

Imagine I am sorting a basket of eggs. But I don’t know how many there are. It’s also a Sunday afternoon in the 3rd century BC, and I am very bored, so I don’t want to count the eggs. No, no, I’m going to play with my food for a while. How can I figure out how many eggs are in the basket without counting them?

I know that if I take out three at a time, I end up with two left-over. If I take out five at a time, I get three left-over, and if I take out seven at a time, I get two left-over. According to the Chinese remainder theorem, this is enough information to solve the problem of figuring out the least number of eggs that I could have in the basket.

### Lists of Multiples Plus Remainders

If I remove three eggs at a time from the basket and there are two left-over, then I know that the original number must be two greater than some multiple of 3. The multiples of 3 are 3, 6, 9, 12, 15, 18, 21, 24 etc. Adding the remainder of 2 to each of these numbers leaves me with my list of options for the number of eggs in my basket: 5, 8, 11, 14, 17, 20, 23, etc.

The list of multiples of number 5 is 5, 10, 15, 20, 25, 30. With a remainder of 3, I know my options for the number of eggs are 8, 13, 18, 23, etc.

And finally, the list of multiples of number 7 is 7, 14, 21, 28, etc.. With a remainder of 2 eggs, I know that my basket must have 9, 16, 23, 30 (etc.) eggs.

Once I get to this point, I need to see which of those last numbers is in the above lists of possible numbers of eggs. To make it easier to see, here are all the lists of possible egg amounts together:

Based on removing three eggs: 5, 8, 11, 14, 17, 20, 23

Based on removing five eggs: 8, 13, 18, 23

And based on removing seven eggs: 9, 16, 23, 30

As you can see, the only number they all share is 23. Therefore, I now know that there must be at least 23 eggs in the basket.

### One Big Omelette

The above example pretty much sums up the problem that the Chinese remainder theorem solves. But that method of manual calculation gets quite tricky once I start working with larger numbers. Let’s say I became so enthused with my basket of eggs that I decided to start an omelet restaurant. I then get the below statistics for egg removal:

If I remove eggs from a basket 2, 3, 4, 5, and 6, at a time, there remain, respectively, 1, 2, 3, 4, and 5 eggs. But if the eggs are removed 7 at a time, no eggs remain. What is the least number of eggs that could have been in the basket?

If you try to make lists of multiples with those numbers, you will have some very long lists. At this point, it’s easier to solve a system of linear congruence equations.  The Chinese remainder theorem allows us to do just this. For example, the system of linear congruence equations given by $$\begin{cases} x \equiv 1 \pmod{2} \\ x \equiv 2 \pmod{3} \\ x \equiv 3 \pmod{4} \\ x \equiv 4 \pmod{5} \\ x \equiv 5 \pmod{6} \\ x \equiv 0 \pmod{7} \end{cases}$$ arises from a variety of situations, e.g. the above question. Using the Chinese remainder theorem we can solve these systems very quickly.

Further, by the Fundamental Theorem of Arithmetic, a single congruence equation with composite modulus can be rewritten as a system of congruence equations with pairwise relatively prime moduli. I give a well-thought-out proof of the Chinese remainder theorem and provide many examples that demonstrate these ideas below. I will even go over an algorithm that you can write to avoid using the Chinese remainder theorem by hand in every instance. But first, there are some familiar topics.

## Introduction and Prerequisites

Before jumping straight into the proof and examples of the Chinese remainder theorem, I strongly urge you to start with some other materials that will help you get grounded. I will call them prerequisite materials and discuss them below. But if you already feel pretty comfortable with each of the topics they cover, then, by all means, full steam ahead.

### Divisibility

The first is an article titled Divisibility (and the Division Algorithm). It goes over several divisibility lemmas that are crucial for several theorems such as the Chinese remainder theorem. You will also find information on linear combinations and the division algorithm.

I especially recommend the article Greatest Common Divisors (and Their Importance). There are several simple lemmas in this article that are required. Materials such as the Euclidean Algorithm (by Example) also provide essential knowledge on finding the greatest common divisor of two integers that you will need when using the Chinese remainder theorem. You will see how crucial it is when you know the theorem’s proof. With the algorithm, you will also be able to write the gcd as a linear combination of the given integers.

### Prime Numbers

Next up is Prime Number Theorems (Infinitude of Primes). It discusses prime numbers, shows how to use the sieve of Eratosthenes to find them, and proves some prime number theorems. You will also see how assuming a well-ordering axiom shows that all natural numbers have a prime divisor.

The next important topic is the Fundamental Theorem of Arithmetic. If you’re keeping up with each of these, you probably noticed the importance of prime numbers. In this article, you will start with a characterization of them in terms of divisibility, which I then use to prove the Fundamental Theorem of Arithmetic. The theorem states that every positive integer has a unique factorization into a product of primes.

### Congruence

Finally, be sure to have a decent foundation on congruence. I suggest looking over both Congruence Theorems and Their Proofs and Linear Congruences and Their Solvability. The former discusses essential topics such as modular arithmetic, least positive residues, and elementary lemmas proofs. In the latter, I go over when linear congruence equations are solvable. It also includes the Euclidean algorithm, linear Diophantine methods, and how to use a quicker ad hoc method.

With those articles, you will familiarize yourself with the definition of congruency and how to solve congruence equations. Being able to construct a solution to the original congruence from a linear system of congruence equations is where the Chinese remainder theorem is often applied.

## What is a Linear System of Congruence Equations?

### Moduli and Congruences

When solving a linear congruence with a large modulus, it is sometimes useful to reduce the linear congruence to a system of linear congruences with smaller moduli. Understanding these moduli and their various properties are essential for understanding their role in the congruences.

Two integers $a$ and $b$ are congruent modulo $n$ if $a-b$ is divisible by $n$ (a positive integer). We use the symbol $\equiv,$ giving us $a\equiv b \pmod{n}$ and this is called a congruence equation. An example of a valid congruence is if $a = 24,$ $b = 4,$ and $n = 5$ because $(24-4)$ is divisible by 5, and we write $$24 \equiv 4 \pmod{5}.$$

A congruence equation may have an unknown, $x,$ such that $a x \equiv b \pmod{n}.$ When you have multiple congruence equations that you wish to solve simultaneously, then it is called a linear system of congruence equations

In the Chinese remainder theorem, the moduli of each congruence equation in the system must be coprime, which means that the only positive integer which can divide the numbers is 1. Thus, the gcd of the moduli is equal to 1.

### How They Apply to the Chinese Remainder Theorem

In a system of simultaneous linear congruences that all have coprime moduli, the theorem will give you a number that leaves certain remainders when divided by certain divisors. You might see now how this relates to the remainders of eggs after dividing them by various amounts. But here, I will show you a Chinese remainder theorem example that is equivalent to having multiple baskets of eggs.

Let’s solve the following linear system of congruence equations.

\begin{align*} \label{crtex} \begin{cases} x\equiv 15 \pmod{27} \\ x\equiv 16 \pmod{20} \end{cases} \end{align*}

Notice, $20$ and $27$ are relatively prime, so we can find integers $a$ and $b$ such that $20a+27b=1.$ In fact, by inspection we find $a=-4$ and $b=3$ since ${20(-4)+27(3)=1}.$ We claim $$x=15(20)(-4)+16(27)(3)=96$$ is a solution to both linear congruence equations. More specifically, we will say, $x\equiv 96 \pmod{540}$ is the solution to the system where $540=(20)(27).$ This strategy and the uniqueness is justified in the following the Chinese remainder theorem, as proven below.

Example. Solve the linear system of congruences $$\begin{cases} x\equiv 2 \pmod{3} \\ x\equiv 5 \pmod{4} \\ x\equiv -3 \pmod{7} \end{cases}$$

Solution. I find $N=(3)(4)(7)=84$ and I use a table to construct the solution.

$$\begin{array}{c|c|c|c} n_i & a_i & \bar{n}_i & u_i \\ \hline 3 & 2 & 84/3=28 & 28u_1\equiv 1 \pmod{3} \Rightarrow u_1=1 \\ 4 & 5 & 84/4=21 & 21u_2\equiv 1 \pmod{4} \Rightarrow u_2=1 \\ 7 & -3 & 84/7=12 & 12u_3\equiv 1 \pmod{7} \Rightarrow u_3=3 \end{array}$$

By the Chinese remainder theorem the solution to the system in this example is \begin{align*} x & =(2)(28)(1)+(5)(21)(1)+(-3)(12)(3) \\ & =53 \pmod{84}. \end{align*} as wanted.

## The Chinese Remainder Theorem and It’s Proof

The Chinese remainder theorem has two forms, both of which I will provide the proof and give some examples. This section details the first form. Then, I describe the second general (or extended form) of the theorem later.

If this feels a bit confusing for you, I suggest taking a look at the examples in the section immediately following this one. I think these examples might help you see how the proof of the Chinese remainder theorem works as they are very similar to the proof. The main difference is just that they use actual numbers in place of variables. Now, for the evidence itself.

### Before Starting the Proof

Before I dive into this, I want to outline how the proof of the Chinese remainder theorem starts and what the goal is. First, I will begin the proof with a system of equations, and I will use $s$ for the number of equations. The solution I will get is $x$ with a unique solution modulo $N,$ the product of all the moduli $n_i.$ But when using the Chinese remainder theorem, you need to be sure that these moduli are all pairwise relatively prime. By this, I mean that any two of them need to be relatively prime (or coprime) such that their gcd is 1.

In the system of equations, I have the $a_i$ and the moduli $n_i$, and I will be solving for $x.$ But to do that, I will first need to find the integer $u_i$, which will help construct a solution. The $u_i$ comes from knowing that the moduli $n_i$ are pairwise relatively prime. This knowledge means that I can use the extended Euclidean algorithm to find $u_i$.

In the proof below, the Euclidean algorithm is applied in the part where I use $v_i n_i+u_i \bar{n}_i=1;$ to find $u_i.$ I just wanted to point this out, but you should already be familiar with this concept if you meet the prerequisites mentioned above in the section “Introduction and Prerequisites.” If you find yourself having trouble keeping up with all of it, I recommend going back to take a look at the articles I mentioned in that section.

Theorem. (Chinese Remainder I) Suppose $n_1, n_2, \ldots, n_s$ are pairwise relatively prime positive integers. Then the system of congruences \begin{align*} \begin{cases} x\equiv a_1 \pmod{n_1} \\ x\equiv a_2 \pmod{n_2} \\ \quad \vdots \\ x\equiv a_s \pmod{n_s} \\ \end{cases} \end{align*} has a unique solution modulo $N=n_1n_2\cdot \cdot \cdot n_s.$

### Chinese remainder theorem proof

Proof. Let $\bar{n}_i=N\left/n_i.\right.$ I know that $\left(n_i,\bar{n}_i\right)=1$ for $i=1, \ldots, s$ because $\left(n_i,n_j\right)=1$ whenever $i\neq j.$ Therefore, for each $i,$ there are integers $v_i$ and $u_i$ such that $v_i n_i+u_i \bar{n}_i=1;$ and using these $u_i$ I can construct a solution to the system as

$$x=a_1\bar{n}_1u_1+a_2\bar{n}_2u_2+\cdots+a_s\bar{n}_su_s.$$

To verify this is a solution, I check the $i^{\text{th}}$ congruence equation, namely, $$x=\sum_{k=1}^s a_k\bar{n}_ku_k\equiv a_i\bar{n}_iu_i\equiv a_i \pmod{n_i}$$ for $1\leq i\leq s$.

To prove uniqueness, I assume $y$ is a solution to the system of congruences. Then $x_0\equiv a_i\equiv y \pmod{n_i}$ for $1\leq i\leq s$. Hence, $n_i|\left(x_0-y\right)$ for each $n_i$ and since no two of the $n_i$ have a common factor, $n_1n_2\cdot \cdot \cdot n_s|\left(x_0-y\right),$ that is $N\left|\left(x_0-y\right).\right.$ Thus, $y\equiv x_0 \pmod{N}$ as needed.

The above proof for the Chinese remainder theorem is constructive. By that, I mean it not only tells you the solution exists, but it also tells you how to find the said solution. Many types of proofs aren’t constructive in this way. Instead, they only give the existence of something.

And now you know the proof of the Chinese remainder theorem!

## 3 Examples Using the Chinese Remainder Theorem

The below examples should help clear up all (or at least some) confusion you may have about the above proof of the Chinese remainder theorem. I have included some tables as part of the solutions to organize the information better. You will see that getting the solution merely involves adding the products of the last three rows. That is, multiply across each row to obtain a product, and then add those products together. Multiply across, add down.

### Example 1

Example. Solve the linear system of congruences. $$\begin{cases} x\equiv 3 \pmod{5} \\ x\equiv 2 \pmod{6} \\ x\equiv 4 \pmod{7}. \end{cases}$$

Solution. I find $N=(5)(6)(7)=210$ and I use a table to construct the solution. Remember that the column for $u_i$ comes from using the Euclidean algorithm.

$$\begin{array}{c|c|c|c} n_i & a_i & \bar{n}_i & u_i \\ \hline 1 5 & 3 & 210/5=42 & 42u_1\equiv 1 \pmod{5} \Rightarrow u_1=3 \\ 6 & 2 & 210/6=35 & 35u_2\equiv 1 \pmod{6} \Rightarrow u_2=5 \\ 7 & 4 & 210/7=30 & 30u_3\equiv 1 \pmod{7} \Rightarrow u_3=4 \end{array}$$

By the Chinese remainder theorem, the solution for this example is \begin{align*} x & =(3)(42)(3)+(2)(35)(5)+(4)(30)(4) \\ & =1208\equiv 158 \pmod{210}. \end{align*} as desired.

What’s important to know about this solution of 158 is that it is a unique solution. By this, I mean that it is the single number less than $N=210$ which still solves all of the equations in the system if you plug it in for $x.$

However, 1208 is also a valid solution. There are many valid solutions, but each always moduli with 210. Thus, any multiple of 210 is a valid solution/congruence, such as $158 + 210.$ In other words (and symbols), $368\equiv 3 \pmod{5}$ is also a valid congruence. You can see this because 5 divides $(368-3).$ Likewise, $1208\equiv 3 \pmod{5}$ is a valid congruence, $210\equiv 3 \pmod{5}$ is a valid congruence.

### Example 2

Example. Solve the linear system of congruences. $$\begin{cases} x\equiv 2 \pmod{3} \\ x\equiv 3 \pmod{5} \\ x\equiv 2 \pmod{7}. \end{cases}$$

Solution. I find $N=(3)(5)(7)=105$ and I use a table to construct the solution.

$$\begin{array}{c|c|c|c} n_i & a_i & \bar{n}_i & u_i \\ \hline 3 & 2 & 105/3=35 & 35u_1\equiv 1 \pmod{3} \Rightarrow u_1=2 \\ 5 & 3 & 105/5=21 & 21u_2\equiv 1 \pmod{5} \Rightarrow u_2=1 \\ 7 & 2 & 105/7=15 & 15u_3\equiv 1 \pmod{7} \Rightarrow u_3=1 \end{array}$$

Therefore, \begin{align*} x & =(2)(35)(2)+(3)(21)(1)+(2)(15)(1) \\ & =263\equiv 23 \pmod{105}. \end{align*} is the solution for this example by the Chinese remainder theorem.

Comparing this example to the previous one, you should notice that the moduli are also pairwise relatively prime. Additionally, $s$ is still 3, meaning there are only three congruences in the system. But keep in mind that these may change for any given linear system.

### Example 3

Example. Solve the linear system of congruences. $$\begin{cases} x\equiv 1 \pmod{2} \\ x\equiv 2 \pmod{3} \\ x\equiv 3 \pmod{5} \\ x\equiv 4 \pmod{7}. \end{cases}$$

Solution. I find $N=(2)(3)(5)(7)=210$ and I use a table to construct the solution. $$\begin{array}{c|c|c|c} n_i & a_i & \bar{n}_i & u_i \\ \hline 2 & 1 & 210/2=105 & 105u_1\equiv 1 \pmod{2} \Rightarrow u_1=1 \\ 3 & 2 & 210/3=70 & 70u_2\equiv 1 \pmod{3} \Rightarrow u_2=1 \\ 5 & 3 & 210/5=42 & 42u_3\equiv 1 \pmod{5} \Rightarrow u_3=3 \\ 7 & 4 & 210/7=30 & 30u_4\equiv 1 \pmod{7} \Rightarrow u_3=4 \end{array}$$

By the Chinese remainder theorem, I find that the solution to this example is \begin{align*}x & =(1)(105)(1)+(2)(70)(1)+(3)(42)(3)+(4)(30)(4) \\ & =1103\equiv 53 \pmod{210}. \end{align*} as desired.

In this example, $s$ changed to 4 as opposed to the three you had seen previously. But more significant changes are yet to come in the next sections that look at problems involving a different form of the Chinese remainder theorem.

## The General Form (or Extended Version) of the Chinese Remainder Theorem

Remember how I mentioned that there was a second version of the theorem? Well, this is it, the proof for part II of the Chinese remainder theorem. The difference between this version and the previous is that there are coefficients in front of the variable $x$.

### Before Starting the Proof

From the start, I have coefficients represented by $a_i$. But the proof will still involve a system of equations, just as in the first version of the Chinese remainder theorem. The proof is used to solve systems that look something like this:

$$\begin{cases} 1 x\equiv 3 \pmod{4} \\ 4x\equiv 3 \pmod{7} \\ 6 x\equiv 52 \pmod{60} \end{cases}$$

So you can see that it looks a little different from the previous examples, but the statement of the theorem is precisely the same. I still get a unique solution and a $N.$ The only difference is an additional step to deal with that pesky $a_i.$ Also, the $a_i$ is now on the left side of the equation, as opposed to the right. I suggest looking at the examples below as you go through the proof.

### The Proof

Theorem. (Chinese Remainder Theorem II) Suppose $n_1, n_2, \ldots n_s$ are pairwise relatively prime positive integers and that $\left(a_i,n_i\right) =1$ for each $i.$ Then the system of congruences $$\begin{cases} a_1 x\equiv b_1 \pmod{n_1} \\ a_2 x\equiv b_2 \pmod{n_2} \\ \quad \vdots \\ a_s x\equiv b_s \pmod{n_s} \\ \end{cases}$$ has a unique solution modulo $N=n_1n_2\cdots n_s.$

Proof. Since $\left(a_i,n_i\right)=1$ for each $i,$ I know that each congruence in the system has a solution, and I first choose integers $x_1, x_2, \ldots ,x_s$ such that $a_i x_i\equiv b_i \pmod{n_i}.$ Let $\bar{n}_i=N\left/n_i\right.$ and since no two of the $n_i$ have a common factor, I see that $\left(n_i,\bar{n}_i\right)=1.$ Thus, there is an integer $u_i$ such that $\bar{n}_i u_i\equiv 1 \pmod{n_i}.$ I now show that the number $x_0$ defined by $$x_0=\sum_{i=1}^s x_i\bar{n}_iu_i$$ is a solution of the original system of congruences.

First note that $n_i$ divides each $\bar{n}_i$ when $j\neq i.$ Thus, for each $i,$ I have, $$a_ix_0=\sum_{k=1}^s a_k x_k \overline{n}_k u_k\equiv a_ix_i\equiv b \pmod{n_i}.$$ Hence, $x_0$ is s solution of each congruence. If $y$ is a solution to the system of congruences, then $x_0\equiv x_i\equiv y \pmod{n_i}.$ Hence, $n_i|\left(x_0-y\right)$ for each $n_i$ and since no two of the $n_i$ have a common factor, $n_1n_2\cdot \cdot \cdot n_s|\left(x_0-y\right),$ that is $N\left|\left(x_0-y\right).\right.$ Thus, $y\equiv x_0 \pmod{N}.$

## Example on the Extended Chinese Remainder Theorem

These examples again use some tables to help explain part II of the Chinese remainder theorem. The same rule applies here as it did above: multiply across and add down for the last three rows. This technique will lead you to a unique solution, as well as other valid solutions.

Example. Solve the linear system of congruences. $$\begin{cases} 2 x\equiv 3 \pmod{7} \\ 3x\equiv 4 \pmod{5} \\ 5 x\equiv 46 \pmod{51} \end{cases}$$

Solution. I find $N=(7)(5)(51)=1785$ and I use a table to construct the solution. $$\begin{array}{c|c|c|c|c|c} n_i & a_i & b_i & a_i x_i \equiv b_i \pmod{n_i} & \bar{n}_i & \bar{n}_iu_i \equiv 1 \pmod{n_i} \\ \hline 7 & 2 & 3 & x_1=5 & 255 & u_1=5 \\ 5 & 3 & 4 & x_2=3 & 357 & u_2=3 \\ 51 & 5 & 46 & x_3=50 & 35 & u_3=35 \end{array}$$ By the Chinese remainder theorem I get the solution \begin{align*}x & = (5)(255)(5)+(3)(357)(3)+(50)(35)(35) \\ & = 70838 \equiv 1223 \pmod{1785}. \end{align*} as required.

## The Chinese Remainder Theorem Algorithm

### Basic Setup

In this day and age, you need to know how to apply math in computer settings. It’s also convenient once you know how to do it so that I will outline the process here. In a program of your choosing, you will want to write an algorithm that solves a system of linear congruences via the application of the Chinese remainder theorem. Some useful languages to use are Python, 360 Assembly, Ada, C, C++, C#, Bracmat, Clojure, or Java.

And don’t forget to write a part that states the system cannot be solved, if that is the case. In that particular case, there would be infinitely many solutions, so the algorithm for the Chinese remainder theorem should return a unique solution which is greater than or equal to zero and less than or equal to the product of the moduli of the system $N.$

In your algorithm, $N$ will be defined as $N=n_1n_2\cdots n_s,$ just as in a regular Chinese remainder theorem problem. Additionally, the $n_i$ must be positive coprime integers. The system of congruences in need of solving can be represented as $x \equiv a_i \pmod{n_i}$ for $i = 1, \ldots, k.$

### Applying the Extended Euclidean Algorithm

When using the Chinese remainder theorem to find the solution $x$we will use the Extended Euclidean algorithm. This algorithm is conventional in computer programming as an extension of the Euclidean algorithm. Its purpose is to compute the gcd of two integers and the coefficients of Bezout’s identity. This algorithm is particularly useful when the two integers are coprime, which you of course know is the case in the Chinese remainder theorem.

This algorithm will find the integers $r_i$ and $s_i$ in order to give $r_i s_i + s_i N/n_i =1.$ Then, a solution to the system of congruences will be the sum of $a_i s_i N/n_i$ from $i = 1$ to $i=k.$ The minimal solution to this algorithm for the Chinese remainder theorem is $x \pmod{N}$ where $x$ is the least positive residue.

If you have difficulties writing this code, you can consult this page here.

## Applications of the Chinese Remainder Theorem

I know what you’re thinking: why all this fuss about counting eggs in baskets? Well, of course, that’s not the real application of the theorem. The Chinese remainder theorem has many other uses, particularly in advanced computing algorithms. It also helps out other theorems as part of their proofs that require advanced manipulation to reach their conclusion.

### Cryptography and Encryption

I know that cyber security is a hot topic these days, and the Chinese remainder theorem plays a big role in important algorithms. Cryptography is a set of techniques used for making communication secure, particularly online and through digital means. Encryption is one of the methods of doing this, in which messages and information are encoded such that only authorized people can access and understand it.

Professionals implement the Chinese remainder theorem in the RSA cryptosystem, a widely used public-key system for secure data transmission. We base the optimization for decryption on the Chinese remainder theorem, in particular, it produces and stores values as part of a private key.

Additionally, the theorem gets used in secret sharing to guarantee the impossibility of recovering the secret from a set of shares as long as that set has less than a certain number of elements.

### Fourier Transforms

The Fourier transform is a well-known function used in many areas. It takes a signal, which is a function of time, and breaks it down into the individual frequencies that compose it. It is used to solve partial differential equations, but also in scientific fields such as nuclear magnetic resonance, infrared spectroscopy, mass spectrometry, and magnetic resonance imaging. The Chinese remainder theorem helps simplify the computations of the problems that the Fourier transform solves.

More specifically, problems involving fast Fourier transforms implement the Chinese remainder theorem to reduce the necessary amount of computation. It changes a larger Fourier transform into two fast ones of smaller sizes. But, of course, it only works if the size of the original transform is composed of two coprime sizes.

### Radar Range Ambiguity Resolution

Medium pulse repetition frequency radar uses techniques for range ambiguity resolution that implement the Chinese remainder theorem. It helps them to obtain information over significant distances that are even longer than the gap between the transmit pulses.

### Sequence Numbering in Gödel’s Theorems

There are two Gödel’s incompleteness theorems of mathematical logic that show the limitations of axiomatic systems. The Chinese remainder theorem can be used in specific theorems to achieve higher readability through the use of more modularity and reuse.

### Dedekind’s Theorem

Another theorem that receives a helping hand from the Chinese remainder theorem is Dedekind’s theorem. This theorem looks at the linear independence of characters, and the Chinese remainder theorem yields an isomorphism in its proof.

## Chinese Remainder Theorem Problems and Exercises

As with anything in math, the key to mastering it is to practice, practice, practice. You should be sure to put in the time and effort to get comfortable with everything necessary for using this theorem. By this, I mean reviewing the vocabulary, fully understanding the proof, practicing simple problems, and eventually applying the theory to real-world problems.

I have included some exercises below to help ease you into it. They start relatively simple and without using complicated terms. Then, I introduce more formal conditions and complicated problems. You should try to use the Chinese remainder theorem both by hand and as an algorithm on a computer to solve these examples.

### Simple Chinese Remainder Theorem Problems

Exercise 1. Find an integer that leaves remainder of 1 when divided by either 2 or 5, but that is divisible by 3.

Exercise 2. Find an integer that leaves remainder of 9 when it is divided by either 10 or 11, but that is divisible by 13.

Exercise 3. A certain integer between $1$ and $1200$ leaves the remainder $1, 2, 6$ when divided by $9, 11, 13$ respectively. What is the integer?

Exercise 4. For which integers $c$, does $12x\equiv c \pmod{30}$ have solutions? When there are solutions how many are there?

Exercise 5. Find three consecutive integers divisible by $2, 3,$ and $5$, respectively.

Exercise 6. Find the smallest even integer $m$ such that $3|m$, $5|(m+3)$, and $11|(m+5)$.

Exercise 7. Use the Chinese remainder theorem to solve the linear congruence equation $3 x\equiv 11 \pmod{245}.$

### More Complex Linear Systems

Exercise 8. Determine which integers $a$ have inverse modulo $14$ and then find each of the inverses.

Exercise 9. Find all solutions to the linear congruence equations $6x+3y\equiv 12 \pmod{13}$ and $10x+5y\equiv 9 \pmod{15}$.

Exercise 10. Solve the linear system of congruences. $$\begin{cases} x \equiv 1 \pmod{2} \\ x \equiv 2 \pmod{3} \\ x \equiv 5 \pmod{17} \\ x \equiv 3 \pmod{5} \end{cases}$$

Exercise 11. Solve the linear system of congruences. $$\begin{cases} x \equiv 0 \pmod{2} \\ x \equiv 0 \pmod{3} \\ x \equiv 1 \pmod{5} \\ x \equiv 6 \pmod{7} \end{cases}$$

Exercise 12. Find a single congruence that is equivalent to the system of congruences $x\equiv r_1 \pmod{m}$ and $x\equiv r_2 \pmod{m+1}$.

Exercise 13. Solve the linear system of congruences. $$\begin{cases}x \equiv 4 \pmod{6} \\ x \equiv 13 \pmod{15}\end{cases}$$

Exercise 14. Solve the linear system of congruences. $$\begin{cases} x \equiv 7 \pmod{10} \\ x \equiv 4 \pmod{15}\end{cases}$$

Exercise 15. Solve the linear system of congruences. $$\begin{cases}x \equiv 7 \pmod{15} \\ x \equiv 4 \pmod{10}\end{cases}$$

Exercise 16. Solve the linear system of congruences. $$\begin{cases}x \equiv 5 \pmod{6} \\ 7x \equiv 3 \pmod{10} \\ 4x \equiv 8 \pmod{15}\end{cases}$$

Exercise 17. Solve the linear system of congruences. $$\begin{cases}x\equiv 1 \pmod{999} \\ x\equiv 2 \pmod{1001} \\ x\equiv 3 \pmod{1003} \\ x\equiv 4 \pmod{1004} \\ x\equiv 5 \pmod{1007}\end{cases}$$

Exercise 18. Find a single congruence that is equivalent to the system of congruences $x\equiv r_1 \pmod{m}$ and $x\equiv r_2 \pmod{m+1}$.

Exercise 19. Solve the system $2x\equiv 3 \pmod{4},$ $5x\equiv 6 \pmod{7},$ $9x\equiv 10 \pmod{11}$ using the Chinese remainder theorem.

Exercise 20. Using the Chinese remainder theorem, solve the system of linear congruence equations $2x\equiv 3 \pmod{4},$ $3x\equiv 5 \pmod{6},$ and $4x\equiv 1 \pmod{7}.$

## Chinese Remainder Theorem Word Problems

The above exercises are quite straightforward in terms of their presentation. The below exercises, not so much. They aren’t necessarily more complicated than those I listed above. However, they do require a different mode of thinking.

Rather than clearly stating what you must do to find the answer, they detail the problem itself. I say the problem in a conversational manner that describes a real-world problem in regular terms that you could use the Chinese remainder theorem to solve. From there, you must figure out what answer you need and what is the best way to get to it. It requires a bit more creativity and abstract thought, in addition to logic.

When trying to solve problems, you might react in an entirely different way to these problems than someone else. But it’s good to work out your brain in many ways. You could even use these problems to test your abilities at working with the Chinese remainder theorem algorithm on a computer.

### Problems to Try Out

Exercise 21. A professor buys a new car every three years; he bought his first in 1981. He gets a sabbatical leave every seven years, starting in 1992. When will he first get both during a leap year?

Exercise 22. On the Fourth of July, I took a red pill at 8 a.m. and a green pill at noon. The next day I took a white pill at 10 p.m. I take the red, green, and white pill every 5, 7, and 24 hours, respectively. How often do I take all three together? When in August will this first happen, if at all?

Exercise 23. A group of 17 babies are playing with some toy blocks. They put their blocks into 11 equal piles of multiple blocks. There is a twelfth pile that contains 6 leftover blocks. But when they put the blocks into 17 equal piles, there aren’t any left over. What’s the smallest number of blocks they could have?

### Problems You Can Find Online

Exercise 24. A scientist feeds his pet python every fours days and bathes it once a week. This week he fed it on Tuesday and washed it on Wednesday. When, if ever, will he feed and wash the python on the same day? How often will this happen?

Exercise 25. The three children in a family have feet that are 5 inches, 7 inches, and 9 inches long. When they measure the length of the dining room of their house using their feet, they each find that there are 3 inches left over. How long is the dining room?

Exercise 26. If I remove eggs from a basket 2, 3, 4, 5, and 6, at a time, then there remain, respectively, 1, 2, 3, 4, and 5 eggs. But if I remove 7 at a time, no eggs remain. What is the least number of eggs that I could have in the basket?

Exercise 27. I have a box filled to the brim with gold coins. If I divide the coins equally among six of my lucky friends, the I get four coins left over. If I only split the coins between my five luckiest friends, then there are three coins left over. What is the smallest number of coins that the box could contain. And, since in reality I have seven friends who deserve some of the treasure, how many coins would be left if I equally divided them among those seven friends?

## Getting Help With the Chinese Remainder Theorem

As with anything in life, two brains are usually better than one. I know that wrapping your head around higher-level math topics like this can be tough, which is why I want to encourage you to seek support. Professional tutors are not only familiar with the subject, but they also know how others have trouble. They are skilled in focusing on the specific areas and methods that are giving you have been having trouble.

In the old days, the only way to get with a tutor was to do it in person. Of course, that’s a thing of the past, and now they are at your fingertips at any moment. There are dozens of websites dedicated to matching students with their perfect tutor, and usually at a reasonable cost.

### How to Find the Perfect Online Tutor

Many tutors in all subject areas have moved their business to online freelancing platforms. These websites help them develop their skills into part- or full-time jobs, meaning they can optimize their services. The sites also help people like you to search through the various freelancers to find one that matches your needs.

Whether you want to find someone to teach you the basics of the Chinese remainder theorem or teach you programming that can help you with the algorithm, you are sure to find the help you need. Below, I discuss a few of the sites that I recommend to help you find the support you might need.

#### Wyzant.com

Wyzant not only provides you with potential online tutors, but it can also match you with local ones. You can search profiles on the site by setting filters based on subject, location, schedule, price, and more. And unlike some other places, Wyzant does not set the price that tutors charge. Instead, each tutor can set their rate. By setting their price, this allows for more flexibility and competition between various tutors. It also gives you more flexibility to choose the best fit for you.

While some of the tutors on Wyzant are certified, not all are. Check their profiles to see what qualifications they have, as well as to know if they have passed a background check. This last part is particularly important if you plan on meeting them in person, so keep it in mind no matter where you look for tutors!

You can also find reviews on their profiles to see what others have to say about their services. And if, after all that checking, you still end up not being satisfied with your first lesson, Wyzant will refund your payment. So, go ahead and give it a shot.

#### Fiverr.com

Unlike Wyzant, Fiverr is a site dedicated to general freelancers, not just tutors. From their massive pool of freelancers, you can effortlessly search for tutors in the area you want. And each of them has easily identifiable credentials such as reviews, ratings, and “levels” to help you identify those with more experience and proven performance.

Fiverr also has a refund policy based on the performance of the freelancer you contract. If they are late for the agreed work or unresponsive for over 24 hours, then you can cancel and refund your order. But money shouldn’t be as big worry on Fiverr as some other tutor sites. Their prices are known for being quite low, often starting at just 5 or 10 dollars. Compare that to the hundreds charged per hour on other tutoring sites, and I think you’ll be interested in this platform.

#### Freelancer.com

As one of the largest freelancer sites out there, I am sure you will find something on freelancer.com. You can either find freelancers who advertise for tutoring that you are interested in, or you can post a job with your requirements. The freelancers on the site will then see your posting and makes bids on it. By this, I mean they come to you, and their bids will be competing with one another to encourage lower prices or other added benefits.

Once you have selected someone, there are various ways to go about getting the job done. The website has some helpful features in this area, such as a desktop app, mobile app, chat messaging, and time tracking.

If you want to consider this site as an option, you should know that the payment system requires you to pay upfront. The funds go into an escrow account where they stay until the freelancer completes the job. Then, these funds get released to the freelancer, ensuring that both parties complete their side of the deal.

## Further Reading on the Chinese Remainder Theorem

While having another human help is undoubtedly a good idea, you might prefer that it wasn’t in the flesh. After all, tutors are often costly, and they often focus on practicing problems and doing exercises. Books, on the other hand, are comparatively pretty cheap and let you go at your own pace and at any time you wish in a variety of areas. They also go much more in-depth than a tutor typically would. Below, I discuss some books that go over applications, theory, problems, algorithms, and other concepts of the Chinese remainder theorem.

### Chinese Remainder Theorem: Applications in Computing, Coding, Cryptography

This book provides a very well-rounded approach to everything about the Chinese remainder theorem. Of course, it covers the applications it mentions in the title, but it also talks about much more. In Chinese Remainder Theorem: Application in Computing, Coding, Cryptography, you will also learn about the history, philosophy, and generalizations of the theorem.

This book covers so much background in the subject you don’t need to familiar with the topic already. It even includes some prerequisite material such as algebra and information theory. However, anyone reading it should still have general math knowledge and abilities. It may also help to be already familiar with computing to help you understand the applications and algorithms relating to the Chinese remainder theorem.

Because the general format of the book is for a college level, it’s an excellent introduction for students. It can also be used by professors to help structure and guide courses. It might be useful for courses such as coding theory, algorithmics, cryptography, or similar areas.

### Elementary Number Theory: Primes, Congruences, and Secrets: A Computational Approach

This text gets more into the various parts that make up the Chinese remainder theorem. As I mentioned above, topics such as primes and congruences play a considerable role in the theorem. With Elementary Number Theory, you can learn about these topics with various numerical examples.

This text gets more into the various parts that make up the Chinese remainder theorem. As I mentioned above, topics such as primes and congruences play an essential role in the theorem. With Elementary Number Theory, you can learn about these topics with various numerical examples.

The material in the book is a mix of theory, algorithms, and computation that relate to the Chinese remainder theorem. It even covers some of the historical aspects of the field as well. And, it was born from an undergraduate course at Harvard, so you can be sure it’s of high quality.

At the end of each chapter, you will find exercises to put your knowledge to the test. In addition to the math itself, this text also shows you how to use a powerful software system. This system, Sage, is open source and free for anyone who wants to take advantage of it. I highly recommend taking a look.

### Elementary Number Theory (Textbooks in Mathematics)

Another number theory book I suggest taking a look at is the Textbooks in Mathematics Elementary Number Theory. It focuses on an accessible approach that covers both the applications of number theory as well as its role in pure mathematics. These applications include cryptography, so this book would pair well with the first book I mentioned above.

The book starts with a chapter on proofs and some other topics that are important with regards to the Chinese remainder theorem. Then, the meat of the text covers linear Diophantine equations, congruences, Euler’s theorem, and more.

Throughout the book, you will find “check your understanding” problems to ensure you’re following along. There are also exercises at the end of each chapter to apply and reinforce knowledge. Some exercises also introduce new ideas to encourage creative thinking.

### Elementary Number Theory and Its Applications

Elementary Number Theory and Its Application is a great tool that blends the classical theory of the field with its applications. Of note, it is well-known for providing fantastic sets of exercises. These exercises are of all levels, ranging from basic to quite challenging. There are even computer projects and computational activities so that you can apply your knowledge about the Chinese remainder theorem algorithm.

Getting a firm grasp on number theory concepts is crucial for dealing with the Chinese remainder theorem. With a wide range of exercises in this book, you are sure to become very comfortable with the subject.

This text has changed over the years to take into account feedback from professors who used it in their courses. Each new edition offers additional examples and problems to give students a wide range of practice. The newer versions also add modern advancements and discoveries to keep everything up to date.

## The Chinese Remainder Theorem and Its History

The first mentions of the theorem focus on the ideas and logic that it explains. That is, they do not include generalized equations or proofs. Instead, they are concrete examples with specific numbers.

For example, most people credit the Chinese mathematician with the first known statement of the theorem. He writes an instance of counting trees by various increments that result in various amounts left over, just like the first example with the eggs that I gave at the beginning of this article.

### From China to Europe

As Sun-Tzu’s writing didn’t give proof or an algorithm for the Chinese remainder theorem, another mathematician took care of that part. In the 6th century, Aryabhata solved the problem with an algorithm, really giving rise to the Chinese remainder theorem as we know it today. Various individual cases were also known in the 7th century, followed by a complete generalized solution by Chinese mathematician Ch’in Chiushao.

The theorem eventually arrived in Europe in 1202 as part of a mathematical treatise. However, the remainder problem was slightly different than that of Sun-Tzu. That original remainder problem didn’t make it for a while longer. There were several treatises throughout the centuries of various versions of the theorem. They ranged in geographic location from China, to the Arab world, to Europe. The original finally arrived in Europe and was translated into English in the 19th century.

### Essential Parts of the Theorem

The idea of congruence, which plays a crucial role in the Chinese remainder theorem today, have been brought up throughout time. Gauss introduced them in 1801 by using them to solve a calendar problem. But, it turns out Euler had already used the method before him. And on top of that, so had the ancient Chinese! People used congruences of the first degree to calculate old calendars in China even before Sun-Tzu’s writing.

Euclidean division also plays a significant role in solving problems and creating algorithms for the Chinese remainder theorem. However, although it’s getting its name from Euclid, he did not play a direct role in its creation. Instead, the name originates as a shorthand for the term “division of Euclidean rings.”

## Videos on the Chinese Remainder Theorem

The above explanations might just feel like a wall of text for you. I get that; it can be more natural to see someone else do a problem step by step. That’s why I include some videos below of additional explanations from various people. They give a step-by-step narration of solving Chinese remainder theorem problems and examples, often breaking down the complicated math in more accessible terms or analogies. Before each video, I will summarize the contents to give you an idea of what you can gain from it.

### The Chinese Remainder Theorem Made Easy

First, the video “The Chinese Remainder Theorem made easy” shows the solution process for a typical question you might see on an exam. The video is by Randell Heyman, who creates educational videos for various concepts in math. His slogan is “I translate mathematics into English,” which I think gives many people hope for understanding the crazy language of math. The concepts cover both high school and university levels, so if you find this video useful, then you may want to check out some others of his.

The video starts by introducing a system of congruences where $s=3$ and then asking you to find $x.$ He also begins by referring you to some videos to help with understanding moduli. Similarly, he emphasizes the importance of understanding the concept of gcd. He then checks that each pair of moduli in the given system has a gcd of 1. After checking that this is indeed the case, he uses the Chinese remainder theorem.

He then splits the solution into three sections, rather than jumping straight to the solution equation generally found in places like the proof of the Chinese remainder theorem. By this, I mean, he essentially makes the solution a set of simple multiplication and addition steps. It’s just a matter of knowing what needs to be added or multiplied, and when. His method even works when the numbers are much larger, with only a small change. In that case, you use the Extended Euclidean Algorithm.

### Chinese Remainder Theorem from Maths With Jay

Maths with Jay is another channel that looks at some of the different concepts troubling students of varying levels. Although based in the UK, the math concepts don’t change. But some of the prep materials might (looking at you, A-Levels). Some of her videos even cover more practical advice like how to set your calculator in different modes.

This video starts with a system where $s=3$ and you need to solve for $x.$ Jay then pauses from that specific problem to show a general case example for using the Chinese remainder theorem. This example uses a table much like the ones that I went over in previous sections. She gives a clear explanation of what each column represents and how to calculate the value. The final column, in this case, is a product of the previous columns. Then, the sum of that last column gives the solution. She then shows how the final equation represents this process.

With that general case in mind, she returns to the specific example problem. Using real numbers from the example, she plugs them into the same table. During the whole process, you can see the two cases side by side and hear her narrate the steps. She even shows how to check the answer using a computer program, which is always a great idea if you don’t have solutions available while studying.

### Number Theory: Chinese Remainder Theorem Proof

In this video, Michael Penn uses old school chalk and blackboard to do the Chinese remainder theorem proof. Straight off, he starts with generalized examples and advanced terms. He doesn’t go into explanations of the terms or basic concepts used in the problem, so you will need to be sure that you are already familiar with them.

But as long as you can keep up with the terms, he walks through the process at a comfortable pace with constant narration to explain what he is doing. During the process, he points out how he collects certain information. So that know where certain assumptions or derivations come from, so they don’t appear to come out of thin air.

### Chinese Remainder Theorem With Cards From Numberphile

The channel Numberphile makes some fun and simple “videos about numbers” as they say in their bio. Their animations and interesting real world examples help you grasp what the math concepts really mean. In this video, they use some cards to illustrate an example of what the Chinese remainder theorem really tells us and how you can actually use it for something. In fact, they make it into a “magic” card trick. The trick uses two sets of four cards that appear to be randomly shuffled, yet they end up matching each other when laid down side by side at the end.

The key for the trick is the number of times that you shuffle, which is based on selecting a specific word. This word should have certain properties regarding the number of letters it contains. You’ll see what I mean when you watch the video. And then, you will be able to surprise your friends with your incredible card skills (and also with some Chinese remainder theorem skills). You will even be able to do it with larger numbers of cards, really upping the wow factor.

## Chinese Remainder Theorem FAQ

Below, I outline the basics of the topics covered in more detail in this guide. For more information and additional resources, check out the corresponding sections in the article above.

## How do you solve the Chinese remainder theorem?

Using the Chinese remainder theorem to solve a system of linear congruence equations starts with checking that the system has pairwise relatively prime moduli. Then, use the Euclidean algorithm to construct a unique solution modulo the product fo the moduli. The actual computations involved in finding the solution is primarily multiplication and division.

## Who created the Chinese remainder theorem?

Some debate surrounds this topic, but many people attributed the idea of the theorem to the Chinese author Sun-Tzu in the 3rd century. Then, the actual theory appeared later in various locations and changed throughout time as new mathematicians added to it.

## How is modular arithmetic used?

Modular arithmetic provides a system for integers such that numbers “wrap around” in a sort of cycle after reaching a specific value. Everyone uses modular arithmetic in many contexts, including time (clocks that start over after reaching 12) or degrees of a circle. The concept is also essential in many areas of theoretical mathematics and computer science.

## How is the Chinese remainder theorem used?

The theorem has several applications in the field both within and outside of mathematics. Within, it helps solve and manipulate other problems and proofs. Outside, it has applications in advanced computing and technology.

## The Chinese Remainder Theorem in Other Algebraic Structures

The Chinese remainder theorem and its proof that I have discussed above is the case for the integers. But there are other options that I can use in problems dealing with the Chinese remainder theorem. These include using rings, which will then lead us to the concept of ideals.

### What Is a Ring?

If I look closely at the proof, I see that I can derive the Chinese remainder theorem in more general algebraic structures. By this, I mean for rings. I will demonstrate here the case for commutative rings with unity.

So what is a ring?

Definition. A ring is a set $R$ together with two operations additions namely $(+)$ and multiplication $(\cdot)$ defined on $R$ with the following properties:
(1) closed under addition: for all $a, b\in R$, $a+b \in R$,
(2) additive identity: there exists $0\in R$ such that for all $a\in R$, $a+0 = a$,
(3) additivity inverse: for all $a\in R$, there exists $-a\in R$ such that $a+(-a) = 0$,
(4) addition is associative: for all $a,b,c\in R$, $a+(b+ c) = (a+ b)+ c$,
(5) addition is commutative: for all $a, b\in R$, $a+b = b+a$,
(6) closed under multiplication: for all $a, b\in R$, $a\cdot b \in R$,
(7) multiplication is associative: for all $a,b,c\in R$, $a\cdot (b\cdot c) = (a\cdot b)\cdot c$,
(8) multiplication (left) distributes over addition: for all $a,b,c\in R$, $a\cdot (b+ c) = (a\cdot b) + (a \cdot c)$, and
(9) multiplication (right) distributes over addition: for all $a,b,c\in R$, $(b+ c) \cdot a = (b\cdot a) + (c \cdot a)$.

### Various Types of Rings

If multiplication is commutative, meaning: for all $a,b\in R$, $a\cdot b = b\cdot a$, then $R$ is a called a commutative ring.

Notice that the integers $\mathbb{Z}$ is a commutative ring!

You might also notice that there are many commutative rings, such as the ring of polynomials over the real numbers, denoted as $\mathbb{R}[x]$, or $R[x,y]$ for two variables and so on. There are many more types of rings beside the integers and polynomials, and not all rings are commutative

If $R$ has an element $1$ such that $1\cdot a = a\cdot 1 = a$ for all $a\in R$, then $R$ is called a ring with unity. Again, notice that $\mathbb{Z}$ and polynomial rings such as $\mathbb{R}[x_1, \ldots, x_n]$ are commutative rings with unity.

### What Is an Ideal?

Okay, so going forward, I will work with a ring with unity $R$. Now, in rings, the concept of “number” is not present. For example, in the commutative ring with unity $\mathbb{R}[x,y,z]$, the elements $x y^2 +z^3 +2$ and $z-y x^4+17$ are not numbers. So even though $23$ is a number and is in $\mathbb{R}[x,y,z],$ I can not say that this ring consists of numbers. In rings, the important objects to study are ideals, not elements.

One way I see this is by understanding the meaning of the Chinese remainder theorem in other algebraic structures such as a commutative ring with unity. So here is what an ideal is:

Definition. A nonempty subset $I$ of a commutative ring with unity $R$ is called an ideal of $R$ if
(1) for all $a,b\in I$, $a+b\in I$ and
(2) for all $r\in R$ and all $a\in I$, $r \cdot a \in I$.

For example, in the integers, the set of even integers is ideal. Why? (1) If I take any two even integers and add them, I have another even integer. (2) If I take an integer and an even integer and then multiple them, I get an even integer.

Notice the set of multiples of $3$ is another ideal; the set of multiples of 4 is another ideal, and so on. Also, notice that the ring $R$ is itself an ideal of $R$, and secondly, that ${0}$ is an ideal of $R$.

Furthermore, the set of linear combinations of two integers is also an ideal in $\mathbb{Z}$. For example, the set $\{3a+4b : a,b\in \mathbb{Z} \}$ is an ideal of $\mathbb{Z}$. Can you see why? In the ring $\mathbb{R}[x,y]$, the set of all linear combinations of $x^ y -3x +y -4$ and $2x^3-x y +1$ is an ideal.

### Operations With Ideals

Similarly to numbers, you can do (algebraic) operations with ideals such as adding and multiplying. Here’s how to add two ideals:

$$I+J =\{ i + j : i\in I, j\in J\}$$

And here is how to multiply two ideals:

$$IJ =\{ i \cdot j : i\in I, j\in J\}.$$

It’s not too hard to show that $I+J$ and $IJ$ are also ideals of $R$. Since ideals are sets, I can do set-theoretic operations on them, such as intersections. It turns out, for commutative rings, we have $I\cap J = IJ$.

Ideals are incredibly important to study and for many reasons. But, you may ask, how are ideals and congruence related? Well, in the integers, we say $a\equiv b \pmod{n}$ which means $n\vert (a-b)$ or in other words: $a = b + kn$ for some integer $k$. Here, let $I$ be the ideal of $\mathbb{Z}$ that consists of all multiples of $n.$ So you have $a\equiv b \pmod{I}$ which is equivalent to $a \in b + I$ which is also equivalent to $a = b + kn$ for some integer $k$.

Now I get back to the Chinese remainder theorem with a proof.

Theorem. Let $I_1,\ldots, I_s$ be ideals in a commutative ring with unity such that $I_1+I_2+\cdots +I_s = R$, then the system of congruence equations \begin{align*} \begin{cases} x\equiv a_1 \pmod{I_1} \\ x\equiv a_2 \pmod{I_2} \\ \quad \vdots \\ x\equiv a_s \pmod{I_s} \\ \end{cases} \end{align*} has a unique solution modulo $I=I_1I_2\cdots I_s.$

Try to follow the proof above to see if you can write your proof. But first, you might give yourself an example (or two) using the Chinese remainder theorem in this way to see it actually working, and then maybe even apply it in a problem with an algorithm in a program of your choosing.

## Conclusion: How to Proceed

I hope that this article has been enlightening when it comes to information, proofs, examples, problems, algorithms, and other information regarding the Chinese remainder theorem. I have included numerous examples that attempt to demonstrate the concepts clearly. But in case those aren’t sufficient, the links to other materials such as videos and additional articles should cover everything you could need for the topic. You just need to identify your weak points and target them.

### The Field Goes On

Although I aimed for thoroughness, I must admit that there is still a world of information out there on the subject. The more you dig into any one part of the theorem, the more material you will discover. Particularly once you get into the world of applications. Using the Chinese remainder theorem to create complex algorithms for cryptography and similar problems is a vast topic in its own right.

But even without getting into applications, there is still much to learn regarding the theorem. If you are having any trouble with the theory, consider taking a break to look at some of the related math concepts in more detail.

### Do What Works For You

Part of the problem you might have with the Chinese remainder theorem may stem from not fully understanding other concepts like the Euclidean algorithm, moduli, congruences, or primeness. I suggest looking into those topics on their own by doing related proofs and examples on them before connecting them back to the Chinese remainder theorem.

Ultimately, everything will come together with practice. Start with the smaller components and proofs before building up to doing problems and examples with the Chinese remainder theorem. Seek help from professional tutors, books, or online courses. And focus on those topics that give you the most trouble. At some point, it will all just click.

Did the applications of the Chinese remainder theorem surprise you? Would you like to see more problems and examples of the Chinese remainder theorem?

## Contributors

• David Smith is the Founder and CEO of Direct Knowledge. Inspired by more than two decades of teaching undergraduate mathematics, he founded Direct Knowledge to share high-quality educational content with anyone seeking to learn. In addition to teaching and coordinating undergraduate courses in calculus, linear algebra, and number theory at both a junior college and a Tier One research university, David pursued his personal interest in computer science with several graduate level courses in artificial intelligence and machine learning. David has a B.S. and M.S. in Mathematics.