Question

Use the construction in the proof of the Chinese remainder theorem to find all solutions to the system of congruences \(\displaystyle{x}\equiv{2}{\left(\text{mod}{3}\right)},{x}\equiv{1}{\left(\text{mod}{4}\right)},{\quad\text{and}\quad}{x}\equiv{3}{\left(\text{mod}{5}\right)}\).

Answer 1

Step 1
Given system of congruences is,
\(\displaystyle{x}\equiv{2}{\left(\text{mod}{3}\right)}\)
\(\displaystyle{x}\equiv{1}{\left(\text{mod}{4}\right)}\)
\(\displaystyle{x}\equiv{3}{\left(\text{mod}{5}\right)}\)
To find all solutions of the system by using Chine's Remainder theorem.
Step 2
To find the solution of the system of congruences:
From he system of congruences,
\(\displaystyle{a}_{{1}}={2},{a}_{{2}}={1},{a}_{{3}}={3}\)
\(\displaystyle{m}_{{1}}={3},{m}_{{2}}={4},{m}_{{3}}={5}\)
m is defined as the product of all \(\displaystyle{m}_{{i}}'{s}\).
Thus, \(\displaystyle={m}_{{1}}\times{m}_{{2}}\times{m}_{{3}}={3}\times{4}\times{5}={60}\)
\(\displaystyle{M}_{{i}}\) is defined as m divided by \(\displaystyle{m}_{{i}}\)
\(\displaystyle{M}_{{1}}=\frac{{m}}{{{m}_{{1}}}}=\frac{{60}}{{3}}={20}\)
\(\displaystyle{M}_{{2}}=\frac{{m}}{{{m}_{{2}}}}=\frac{{60}}{{4}}={15}\)
\(\displaystyle{M}_{{3}}=\frac{{m}}{{{m}_{{3}}}}=\frac{{60}}{{5}}={12}\)
Step 3
To find the inverse of \(\displaystyle{M}_{{i}}\text{mod}{m}_{{i}}\):
\(\displaystyle{M}_{{1}}\text{mod}{m}_{{1}}={20}\text{mod}{3}={2}\)
Inverse is 2, Since 2.2 mod 3 = 4 mod 3 = 1
\(\displaystyle{M}_{{2}}\text{mod}{m}_{{2}}={15}\text{mod}{4}={3}\)
Inverse is 3, Since 3.3 mod 4=9 mod 3=1
\(\displaystyle{M}_{{3}}\text{mod}{m}_{{3}}={12}\text{mod}{5}={2}\)
Inverse is 3, Since 3.2 mod 5=6 mod 5=1.
Inverses are noted as, \(\displaystyle{y}_{{i}}'{s}\):
i.e. \(\displaystyle{y}_{{1}}={2},{y}_{{2}}={3},{y}_{{3}}={3}\).
Step 4
To find the solution:
Solution of the system is,
\(\displaystyle{x}={a}_{{1}}{M}_{{1}}{y}_{{1}}+{a}_{{2}}{M}_{{2}}{y}_{{2}}+{a}_{{3}}{M}_{{3}}{y}_{{3}}\)
\(\displaystyle={\left({\left({2}\times{20}\times{2}\right)}+{\left({1}\times{15}\times{3}\right)}+{\left({3}\times{12}\times{3}\right)}\right)}{\left(\text{mod}{60}\right)}\)
=233 (mod 60)
\(\displaystyle\equiv{53}{\left(\text{mod}{60}\right)}\)
\(\displaystyle{x}\equiv{53}{\left(\text{mod}{60}\right)}\) & thus x = 53 + 60k, with k an integer are all solutions of the system.
Thus, the solution of system is x = 53 + 60k, k is an integer.