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.
0

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}\)
...