Existence of Solutions in Chinese Remainder Theorem

Existence of a solution to CRT

I'll only prove this in not the most general form, but luckily the most general form is a pretty easy extension.

In particular, I will show that if $m$ and $n$ are relatively prime (i.e. $\gcd(m, n) = 1$), then the congruences $$x \equiv a \pmod{m}$$ $$x \equiv b \pmod{n}$$ will have some integer $x$ that satisfies both.

Let's get a feel for CRT by doing an example. We'll solve the congruence system $$x \equiv 3 \pmod{5}$$ $$x \equiv 2 \pmod{7}$$

So note that $23 \equiv 2 \pmod{7}$. So $x = 23$ works! Now let's do the general case. So let's find an $x$ such that $$x \equiv a \pmod{m}$$ $$x \equiv b \pmod{n}$$

So let's write out $n$ numbers: $a+0 \cdot m, a+1 \cdot m, a+2 \cdot m, \dots, a + (n-1) \cdot m$.

Let's do this now. How can we prove that they are all different. A good proof technique is contradiction. We assume that some two are in fact congruent $\pmod{n}$, and try to reach a contradiction.

So assume for some $i \not= j$, both in the range $[0, n-1]$, that $a + im \equiv a + jm \pmod{n}$. I choose the range $[0, n-1]$ because the numbers we are interested in are $a+0 \cdot m, a+1 \cdot m, a+2 \cdot m, \dots, a + (n-1) \cdot m$.

Subtracting gives us $(i-j)m \equiv 0 \pmod{n}$.

So $n | (i-j)m$. But since $\gcd(n, m) = 1$, by Euclid's Lemma, $n | i-j$. But this is a contradiction! Why? Because $i, j$ are both between $0$ and $n-1$! So if their difference is a multiple of $n$, they must be equal. Contradiction! So all the remainders are distinct. Let's finish now. Because we looked at the numbers $a+0 \cdot m, a+1 \cdot m, a+2 \cdot m, \dots, a + (n-1) \cdot m$, we looked at $n$ different numbers. But their remainders are all different too! Since there are exactly $n$ different remainders $\pmod{n}$, each of the above numbers corresponds to exactly one remainder. In particular, some numbers will have remainder exactly $b \pmod{n}$. So a solution exists!

Chinese Remainder Theorem

In this article we are going to talk about the Chinese Remainder Theorem. Before I start, I assume the readers have a basic knowledge about Modular arithmetic, because we are going to work in it a lot later.

This is Chinese Remainder Theorem.

Let $a_1, a_2, a_3,...,a_n \in \mathbb{N}$ where they are pairwise relatively prime and let $b_1, b_2, b_3,...b_n \in\mathbb{Z}$. Then $\exists N\in\mathbb{Z}$ which satisfies the set of simultaneous congruences $$N\equiv b_i\pmod{a_i}$$ where $i=1,2,3,...,n$

In fact, this theorem has been existed and implemented in the early days. Let's try two famous examples and you are going to try another one. Credits to Cut The Knot.

Example 1. (Sun Tsu Suan-Ching, 4th Century AD)

There exists a number which is unknown. If divided by 3, it gives remainder of 2; by 5, the remainder is 3; by 7, the remainder is 2. Find the number. (Find the least, because there are lots of number that satisfy this condition)

Solution 1. We start by writing three congruence relations. We have

$$\begin{align*}x&\equiv 2\pmod3\\x&\equiv 3 \pmod5\\x&\equiv 2\pmod7\end{align*}$$

Now, set $x=3x_1+2$ (why?) such that $x_1$ is integer and substitute it into the second congruence relation. We have

$$\begin{align*}3x_1+2&\equiv3\pmod5\\\Longrightarrow 3x_1&\equiv1\pmod5\end{align*}$$

Here comes the tricky part.

Now, let's try add one 5 to the RHS. We have

$$\begin{align*}3x_1&\equiv 6\pmod5\\\Longrightarrow x_1&\equiv 2\pmod5\end{align*}$$

Cheers! Now set $x_1=5x_2+2$ and substitute it back to the first equation to get

$$3x_1+2=3(5x_2+2)+2=15x_2+8(@)$$

So we can see that 8 is the first number to satisfy the first two congruence relations. But we are not done yet, we need to substitute (@) into the third congruence relation. So, using the steps above, we get

$$15x_2+8\equiv2\pmod7\Longrightarrow 15x_2\equiv-6\pmod7$$

Now, instead of adding 5 on the RHS, we add 7 (why?). We have

$$15x_2\equiv-6\pmod7\Longrightarrow 15x_2\equiv1\pmod7$$

Uh oh, it seems like adding 7 is not enough...So, we will have to keep adding 7 so that it perfectly divides 15. We then have

$$x_2\equiv1\pmod7\Longrightarrow x_2=7x_3+1$$

Last step! Substitute back $x_2=7x_3+6$ into (@), we get $$15x_2+8=15(7x_3+1)+8=105x_3+23$$ and we are done! The least number that satisfies the condition is 23.

Example 2. (A Chinese Idiom Story? Han Xin has 1500 soldiers and about 400 to 500 of them had died. If the soldiers were to stand 3 in a row, we left 2 soldiers, if 5 in a row, we left 4 soldiers, and if 7 in a row, we left 6 soldiers. How many soldiers are there?

Solution 2. Same as example 1, start with 3 congruence relations, $$\begin{align*}x&\equiv 2\pmod3\\x&\equiv 4 \pmod5\\x&\equiv 6\pmod7\end{align*}$$

Now, set $x=3x_1+2$ and substitute the second congruence. We have

$$\begin{align*}3x_1+2&\equiv4\pmod5\\\Longrightarrow 3x_1&\equiv2\pmod5\end{align*}$$

Remember that you can't divide by 3 on both sides for now, we are going to add some more 5's on RHS until $3|2+5k$. So, we have

$$3x_1\equiv12\pmod5\Longrightarrow x_1\equiv4\pmod5\Longrightarrow x_1=5x_2+4$$

and, for $x$, it now becomes $x=3x_1+2=3(5x_2+4)+2=15x_2+14$. Now substitute this to the last congruence and using the steps above, we get $x_2\equiv6\pmod7\Longrightarrow x_2=7x_3+6$ (the steps here are left as an exercise to the reader).

For the penultimate step, substitute $7x_3+6$ into $15x_2+14$ to get $105x_3+104$.

Since the number of soldiers died is around 400 to 500, we can say that the number of soldiers left is $$1000<105x_3+104<1100$$ $$\Longrightarrow 8\frac{8}{15}<x_3<9\frac{17}{35}$$

Therefore, substituting $x_3=9$ we get the number of soldiers left is 1049.

Last problem! This time, you are going to do it.

(Brahma-Sphuta-Siddhanta) Add old woman goes to the market and a horse steps on her basket and crushes the eggs. The rider offers to pay for the damages and asks her how many eggs she had bought. She does not remember the exact number, but when she had taken them out 2 at a time, there was one egg left. The same happened when she picked them out 3, 4, 5, 6 at a time, but when she took them 7 at a time, they came out even. What is the smallest number of eggs she could have had?

Happy solving and that's it for this post.

It is known that $2^{10}\equiv 1 \bmod 11$, while $2^{6}\equiv 1 \bmod 7$. Use this information to find $2^{100} \bmod 77$.

CRT guarantees that we can find $2^{100} \bmod 77$ if we know $2^{100} \bmod 7$ and $2^{100} \bmod 11$.

To start with, notice $2^{100}\equiv (2^4)(2^6)^{16} \equiv 2^4 \equiv 2 \bmod 7$. Similarly, $2^{100}\equiv (2^{10})^{10} \equiv 1 \bmod 11$.

Now we just need to find an integer $n$ between $0$ and $76$ that satisifies $n\equiv 1\bmod 11$ and $n\equiv 2 \bmod 7$. Listing out all the possibilities for $n\equiv 1\bmod 11$, we get $1,12,23,34,45,56,67$. It turns out that $23\equiv 2\bmod 7$, so $23$ is our answer.

Here, I will focusing on some neat methods I know to obtain solutions for given system of congruences using the Chinese Remainder Theorem (CRT).

Via Diophantine Equations

The Chinese Remainder Theorem at heart is really nothing but a linear diophantine equation, so it should be of no surprise that we can draw out an algorithm to generate solutions.

Say we have two relatively prime positive integers $m,n$ and two fixed integers $a,b$ such that $$x\equiv a \pmod{m}$$ $$x\equiv b\pmod{n}.$$

Then, we can express each of the above two equations in terms of a linear equation: $$x=mp+a$$ $$x=nq+b$$ implying that $$mp+a=nq+b \Rightarrow mp-nq=b-a$$

Note that $\gcd(m,n)=1$ which makes possible to compute values for $(p,q)$ using the classic Extended Euclidean Algorithm. In case your unfamiliar with this technique here's a link which will direct you to a really nice article published by AoPS on the topic.

Thus, using our values of $(p,q)$ we plug it back into any one of our earlier equations and generate our desired values for $x$.

Via Bezout's Identity

Say we have our previously stated system of congruences. Then, Bezout's Identity asserts the existence of two integers say $s,t$ such that $$ms+nt=1.$$

So we now can compute $s$ and $t$ using our Extended Euclidean Algorithm. Once, you do compute those integers, a solution $x$ is given by $$\boxed{x=ams+bnt}.$$ In generel if we have the system of congruences $$X\equiv a_i \pmod{m_1}$$ where $\gcd{(m_1,m_2,\cdots{},m_k})=1$, then there exists a unique value $a$ such that $$x\equiv{a}\pmod{M}$$, where $M=m_1m_2\cdots{}m_k$.