# Elementary Number Theory: Chinese Remainder Theorem

Using the facts that $1591=37.43$ and $51=3.17$ compute 1591 mod 51 using the Chinese Remainder Theorem.

I started off by letting $x \equiv 1591 \mod 51$ which I then wrote as $x \equiv 1591 \mod 17$ and $x \equiv 1591 \mod 3$ using the information I have been given and rules of modular arithmetic (??). From here I used $37.43$ to give $37 \equiv 3 \mod 17$ and $43 \equiv 9\mod 17$ but I do not know how to go from here.

• Just saying, I would have just divided. $\frac{1591} {51}$ May 21 '16 at 13:04

Hint:

The Chinese remainder theorem says that the (well-defined) map \begin{align*} \mathbf Z/51\mathbf Z&\longrightarrow \mathbf Z/3\mathbf Z\times \mathbf Z/17\mathbf Z\\x\bmod51&\longmapsto (x\bmod3,x\bmod17) \end{align*} is a ring isomorphism. obtained through Bézout's relation between $3$ and $17$: $\;6\cdot 3- 17=1$, and it maps $(\alpha,\beta)$ to $\;(\beta\cdot6\cdot 3-\alpha\cdot 17)\bmod 51$.

Some details:

$37\bmod51$ maps to $(37\bmod3,37\bmod17)=(1,3)$ by the C.R.T.

Similarly, $43\bmod51$ maps to $(1,9)$. Hence $1591=37\cdot43$ maps to $\;(1,3)\cdot(1,9)=(1,10)$. Thus by the inverse isomorphism: $$1591\bmod 51=10\cdot 18-1\cdot17=163=10\bmod51.$$

• In Patrick's voice uhhh could I get another hint....? May 21 '16 at 13:12
• @Pstar007: I've added some details. May 21 '16 at 13:35
• Okay it was pretty clear that you have used the lemma to show that the gcd(3,17) = 1. Could you explain why you have used the alpha & beta part? That would help with the first and last line, everything else has been perfect Bernard. Cheers mate May 21 '16 at 15:27

The fact that $51 = 3 \cdot 17$ (which are coprime) means that by the Chinese remainder theorem we can work separately mod 3 and mod 17, and then work backwards to find out what the answer is mod 51 at the end.

$1591 = 37 \cdot 43 \equiv 1 \cdot 1 = 1 \pmod 3$ and $1591 = 37 \cdot 43 \equiv 3 \cdot 9 = 27 \equiv 10 \pmod {17}$

We notice that 10 itself is $\equiv 10 \pmod {17}$ and $\equiv 1 \pmod 3$, so by the Chinese remainder theorem this is the only solution $\pmod {51}$.

Therefore $1591 \equiv 10 \pmod {51}$.

(We can be more formal about this - for example, we just guessed "10" as being the solution of $x \equiv 10 \pmod {17}$ and $x \equiv 1 \pmod 3$, which can be solved algorithmically.)

• Thanks for the help Joshua. Could you please elaborate upon the part before you mentioned 10 being a solution. I can see why 10 is a solution since its congruent in mod 3 but getting to that point is confusing. Edit: I am referring to the second line you started after your initial statement if that clarifies things for you. May 21 '16 at 13:30
• Let me phrase it better: we know $1591 \equiv n \pmod {51}$ for some $n$, and we also know that $n \equiv 1 \pmod 3$ and $n \equiv 10 \pmod {17}$ (because $1591 \equiv \pmod 3$ and $1591 \equiv 10 \pmod {17}$, which is the content of the second paragraph). I observe that $n = 10$ works as a solution for this pair of equations. May 21 '16 at 22:38