2
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ $64 \equiv 1 \pmod 7$, not $2$ and $\equiv 1 \pmod 9$ ,not $7$ $\endgroup$ – Ross Millikan Nov 22 '13 at 14:38
  • $\begingroup$ 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. $\endgroup$ – apnorton Nov 22 '13 at 14:43
  • $\begingroup$ @RossMillikan I know that my answer is wrong but what I need to know is why? what I am doing wrong? Thanks ): $\endgroup$ – Cloules Nov 22 '13 at 14:50
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ thanks but can you please explain how I can solve it using the Chinese Remainder? ): $\endgroup$ – Cloules Nov 22 '13 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.