Derived Chinese Remainder Theorem question

33 Views Asked by At

If we know an example of the CRT, e.g.:

What $n$ is $3\pmod 7$ and $5\pmod{11}$?

and we know the answer, in this case $n=38$, is it any easier to find the answer to a related CRT question, for example:

What $n$ is $6\pmod 7$ and $3\pmod{11}$?

1

There are 1 best solutions below

1
On

The questions to ask are

$$\text{What $a$ is $1 \bmod 7$ and $0 \bmod{11}$? $\ (a=22)$}$$

and

$$\text{What $b$ is $0 \bmod 7$ and $1 \bmod{11}$? $\ (b=56)$}$$

Then the answer to $$\text{What n is 3(mod7) and 5(mod11)?}$$

is $3a+5b \pmod{77} \equiv 38$ and

Then the answer to $$\text{What n is 6(mod7) and 3(mod11)?}$$

is $6a+3b \pmod{77} \equiv 69$.