# 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!!

-

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.

-
Presumably the final $\iff$ should be "and". –  Math Gems Feb 4 '13 at 6:32

Reduce all the statements to equivalent statements to a prime residue system And then use the chinese remainder theorem

-
finding prime factorization of each $n$ then omit the common one? –  Paul Feb 4 '13 at 1:51
Thats how id do it. factorize and the make the statement into equivalent statements for the prime powers. For example: $x\equiv 3mod 14$ if and only if $x\equiv 3 mod 7$ and $x \equiv 3 mod 2$ –  Jorge Fernández Feb 4 '13 at 2:00

Case (b) you'd apply the extended chinese remainder theorem. In this case, as $3 \equiv 8 \pmod{\gcd(10, 15)}$, there is a solution, and it will be unique modulo $\mathrm{lcd}(10, 15, 84)$.

Essentially you solve the system $x \equiv 3 \pmod{15}$ and $x \equiv 5 \pmod{84}$, and patch up the solution to agree with your equivalence modulo 10.

-