# Use the construction in the proof of the Chinese remainder theorem to find all solutions to the system of congruences x -= 2 (mod 3), x -= 1 (mod 4), and x -= 3 (mod 5).

Question
Congruence
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)}$$.

2021-02-22
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.

### Relevant Questions

Consider the system of linear congruences below:
$$\displaystyle{x}\equiv{2}{\left(\text{mod}{5}\right)}$$
$$\displaystyle{2}{x}\equiv{22}{\left(\text{mod}{8}\right)}$$
$$\displaystyle{3}{x}\equiv{12}{\left(\text{mod}{21}\right)}$$
(i)Determine two different systems of linear congruences for which the Chinese Remainder Theorem can be used and which will give at least two of these solutions.
Find all solutions to the following system of linear congruences: $$\displaystyle{x}\equiv{1}\text{mod}{2},{x}\equiv{2}\text{mod}{3},{x}\equiv{3}\text{mod}{5},{x}\equiv{4}\text{mod}{7},{x}\equiv{5}\text{mod}{11}$$.
To determine: The smallest nonnegative integer x that satisfies the given system of congruences.
$$\displaystyle{x}\equiv{3}\pm{o}{d}{\left\lbrace{1917}\right\rbrace}$$
$$\displaystyle{x}\equiv{75}\pm{o}{d}{\left\lbrace{385}\right\rbrace}$$
To determine: The smallest nonnegative integer x that satisfies the given system of congruences.
$$\displaystyle{x}\equiv{3}\pm{o}{d}{5}$$
$$\displaystyle{x}\equiv{7}\pm{o}{d}{8}$$
To determine: The smallest nonnegative integer x that satisfies the given system of congruences.
$$\displaystyle{x}\equiv{3}\pm{o}{d}{5}$$
$$\displaystyle{x}\equiv{3}\pm{o}{d}{7}$$
To determine: The smallest nonnegative integer x that satisfies the given system of congruences.
$$\displaystyle{x}\equiv{1}\pm{o}{d}{\left\lbrace{4}\right\rbrace}$$
$$\displaystyle{x}\equiv{8}\pm{o}{d}{\left\lbrace{9}\right\rbrace}$$
$$\displaystyle{x}\equiv{10}\pm{o}{d}{\left\lbrace{25}\right\rbrace}$$
To determine: The smallest nonnegative integer x that satisfies the given system of congruences.
$$\displaystyle{x}\equiv{1}\pm{o}{d}{4}$$
$$\displaystyle{x}\equiv{8}\pm{o}{d}{9}$$
$$\displaystyle{9}{x}\equiv{3}\text{mod}{15}$$,
$$\displaystyle{5}{x}\equiv{7}\text{mod}{21}$$,
$$\displaystyle{7}{x}\equiv{4}\text{mod}{13}$$.
$$\displaystyle{x}\equiv{5}{\left({b}\text{mod}{24}\right)}$$
$$\displaystyle{x}\equiv{17}{\left({b}\text{mod}{18}\right)}$$
$$\displaystyle{x}\equiv{1003}\pm{o}{d}{\left\lbrace{17},{369}\right\rbrace}$$
$$\displaystyle{x}\equiv{2974}\pm{o}{d}{\left\lbrace{5472}\right\rbrace}$$