Chinese Reminder Theorem equation confusion

89 Views Asked by At

I have got the following system of equation to solve using Chinese Reminder Theorem

\begin{cases} 27^{23} \bmod 11 = 4 \\ 27^{23} \bmod 17 = 5 \\ 27^{23} \bmod (11*17) = x \end{cases}

Obviously you can use a calculator to find that $x$ is 158, but I need to find that using CRT.

Here is my take.

System of 3 equations solved by CRT has a form of

\begin{cases} m \bmod M = x \\ n \bmod N = x \\ t \bmod T = x \end{cases}

and is solved as

$$x = ( \\ m*N*T*((N*T)^{-1} \bmod M) + \\ n*M*T*((M*T)^{-1} \bmod N) + \\ t*N*M*((N*M)^{-1} \bmod T) \\ ) \bmod (M*N*T) \\ $$

So I re-arrange it as

\begin{cases} 4 \bmod 11 = 27^{23} \\ 5 \bmod 17 = 27^{23} \\ x \bmod (11*17) = 27^{23} \end{cases}

and then get

$$27^{23} = ( \\ 4*17*11*17*((17*11*17)^{-1} \bmod 11) + \\ 5*11*11*17*((11*11*17)^{-1} \bmod 17) + \\ x*11*17*((11*17)^{-1} \bmod (11*17)) \\ ) \bmod (11*17*11*17) \\ $$

All that is left is solve for $x$.

Except that neither of

$$(17*11*17)^{-1} \bmod 11 \\ (11*11*17)^{-1} \bmod 17 \\ (11*17)^{-1} \bmod (11*17) \\ $$

is invertible.

What am I missing/doing worng?

I assume my re-arrangement is not correct, because $4 \bmod 11$ can't equal to $27^{23}$, it can be at most $10$ because of the $\bmod$, but even then, that doesn't change the fact that the product of modules are not invertible...

1

There are 1 best solutions below

0
On BEST ANSWER

Hint:

Use CRT on $$x\equiv4\pmod{11}$$ and $$x\equiv5\pmod{17}$$