Apparently discordant result using the Chinese Remainder Theorem (CRT)

Question

This post is mainly concerned about

$$2^{107} \pmod {187} \equiv 161$$

---

---

being quickly or immediately solvable. Far from being my problem, I took it as an exercise in applying, as slowly as possible, the CRT after my own post yesterday on the topic. The intermediate results are verified with WolframAlpha to focus on the important points.

Unfortunately something is incorrect in my application, and sorting it out can help shed some additional light on the CRT and related theorems.

Following @lulu's tip, i.e. $187=11\times 17:$

$2^{107}\equiv 7 \pmod{11}$ since applying Euler's theorem,

$2^{\phi(11)}=2^{10}\equiv 1 \pmod{11}.$ Therefore,

$2^{107}\pmod{11}=\left(2^{10}\right)^{10}\cdot 2^7\pmod{11}\equiv2^7\pmod{11}\equiv \color{red}7\pmod {11}.$

---

---

And

$2^{107}\equiv 8 \pmod{17}$ since applying Euler's theorem,

$2^{\phi(17)}=2^{16}\equiv 1 \pmod{17}.$ Therefore,

$2^{107}\pmod{17}=\left(2^{16}\right)^{6}\cdot 2^{11}\pmod{17}\equiv2^7\pmod{11}\equiv \color{blue} 8\pmod {17}.$

---

Applying now the formula of the CRT:

$$x\equiv a_1 b_1 \frac{M}{m_1}+a_2 b_2 \frac{M}{m_2}\pmod M$$

first by calculating

$b_1 = (187/11)^{-1}\pmod{11}\equiv\color{red}2\mod{11}$

---

and

$b_2=(187/17)^{-1}\pmod{17}\equiv\color{blue}{14}\mod{11}$

---

it would seem that

$2^{107}\pmod{187}=\color{red}7\cdot \color{red}2\cdot17 + \color{blue}8\cdot\color{blue}{14} \cdot11\equiv1470 \pmod{187}$

which is not the expected 161.

Where have I missapplied the CRT?

Answer 1

Since $1470= 7 \cdot 187 + 161$ ; $$1470 = 161\pmod{187}$$

Answer 2

Your result is correct since $1470\equiv 161 \mod187$.

The class representative$\mod n$ is unique only if you take it to be non negative and less than $n$.

Answer 3

As already observed, $1470\equiv 161 \bmod 187$ so to equivalence you already had the right answer for $E:=2^{107} \bmod 187$.

You could end up a lot closer in the initial calculation by using $11^{-1} \equiv -3 \bmod 17$ (which I would find from $3\cdot 11 =33 \equiv -1 \bmod 17$). This gives your calculation as

$E \equiv7\cdot2\cdot17 + 8\cdot(-3) \cdot11 = -26 \equiv 161 \pmod{187}$

I find it useful being comfortable with using the small negative instances of a residue class.

The other simple/simplistic approach to solving the CRT portion is simply to search the space of solutions. You know that

$\begin {cases} E\equiv 7 \bmod 11 \\ E\equiv 8 \bmod 17 \end{cases}$

Then you can check the values in range for the $\bmod 17$ criterion formed by $8{+}17k$, that is $\{8,25, 42, 59, 76, 93, 110, 127, 144, 161, 178 \}$, to find which one meets the $\bmod 11$ criterion also.

Following on from this, you could also directly solve for $k$ in $8 + 17k\equiv 7 \bmod 11$:

$\begin{align} 8 + 17k&\equiv 7 \bmod 11\\ 6k &\equiv -1 \bmod 11\\ 2\cdot6k &\equiv -2 \equiv 9\bmod 11\\ 12k \equiv k &\equiv 9 \bmod 11\\ \end{align}$

Then $8+17\cdot 9 = 161$.