Answered: "Solve the following systems of congruences. x≡4(mod 5)..."

ringearV

Answered question

2021-02-21

Solve the following systems of congruences.

x \equiv 4 (m o d 5)

x \equiv 3 (m o d 8)

x \equiv 2 (m o d 3)

Answer & Explanation

un4t5o4v

Skilled2021-02-22Added 105 answers

Formula used:
1) Theorem: System of congruences:
Let m and n be relatively prime and a and b integers. There exists an integer x that satisfies the system of congruences

x \equiv (m o d m)

x \equiv b (m o d n)

Furthermore, any two solutions x and y are congruent modulo mn.
2) Theorem: Addition and Multiplication Properties:
If

a = b (m o d n)

and x is any integer, then

a + x \equiv b + x (m o d n) a n d a x \equiv b x (m o d n)

.
3) Theorem: Cancellation Law:
If

a x \equiv a y (m o d n) a n d (a, n) = 1, t h e n x \equiv y (m o d n)

.
Explanation:
Consider the system of congruences

x \equiv 4 (m o d 5)

x \equiv 2 (m o d 3)

Since 5 and 3 are relatively prime, then

(5, 3) = 1

.
Then, by using theorem there exists an integer x that satisfies the system of congruences.
From the first congruence

x = 4 + 5 k

for some integer k and substitute this expression for x into the second congruence.

4 + 5 k \equiv 2 (m o d 3)

By using addition property,

4 + 5 k + (— 4) \equiv 2 + (— 4) (m o d 3)

\Rightarrow 5 k = — 2 (m o d 3)

Since

5 \equiv 2 (m o d 3)

\Rightarrow 2 k \equiv - 2 (m o d 3)

Since

(2, 3) = 1

then by using cancellation law,

\Rightarrow k \equiv - 1 (m o d 3)

Now,

- 1 \equiv 2 (m o d 3)

,
Therefore,

k = 2 (m o d 3)

Thus,

x = 4 + 5 (2) = 14

satisfies the system and

x = 14 (m o d 5 * 3)

x = 14 (m o d 15)

gives all solutions to the given system of congruences.

Do you have a similar question?

Recalculate according to your conditions!

New Questions in High school geometry

Didn't find what you were looking for?