elementary number theory - Solving simultaneous linear congruences

(a) $x≡5\pmod 7\;\;,\; x≡7\pmod{11}\;\;,\;\;x≡3\pmod{13}$

(b) $x≡3\pmod{10}\;\;,\;\; x≡8\pmod{15}\;\;,\;\;x≡5\pmod{84}$

---

for (a) I have a rough idea how to do it, its like:

$n_1=7,n_2=11,n_3=13$ then $n=7·11·13=1001$

${1001\over7}·k_1≡1mod(7)$

${1001\over11}·k_2≡1mod(11)$

${1001\over13}·k_3≡1mod(13)$

Hence, $k_1=[5], k_2=[4], k_3=[12]$

$x_0=(11·13)·5·5+(7·13)·4·7+(7·11)·(-1)·3=287$

the solution set is $x=x_0+k_n, k\leftarrow\mathbb{Z}, x=887+k(1001)$

Im not sure if im correct, but i just follow the standard procedure

(b) for this one, what should I do the the $n$'s are not coprime, or prime???

Thank you!!

Answer

You've got the idea...

Apply prime factorization to each of the moduli $n$, omit common factors, proceed in much the way you did for (a), and transform each statement in the system into equivalent congruences for the prime powers: (i.e. to a prime residue system). E.g.

$$x \equiv 3 \pmod{10} \iff x \equiv 3 \pmod 2 \;\text{and}\; x \equiv 3 \pmod 5\,.$$

And of course, you'll then want to use the Chinese Remainder Theorem and/or the extended CRT.