# How to solve Chinese Remainder Theorem

• MHB
• vokoyo
In summary, the problem is that the $m_i$ are not pairwise co-prime, so we need to do something about that first. The first two equations are x= 2 (mod 3) and x= 5 (mod 9). The second equation means that x= 5+ 9m for some integer m. But then we can write x= 2+ 3+ 9m= 2+ 3(3m+1) so the first equation is also satisfied. If that had been any number but "2" in the first equation there would be no x satisfying both equations. The approach is correct, but a precondition of CRT is not met.
vokoyo
Dear

How to solve the CRT for cryptography as below -

(1) Find x such that

x = 2(mod3)
x = 5(mod9)
x = 7(mod11)

(2) Find x such that

x = 2(mod3)
x = 4(mod7)
x = 5(mod11)

(3) Find x such that x^2 = 26(mod77)

(4) Find x such that x^2 = 38(mod77)

Prayerfully
Tron Orino Yeong

I have edited your post to remove the blank space above and below the content, and to remove the personal information for your protection.

Please provide your sample solution so that I can improve my calculus skills

vokoyo said:
Dear

How to solve the CRT for cryptography as below -

(1) Find x such that

x = 2(mod3)
x = 5(mod9)
x = 7(mod11)

(2) Find x such that

x = 2(mod3)
x = 4(mod7)
x = 5(mod11)

Hi Tron Orino Yeong, welcome to MHB! ;)

To apply CRT we need that the modulo numbers are co-prime.
For (1) we can observe that the second equation x=5(mod 9) implies the first equation.
So we can leave out the first equation, reducing it to a standard CRT problem.
Problem (2) already has co-prime modulo numbers, meaning it's already a standard CRT problem.

The general solution for CRT (assuming co-prime $m_i$) is:
$$\begin{cases}x\equiv a_1\pmod{m_1}\\ ... \\ x\equiv a_k\pmod{m_k}\end{cases} \quad\Rightarrow\quad x\equiv \left[\frac M{m_1}\right]^{-1}_{m_1}\frac M{m_1}\cdot a_1 + ... + \left[\frac M{m_k}\right]^{-1}_{m_k}\frac M{m_k}\cdot a_k \pmod{M}$$
where $M=m_1\cdot ...\cdot m_k$ and $\left[\frac M{m_i}\right]^{-1}_{m_i}$ is the multiplicative inverse modulo $m_i$.

How about applying the formula to find the solutions?

vokoyo said:
Dear

How to solve the CRT for cryptography as below -

(1) Find x such that

x = 2(mod3)
x = 5(mod9)
x = 7(mod11)
First note that 3 divides 9 so there may not be a solution. In fact, if x= 5 (mod 9) then x= 5+ 9n for some integer n. But then x= 5+ 9n= 2 (mod 3) since 9= 0 (mod 3).

Putting x= 5+ 9n into the third equation, x= 5+ 9n= 7 (mod 11) so 9n= 2 (mod 11). That says that 9n= 2+ 11m for some integer m. That is equivalent to 9n- 11m= 2. But 11- 9= 2 so it is sufficient to take n= m= -1. But then n= -1+ 11k and m= -1+ 9k is also a solution for any k: 9(-1+ 11k)- 11(-1+ 9k)= -9+ 99k+ 11- 99k= 2 for all k.

Set n in x= 5+ 9n equal to -1+ 11k gives x= 5+ 9(-1+ 11k)= -4+ 99k.
If you don't like negative numbers, change k by 1: -4+ 99+ 99k= 95+ 99k.
2) Find x such that

x = 2(mod3)
x = 4(mod7)
x = 5(mod11)

(3) Find x such that x^2 = 26(mod77)

(4) Find x such that x^2 = 38(mod77)

Prayerfully
Tron Orino Yeong

#### Attachments

• 123.jpg
71.7 KB · Views: 90
• My own solution.jpg
13.6 KB · Views: 71
Last edited:
The approach is correct.
However, a precondition of CRT is not met.
That is, it requires that the $m_i$ are pairwise co-prime.
Since $m_1=3$ and $m_2=9$ are not co-prime, we need to do something about that first.

Observe that any solution of the second equation with $m_2=9$ satisfies the first equation (with $m_1=3$).
So if we leave out the first equation completely, we will find the same solutions, and we satisfy the precondition of CRT.

The first two equations are x= 2 (mod 3) and x= 5 (mod 9). The second equation means that x= 5+ 9m for some integer m. But then we can write x= 2+ 3+ 9m= 2+ 3(3m+1) so the first equation is also satisfied. If that had been any number but "2" in the first equation there would be no x satisfying both equations.

For example, if x= 1 (mod 3) then x= 1+ 3n. Putting that into x= 5(mod 9) we would have 1+ 3n= 5+ 9m or 3(n- 3m)= 4. But the left side is a multiple of 3 and the right side isn't.

Please check for my solution draft paper -

#### Attachments

• 投影片1.JPG
22.2 KB · Views: 63
• 投影片2.JPG
22.6 KB · Views: 70

View attachment 8501

(I need urgent assistance for this exercise)

#### Attachments

• 投影片1.JPG
22.6 KB · Views: 77
Did you check by filling in your solutions in the original equations?

You should find that (1) does not fit.
Your solution is wrong, because the set of equations does not satisfy the precondition of CRT that the $m_i$ must be co-prime.

You should find that (2) does not fit.
Everything is correct, except for a calculation mistake at the very end.
It should be:
$$308+396+1050 \equiv 1754 \equiv 137 \pmod{231}$$

I'm not quite sure what you did for (3).
Your approach seems to be correct, but in the first step, we should have:
$$x^2\equiv 26 \pmod{77} \quad\Rightarrow\quad x^2\equiv 26 \equiv 5 \pmod {7}$$
Checking $x\equiv 0,1,2,3,4,5,6 \pmod{7}$ shows that there is no solution.

Same thing for (4).
$$x^2\equiv 38 \pmod{77} \quad\Rightarrow\quad x^2\equiv 38 \equiv 3 \pmod {7}$$
Checking $x\equiv 0,1,2,3,4,5,6 \pmod{7}$ shows that there is no solution either.

A million thanks to all of you

## 1. What is the Chinese Remainder Theorem?

The Chinese Remainder Theorem is a mathematical theorem that provides a method for finding a number that is a solution to a system of congruences (equations with remainders). It is often used in number theory and cryptography.

## 2. How does the Chinese Remainder Theorem work?

The Chinese Remainder Theorem works by finding a number that satisfies a set of congruences. This number is known as the "residue" and is found by using the Chinese Remainder Theorem formula, which involves calculating the product of the remainders, multiplying them by their respective modular inverses, and then summing them together.

## 3. What are some practical applications of the Chinese Remainder Theorem?

The Chinese Remainder Theorem has many practical applications in fields such as computer science, coding theory, and cryptography. It is commonly used in algorithms for error correction codes, data compression, and secret sharing schemes.

## 4. What are the limitations of the Chinese Remainder Theorem?

While the Chinese Remainder Theorem is a powerful tool for solving congruences, it has some limitations. It can only be used when the moduli (numbers in the congruences) are pairwise relatively prime, meaning they have no common factors. It also does not work for certain types of congruences, such as those with non-prime moduli.

## 5. How can I solve the Chinese Remainder Theorem problem step by step?

To solve a Chinese Remainder Theorem problem, follow these steps:
1. Write out the system of congruences in the form x ≡ a (mod m).
2. Check that the moduli are pairwise relatively prime. If not, use the Chinese Remainder Theorem formula to find a solution.
3. Find the modular inverses of the remainders.
4. Use the Chinese Remainder Theorem formula to calculate the residue.
5. Check that the residue satisfies all of the congruences in the system.
6. If it does, then the residue is the solution. If not, add or subtract the modulus from the residue until it does satisfy all of the congruences.

Replies
2
Views
2K
Replies
1
Views
2K
Replies
1
Views
1K
Replies
3
Views
1K
Replies
4
Views
2K
Replies
4
Views
2K
Replies
2
Views
4K
Replies
1
Views
1K
Replies
5
Views
2K
Replies
3
Views
1K