Check the solution to "Solve the following systems of congruences. 2x≡5(mod 3)..."

remolatg

Answered question

2021-02-18

Solve the following systems of congruences.

2 x \equiv 5 (m o d 3)

3 x + 2 \equiv 3 (m o d 8)

5 x + 4 \equiv 5 (m o d 7)

Answer & Explanation

Aamina Herring

Skilled2021-02-19Added 85 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 a (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,

2 x \equiv 5 (m o d 3)

Since

5 \equiv 2 (m o d 3)

\Rightarrow 2 x \equiv 2 (m o d 3)

By using multiplication property,

2 * 2 x \equiv 2 * 2 (m o d 3)

\Rightarrow 4 x \equiv 4 (m o d 3)

Since

4 \equiv 1 (m o d 3)

\Rightarrow x = 1 (m o d 3)

Now, consider

5 x + 4 \equiv 5 (m o d 7)

By using addition property,

5 x + 4 + (— 4) \equiv 5 + (- 4) (m o d 7)

\Rightarrow 5 x = 1 (m o d 7)

By using multiplication property,

\Rightarrow 5 * 3 x \equiv 1 * 3 (m o d 7)

\Rightarrow 15 x \equiv 3 (m o d 7)

Since

15 \equiv 1 (m o d 7)

\Rightarrow x \equiv 3 (m o d 7)

Therefore, the system of congruences is

x \equiv 1 (m o d 3)

x \equiv 3 (m o d 7)

Since 3 and 7 are relatively prime then

(3, 7) = 1

.
From the first congruence

x = 1 + 3 k

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

1 + 3 k = 3 (m o d 7)

By using addition property,

1 + 3 k + (- 1) \equiv 3 + (- 1) (m o d 7)

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

By using multiplication property,

3 * 3 k \equiv 2 * 3 (m o d 7)

\Rightarrow 9 k \equiv 6 (m o d 7)

Since

9 \equiv 2 (m o d 7)

\Rightarrow 2 k \equiv 6 (m o d 7)

Since

(2, 7) = 1

then by using cancellation law,

\Rightarrow k \equiv (m o d 7)

Thus,

x = 1 + 3 (3) = 10

satisfies the system and

x \equiv 10 (m o d 3 * 7) o r x \equiv (m o d 21)

gives all solutions to the given systems 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?