0
$\begingroup$

I am doing a practice problem for my final which asks:

Solve the following Chinese Remainder Theorem: $$ x \equiv 2 \pmod{3}, \\ x \equiv 3 \pmod{5}, \\ x \equiv 5 \pmod{7}, \\ x \equiv 7 \pmod{11} \\ x \equiv 11 \pmod{13} $$

From the first I can conclude that $x = 3k + 2$ for some $k \in \mathbb{Z}$.

Now I can apply that to the second equation which gives $ 3k+2 \equiv 3 \pmod{5}.$

Then I get lost here. Do I subtract $2$ and solve $ 3k \equiv 1 \pmod{5}$?

I don't have a solid understanding of solving the Chinese Remainder Theorem algebraically in general.

$\endgroup$
1
$\begingroup$

\begin{align} x &\equiv 2 \pmod 3 \\ x &= 2 + 3a \\ \hline x &\equiv 3 \pmod 5 \\ 2+3a &\equiv 3 \pmod 5 \\ 3a &\equiv 1 \pmod 5 \\ a &\equiv 2 \pmod 5 \\ a &= 2 + 5b \\ x &= 2 + 3(2 + 5b)\\ x &= 8 + 15b \\ \hline x &\equiv 5 \pmod 7 \\ 8 + 15b &\equiv 5 \pmod 7 \\ 1 + b &\equiv 5 \pmod 7 \\ b &\equiv 4 \pmod 7 \\ b &= 4 + 7c \\ x &= 8 + 15(4 + 7c) \\ &\text{and so on...} \end{align}

$\endgroup$
  • $\begingroup$ Could you explain how you went from "3a is congruent to 1 mod 5" to "a is congruent to 2 mod 5", and "8 + 1b is congruent to 5 mod 7" to "1 + b is congruent to 5 mod 7"? Other than that I understand how to solve it. $\endgroup$ – Erik Littleton Jun 5 '16 at 3:56
  • $\begingroup$ @EriqueB. : Trial and error. I looked at $3a \equiv 1 \pmod 5$ and thought of $3a = 6$. $8 + 1b \pmod 7 \equiv 1 + b \pmod 7$ since $8 \equiv 1 \pmod 7$. $\endgroup$ – steven gregory Sep 12 '16 at 3:31
0
$\begingroup$

Both mod 3 and mod 11 had the form $x≡ -4$. Combine both:
$$ x≡ -4 \text{ (mod 33)}$$ The rest (mod 5, 7, 13) had the form $x≡ -2$. Combine the rest:
$$ x≡ -2 \text{ (mod 455)} → x=455y-2$$ Combine all modulo equations: $$ 455y-2 ≡ -4 \text{ (mod 33)}$$ $$ -7y≡ -2≡ -35 \text{ (mod 33)}$$ $$ y≡5 \text{ (mod 33)} → y=33z+5$$ Substitute back to x: $$ x= 455(33z+5)-2= 15015z + 2273 $$ $$x≡ 2273 \text{ (mod 15015)}$$

$\endgroup$

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.