Elementary Number Theory: Chinese Remainder Theorem

136 Views Asked by At

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.

2

There are 2 best solutions below

3
On BEST ANSWER

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.$$

2
On

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.)