Find the element in $\mathbb{Z}/143\mathbb{Z}$ whose image is $(\overline{10},\overline{11})$ under the Chinese remainder theorem

Question

Find the element in $\mathbb{Z}/143\mathbb{Z}$ whose image is $(\overline{10},\overline{11})$ in $\mathbb{Z}/11\mathbb{Z} \times \mathbb{Z}/13\mathbb{Z}$ under the Chinese remainder theorem

---

So I figured we must find an element $\overline{x}$ in $\mathbb{Z}/143\mathbb{Z}$ that satisfies:

$x \equiv 10 \pmod {11} $

$x \equiv 11 \pmod {13} $

Applying the Chinese remainder theorem gives us $x=76$.

Can I then simply conclude that the element we're looking for in $\mathbb{Z}/143\mathbb{Z}$ is $\overline{76}$?

Answer 1

Hint:
Find an element $x$ with $x\equiv1\pmod {11}$ and $x\equiv0\pmod {13}.$ Similarly find $y$ with $\begin{cases}y\equiv0\pmod{11}\\y\equiv1\pmod {13}\end{cases}.$ Then $10x+11y\pmod{143}$ is what you want.

Hope this helps.

Answer 2

By Bezout's identity we know that we can find $ x, y$ such that $ 11x + 13y = 1 $. Using the Euclidean algorithm, we have:

$$ 13 = 11\cdot 1 + 2 $$ $$ 11 = 2 \cdot 5 + 1 $$ $$ 2 = 2 \cdot 1 + 0 $$

and now we substitute back:

$$ 1 = 11 - 2 \cdot 5 = 11 - (13 - 11) \cdot 5 = 11 \cdot 6 - 13 \cdot 5 $$

This helps us because now we can explicitly produce the solution. Indeed, I claim that the solution is $ 11 \cdot 6 \cdot 11 - 13 \cdot 5 \cdot 10 = 76 $. We have that

$$ 11 \cdot 6 \cdot 11 - 13 \cdot 5 \cdot 10 \equiv 11 \cdot 6 \cdot 10 - 13 \cdot 5 \cdot 10 \equiv 10 \pmod{11} $$

and

$$ 11 \cdot 6 \cdot 11 - 13 \cdot 5 \cdot 10 \equiv 11 \cdot 6 \cdot 10 - 13 \cdot 5 \cdot 11 \equiv 11 \pmod{13} $$

Generally, if $ I $ and $ J $ are comaximal ideals of a ring $ R $, we can find $ i \in I $ and $ j \in J $ such that $ i + j = 1_R $. Then, the expression $ bi + aj $ lies in the cosets $ a + I $ and $ b + J $. In the case that $ R $ is an Euclidean domain, the Euclidean algorithm gives an easy way of computing $ i $ and $ j $ explicitly.

Answer 3

Solving the CRT by substitution directly, we have: $$\begin{align} x &=11k+10 \\ 11k+10 &\equiv 11 \bmod 13 \\ 11k &\equiv 1 \bmod 13 \\ k &\equiv 11^{-1} \bmod 13 \\ \end{align}$$

Then it's easy to find $11^{-1} = 6 \pmod {13}$ (since $66\equiv 1 \bmod 13$), and thus $k=6$ and $x=76 \;\square$.

And yes, that's the residue class that satisfies your initial problem statement.