MHB How to solve Chinese Remainder Theorem

[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)

Please help me by provide your advice and suggestion

Prayerfully
Tron Orino Yeong

 

[MarkFL]

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

 

[vokoyo]

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

 

[I like Serena]

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! ;)

Let's start with the first 2 problems.

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?

 

[HOI]

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)

Please help me by provide your advice and suggestion

Prayerfully
Tron Orino Yeong

 

[vokoyo]

View attachment 8490

 

[I like Serena]

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.

 

[HOI]

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.

 

[vokoyo]

Please check for my solution draft paper -

 

[vokoyo]

Please help me for question (3) and question (4)

View attachment 8501

(I need urgent assistance for this exercise)

 

[I like Serena]

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.

 

[vokoyo]

A million thanks to all of you