2

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

apnorton
  • 17,706
Cloules
  • 21
  • 2
  • 1
    $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

1 Answers1

1

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

Ross Millikan
  • 374,822