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$
2
  • $\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$ 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$ 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$

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .