# Using Chinese Remainder Theorem for large modulo

I'm an undergraduate and currently in a course for abstract algebra. I'm trying to resolve the following problem:

Compute which element of $$\mathbb{Z}/2550\mathbb{Z}$$ under the map of the Chinese Remainder Theorem is mapped to $$(\bar{14},\bar{32})$$ in $$\mathbb{Z}/50\mathbb{Z} \times\mathbb{Z}/51\mathbb{Z}$$.

Now I think I should solve the following system:

$$x=14 \mod 50$$

$$x=32 \mod 50$$

$$x=14 \mod 51$$

$$x=32 \mod 51,$$ but if I attempt this using the 'general' CRT I have to compute very large multiplications (such as $$50 \cdot 50 \cdot 51 \cdot 51$$) and since no calculator is used I think I'm on the wrong course.

Any suggestions how to handle this?

• For $\, (\bar 14,\bar 32)\in \Bbb Z_{\large 50}\times \Bbb Z_{\large 51}$ you want $\,x\equiv 14\pmod{\!50},\,$ $\,x\equiv 32\pmod{\!51},\,$ not the other congruences. Where did they come from? – Bill Dubuque Mar 13 at 21:38

## 2 Answers

A very simple way: $$\bmod (50,51)\!:\,\ (14,32)\equiv 16(\color{#0a0}4,\color{#c00}2)\to 16(\color{#90f}{104})=1664\$$ since by Easy CRT

\quad\ \ \begin{align}x&\equiv\color{#0a0} 4\!\!\!\pmod{50}\\ x&\equiv \color{#c00}2\!\!\!\pmod{51}\end{align} $$\iff x\equiv\color{#c00} 2+51\underbrace{\left[\dfrac{\color{#0a0}4-\color{#c00}2}{51}\bmod 50\right]}_{\Large \equiv\ 2/1\ \ \ \ }\!\equiv \color{#90f}{104}\,\pmod{50\cdot 51}$$

Remark  Without factoring $$\, x\equiv 51\cdot\color{#0a0}{14} - 50\cdot \color{#c00}{32}\equiv 714\! -\! 1600\equiv -886\equiv 2550-886\equiv 1664\$$ hence the arithmetic is harder mentally without factoring out $$16$$ (or $$32)$$ at the start.

• (+1) Very nice! – José Carlos Santos Mar 13 at 21:08
• Indeed, very nice. Never heard of the Easy CRT before. – Mathbeginner Mar 14 at 9:51

All you need to do is to solve the system$$\left\{\begin{array}{l}x\equiv14\pmod{50}\\x\equiv32\pmod{51}.\end{array}\right.$$The numbers $$50$$ and $$51$$ are coprime and $$1=51-50$$. Therefore,$$-18(=14-32)=-18\times51+18\times50$$and so$$32-18\times51=14-18\times51=-866\equiv1664\pmod{\!2550}.$$So, the answer is $$\overline{1\,664}$$.

• Is the choice of your initial system arbitrary? So could you also have used $x \equiv 14 (\mod 51)$ and $x \equiv 32(\mod 50)$? When I try to solve your system I Get $1664$. Since I would solve: $x=B_{1}X_{1}C_{1}+B_{2}X_{2}C_{2}$ where $B_{1}=51$, $C_{1}=14$, $B_{2}=50$ and $C_{2}=32$. This then I solve $x=51 \cdot 1 \cdot 14 - 50 \cdot 1 \cdot 32 = 1664$. This I would say $x = \overline{1664}$. Do you agree? – Mathbeginner Mar 13 at 10:31
• Of course I agree. That's what I got, right?! – José Carlos Santos Mar 13 at 10:33
• Ah it is, I first saw you got something like $\overline{932}$ but you edited that right when I was typing I guess. Thanks for the help :) – Mathbeginner Mar 13 at 10:57
• How did you know you only had to use two out of the four equations from the system? Is that always the case when the 'remainders' are equal in two of the equations? – Mathbeginner Mar 13 at 10:58
• @Mathbeginner Since your comment was posted quite after my edition, I didn't think that you meant the first version of my answer (which had a mistake). – José Carlos Santos Mar 13 at 10:59