# Using the Chinese Remainder Theorem, solve the following simultaneous congruence equations in x. Show all your working. 9x -= 3 mod 15, 5x -= 7 mod 21, 7x -= 4 mod 13.

Using the Chinese Remainder Theorem, solve the following simultaneous congruence equations in x. Show all your working.
$9x\equiv 3\text{mod}15$,
$5x\equiv 7\text{mod}21$,
$7x\equiv 4\text{mod}13$.
You can still ask an expert for help

## Want to know more about Congruence?

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

pivonie8
Step 1
The given congruence equations are
$9x\equiv 3\text{mod}15$
$5x\equiv 7\text{mod}21$
$7x\equiv 4\text{mod}13$
The first congruence can be converted to
$\frac{9x}{3}\equiv \frac{3}{3}\left(\text{mod}\frac{15}{3}\right)$
$3x\equiv 1\text{mod}5$ (By division property${}_{\left(\frac{a}{k}\equiv \frac{b}{k}\left(\text{mod}\frac{n}{gcd\left(n,k\right)}\right)\right)}^{a\equiv b\text{mod}n}\right)$
Now converting all the congruences from
$ax\equiv b\text{mod}n$
to
$x\equiv b\text{mod}n$
by multiplying b with inverse of a under modulo n.
The obtained congruences are
$x\equiv 2\text{mod}5$
$x\equiv 7\text{mod}21$
$x\equiv 8\text{mod}13$
Where ${n}_{1}=5,{n}_{2}=21,{n}_{3}=13,{a}_{1}=2,{a}_{2}=7,{a}_{3}=8\phantom{\rule{1em}{0ex}}\text{and}\phantom{\rule{1em}{0ex}}gcd\left({n}_{1},{n}_{2},{n}_{3}\right)=1$.
Step 2
Now using Chinese remainder theorem solution is obtained by
$x\equiv {a}_{1}{n}_{1}^{\prime }{y}_{1}+{a}_{2}{n}_{2}^{\prime }{y}_{2}+{a}_{3}{n}_{3}^{\prime }{y}_{3}\left(\text{mod}N\right)\to \left(\cdot \right)$
Where $N={n}_{1}{n}_{2}{n}_{3}=5×21×13=1365$
and
${n}_{1}^{\prime }=\frac{N}{{n}_{1}}=273$
${n}_{2}^{\prime }=\frac{N}{{n}_{2}}=65$
${n}_{3}^{\prime }=\frac{N}{{n}_{3}}=105$
and ${y}_{i}$ are inverse of ${n}_{i}^{\prime }$ under modulo ${n}_{i}$, so calculating ${y}_{i}$.
${y}_{1}=2$
${y}_{2}=11$
${y}_{3}=1$
Step 3
Now substituting all the values in expression (*) .
$x\equiv {a}_{1}{n}_{1}^{\prime }{y}_{1}+{a}_{2}{n}_{2}^{\prime }{y}_{2}+{a}_{3}{n}_{3}^{\prime }{y}_{3}\left(\text{mod}N\right)$
$x\equiv 2×273×2+7×65×11+8×105×1\left(\text{mod}1365\right)$
$x\equiv 1092+5005+840\left(\text{mod}1365\right)$