# Thread: Chinese Remainder Theorem

1. ## Chinese Remainder Theorem

.

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
tcynotebook@yahoo.com
0916643858

.

.

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
tcynotebook@yahoo.com
0916643858

.

2. ## Re: Chinese Remainder Theorem

In the first question, if $x\equiv 5\pmod 9$, then $x\equiv 2\pmod 3$, so you only really have two conditions. If you look on the internet, you will find an algorithm to apply the Chinese Remainder Theorem, but it has several steps and I don't think it's very intuitive. So let me give you an alternative. You have:

$x\equiv 5\pmod 9$
$x\equiv 7\pmod {11}$

Since 9 and 11 are relatively prime, the answer will be given modulo 99. The first thing to do is to look at 9 and 11:

$9\equiv 0\pmod 9$
$9\equiv 9\pmod {11}$

$11\equiv 2\pmod 9$
$11\equiv 0\pmod {11}$

If you have more than two moduli, you would look at the products of all but 1 modulus. For example, in the second problem, you have 3, 7, and 11, so you would look at 21, 33, and 77. The idea is to get zeros in all but one equation.

The next step is to multiply by something to make the nonzero numbers 1. For example, the top one would be multiplied by 5 to get $45\equiv 1 \pmod {11}$. Since the numbers are small, you can just list the multiples of 9 and choose the one that is congruent to $1\pmod {11}$. For large numbers, you would use the Extended Euclidean Algorithm. In this case, it turns out that 5 is the number to multiply by to get 1 for both the top set of equations and the bottom set of equations.

$45\equiv 0\pmod 9$
$45\equiv 1\pmod {11}$

$55\equiv 1\pmod 9$
$55\equiv 0\pmod {11}$

Now you have (0,1) and (1,0) so to get (5,7), you take 7 times the first set of equations and add 5 times the second set of equations.

$590\equiv 5\pmod 9$
$590\equiv 7\pmod {11}$

You now reduce 590 (mod 99) to get the answer 95. Of course, you should always check your answer:

$95\equiv 5\pmod 9$
$95\equiv 7\pmod {11}$

So that's the method. In problem (2), you use the same method, the only difference being you have 3 moduli to work with instead of 2.

For problem (3),

$x^2\equiv 26\pmod {77}$,

since $77=7*11$, you can break it into two equations:

$x^2\equiv 26\pmod 7$
$x^2\equiv 26\pmod {11}$

and reducing,

$x^2\equiv 5\pmod 7$
$x^2\equiv 4\pmod {11}$

The second equation has solutions $x\equiv 2\pmod {11}$ and $x\equiv 9\pmod {11}$, but the first one has no solutions. The squares (mod 7) are 0, 1, 4, 2, 2, 4, and 1. So the system has no solutions, and therefore the original problem has no solutions, and that's our answer.

If the problem were $x^2\equiv 15\pmod {77}$, then you would have

$x^2\equiv 1\pmod 7$ with solutions 1 and 6
$x^2\equiv 4\pmod {11}$ with solutions 2 and 9

and then you would take all combinations:
$1 \pmod 7$ and $2 \pmod {11}$ gives $x\equiv 57\pmod {77}$
$1 \pmod 7$ and $9 \pmod {11}$ gives $x\equiv 64\pmod {77}$
$6 \pmod 7$ and $2 \pmod {11}$ gives $x\equiv 13\pmod {77}$
$6 \pmod 7$ and $9 \pmod {11}$ gives $x\equiv 20\pmod {77}$

so the answer would be x is congruent to 13, 20, 57, or 64 (mod 77).

The same process is used in problem (4). You will get zero solutions if either the (mod 7) equation or the (mod 11) equation has no solutions, or you will get 4 solutions by combining the two solutions (mod 7) with the two solutions (mod 11).

- Hollywood

3. ## Re: Chinese Remainder Theorem

See attached file -

4. ## Re: Chinese Remainder Theorem

The Chinese Remainder Theorem only works if the moduli are pairwise relatively prime. In problem (1), you have 3, 9, and 11, but 3 and 9 are not relatively prime.

- Hollywood

5. ## Re: Chinese Remainder Theorem

Please check for my solution draft paper -

6. ## Re: Chinese Remainder Theorem

It appears you ignored the advice Hollywood gave you for question 1. Not surprisingly, you got a wrong answer. For example, if $k=0$ then you have $x=18$. That does not match two of the original equivalencies. I haven't checked the second one.

7. ## Re: Chinese Remainder Theorem

For the first page, please read my previous two posts.

On the second page, everything is correct up to the very end, where you made an arithmetic error: 308 + 396 + 1050 = 1754, so the answer is 137 (mod 231).

- Hollywood

8. ## Re: Chinese Remainder Theorem

Thank you very much

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

(I need urgent assistance for this exercise)

9. ## Re: Chinese Remainder Theorem

When you're searching for $x^2 \equiv 26 \pmod 7$, instead of looking at what 26 is congruent to (26, 33, 40, ...), you should look at what x might be congruent to. There are only 7 possibilities: 0, 1, 2, 3, 4, 5, and 6. The squares (reduced mod 7) are 0, 1, 4, 2, 2, 4, and 1. But 26 is congruent to 5, so there are no solutions.

In the original problem, $x^2 \equiv 26 \pmod {77}$, we need to find an x that solves both $x^2 \equiv 26 \pmod 7$ and $x^2 \equiv 26 \pmod {11}$. No solutions to the first part means there are no solutions to the original problem.

You can use a similar process to solve problem (4).

- Hollywood

10. ## Re: Chinese Remainder Theorem

Therefore how to write the formal statement in university exam answer sheet - if there is no solution

11. ## Re: Chinese Remainder Theorem

Originally Posted by vokoyo
Therefore how to write the formal statement in university exam answer sheet - if there is no solution
That is the formal answer. $\nexists x \in \mathbb{Z}$ such that $x^2 \equiv 26 \pmod{7}$. Or simply, "No solutions exist". So long as you justify your answer (as Hollywood did), you should be given full credit.

Wolframalpha's Answer

12. ## Re: Chinese Remainder Theorem

A million thanks to all of you