ringearV

Answered

2021-02-21

Solve the following systems of congruences.

$x\equiv 4(mod\text{}5)$

$x\equiv 3(mod\text{}8)$

$x\equiv 2(mod\text{}3)$

Answer & Explanation

un4t5o4v

Expert

2021-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 (mod\text{}m)$

$x\equiv b(mod\text{}n)$

Furthermore, any two solutions x and y are congruent modulo mn.

2) Theorem: Addition and Multiplication Properties:

If$a=b(mod\text{}n)$ and x is any integer, then $a+x\equiv b+x(mod\text{}n)\text{}and\text{}ax\equiv bx(mod\text{}n)$ .

3) Theorem: Cancellation Law:

If$ax\equiv ay(mod\text{}n)\text{}and\text{}(a,n)=1,\text{}then\text{}x\equiv y(mod\text{}n)$ .

Explanation:

Consider the system of congruences

$x\equiv 4(mod\text{}5)$

$x\equiv 2(mod\text{}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+5k$ for some integer k and substitute this expression for x into the second congruence.

$4+5k\equiv 2(mod\text{}3)$

By using addition property,

$4+5k+(\u20144)\equiv 2+(\u20144)(mod\text{}3)$

$\Rightarrow 5k=\u20142(mod\text{}3)$

Since$5\equiv 2(mod\text{}3)$ ,

$\Rightarrow 2k\equiv -2(mod\text{}3)$

Since$(2,3)=1$ then by using cancellation law,

$\Rightarrow k\equiv -1(mod\text{}3)$

Now,$-1\equiv 2(mod\text{}3)$ ,

Therefore,$k=2(mod\text{}3)$

Thus,$x=4+5(2)=14$ satisfies the system and $x=14(mod\text{}5\ast 3)$ or $x=14(mod\text{}15)$ gives all solutions to the given system of congruences.

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

Furthermore, any two solutions x and y are congruent modulo mn.

2) Theorem: Addition and Multiplication Properties:

If

3) Theorem: Cancellation Law:

If

Explanation:

Consider the system of congruences

Since 5 and 3 are relatively prime, then

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

From the first congruence

By using addition property,

Since

Since

Now,

Therefore,

Thus,

Most Popular Questions