Ask question

# 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). # 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 asked 2021-02-21
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)}$$.

## Answers (1) 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 asked 2021-01-13
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. asked 2021-02-04
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}$$. asked 2021-05-04
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}$$ asked 2021-04-16
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}$$ asked 2021-02-18
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}$$ asked 2021-05-06
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}$$ asked 2021-03-10
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}$$ asked 2020-10-18
Using the Chinese Remainder Theorem, solve the following simultaneous congruence equations in x. Show all your working.
$$\displaystyle{9}{x}\equiv{3}\text{mod}{15}$$,
$$\displaystyle{5}{x}\equiv{7}\text{mod}{21}$$,
$$\displaystyle{7}{x}\equiv{4}\text{mod}{13}$$. asked 2021-04-25
Solve system of equation by chinese remainder theorem:
$$\displaystyle{x}\equiv{5}{\left({b}\text{mod}{24}\right)}$$
$$\displaystyle{x}\equiv{17}{\left({b}\text{mod}{18}\right)}$$ asked 2021-03-25
To determine: The smallest nonnegative integer x that satisfies the given system of congruences.
$$\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}$$
...