# Having A Problem With Chinese Remainder Theorem

Find all solutions, if any, to the system of congruences

\begin{align} x&\equiv 7 \pmod{9}\\ x&\equiv 4 \pmod{12}\\ x&\equiv 16 \pmod{21} \end{align}

Solution: Using the Chinese Remainder theorem, we get that this system is equivalent to the 5 equations: \begin{align} x&\equiv 7 \pmod{9} \\ x&\equiv 0 \pmod{4} \\ x&\equiv 1 \pmod{3} \\ x&\equiv 2 \pmod{7} \\ x&\equiv 1 \pmod{3} \\ \end{align}

The 3rd and 5th equations are superfluous, and the total system has general solution $x\equiv16 \pmod {252}$."

I can't seem to get 16 all I get is 64, why?

I do it like this \begin{align} x&\equiv a_1M_1y_1+a_2M_2y_2+a_3M_3y_3 \pmod{16}\\ &\equiv 7\cdot28\cdot4 + 0 + 2\cdot36\cdot4 \pmod{16}\\ &\equiv 1072\pmod{16} \\ &\equiv 64 \pmod{16} \end{align}

• $64 \equiv 1 \pmod 7$, not $2$ and $\equiv 1 \pmod 9$ ,not $7$ – Ross Millikan Nov 22 '13 at 14:38
• I edited your question to use $\LaTeX$ formatting. Please ensure that I haven't inadvertently changed your question via a typo, and see if you can find out what sort of markup is required to format math text on this site. – apnorton Nov 22 '13 at 14:43
• @RossMillikan I know that my answer is wrong but what I need to know is why? what I am doing wrong? Thanks ): – Cloules Nov 22 '13 at 14:50

I do small ones of these by hand. From the first, we have $x=7+9k$ Taking that mod $4$, we get $x=1+3k \pmod 4$ and we want this to be $\equiv 0$. By inspection, $k=1$ works and we have $x=16 \pmod {36}$. Then $16 \equiv 2 \pmod 7$ and we are done, arriving at the solution $16 \pmod {252}$
You should be working mod $9 \cdot 4 \cdot 7=252,$ not mod $16$. Note that $64 \equiv 0 \pmod {16}$ Your $M_2$ should not be zero, it should be $1 \pmod 4$ and $0 \pmod {9,7}$, which is $-63 \pmod {252}$ Your $M_3$ should be $36 \pmod {252}$ I don't know what your $y_1,y_2,y_3$ are. That multiplication by $4$ is the source of your problem. Then you have the solution is $x\equiv 7\cdot 28+0\cdot (-63)+2\cdot 36=268\equiv 16 \pmod {252}$