### Select your language

Suggested languages for you:

Americas

Europe

Q12E

Expert-verified
Found in: Page 449

### Abstract Algebra: An Introduction

Book edition 3rd
Author(s) Thomas W Hungerford, David Leep
Pages 608 pages
ISBN 9781111569624

# In exercise 8-13, solve the system of congruences12. $\begin{array}{l}\mathbf{\text{x}}\mathbf{\equiv }\mathbf{\text{1(mod5)}}\\ \mathbf{\text{x}}\mathbf{\equiv }\mathbf{\text{3(mod6)}}\\ \mathbf{\text{x}}\mathbf{\equiv }\mathbf{\text{5(mod11)}}\\ \mathbf{\text{x}}\mathbf{\equiv }\mathbf{\text{10(mod13)}}\end{array}$

The system of congruence is obtained as $\mathrm{x}\equiv 621\left(\mathrm{mod}\text{\hspace{0.17em}}4290\right)$.

See the step by step solution

## Conceptual Introduction

Let ${{\mathbit{m}}}_{{\mathbf{1}}}{\mathbf{,}}{\mathbf{\text{\hspace{0.17em}}}}{{\mathbit{m}}}_{{\mathbf{2}}}{\mathbf{\text{\hspace{0.17em}}}}{\mathbf{.}}{\mathbf{...}}{{\mathbit{m}}}_{{\mathbf{f}}}$ be pair wise relatively prime positive integers, (it means that $\left({m}_{i},{m}_{j}\right){\mathbf{=}}{\mathbf{1}}$ whenever ${\mathbit{i}}{\mathbf{\ne }}{\mathbit{j}}$ ) . Assume that the ${{\mathbit{a}}}_{{\mathbf{1}}}{\mathbf{,}}{\mathbf{\text{\hspace{0.17em}}}}{{\mathbit{a}}}_{{\mathbf{2}}}{\mathbf{.}}{\mathbf{....}}{\mathbf{,}}{\mathbf{\text{\hspace{0.17em}}}}{{\mathbit{a}}}_{{\mathbf{r}}}$ , are any integers.

Then the system,

$\begin{array}{l}x\equiv {a}_{1}\left(mod{m}_{1}\right)\\ x\equiv {a}_{2}\left(mod{m}_{2}\right)\\ x\equiv {a}_{3}\left(mod{m}_{3}\right)\\ .\\ .\\ .\\ x\equiv {a}_{r}\left(mod{m}_{r}\right)\end{array}$

has a solution.

## Evaluating the system of congruences for x≡1(mod 5)  and x≡3(mod 6) .

Assume that the numbers m and n are relatively prime integers. Then the following system of congruence equations has a solution.

$\mathrm{x}\equiv \mathrm{a}\left(\mathrm{modm}\right)$ …… (1)

$\mathrm{x}\equiv \mathrm{b}\left(\mathrm{mod}\text{\hspace{0.17em}\hspace{0.17em}}\mathrm{n}\right)$ …… (2)

Now from the above two equation solution can be obtained as,

$\mathrm{t}=\mathrm{bmu}+\mathrm{anv}$ …… (3)

Here the numbers u and v are found such that the following equation is satisfied.

$\mathrm{mu}+\mathrm{nv}=1$ …… (4)

Now the given congruence equations are:

$\mathrm{x}\equiv 1\left(\mathrm{mod}\text{\hspace{0.17em}}5\right)$ …… (5)

And,

$\mathrm{x}\equiv 3\left(\mathrm{mod}\text{\hspace{0.17em}}6\right)$ ……. (6)

Compare the equations (5) and (6) with (1) and (2) to obtain the following values,

$m=5$ , $n=6$ , $a=1$ and data-custom-editor="chemistry" $b=3$

Now find out the values of and such that the equation (4) is satisfied.

$5u+6v=1$

Above equation will get satisfied with the values $u=1$ and $v=-1$

Now substitute 3 for b , 5 for m , -1 for u , 1 for a , 6 for n and 1 for v into the equation (3)

$\begin{array}{c}t=3×5×\left(-1\right)+1×6×1\\ =-9\end{array}$

So the required solution is given by,

$\begin{array}{c}x\equiv -9\left(\mathrm{mod}6×5\right)\\ \equiv -9\left(\mathrm{mod}\text{\hspace{0.17em}}30\right)\\ \equiv 21\left(\mathrm{mod}\text{\hspace{0.17em}}30\right)\end{array}$ ...... (7)

## Evaluating the system of congruence for  x≡5(mod 11)

Now the third system of congruence is given by,

$\mathrm{x}\equiv 5\left(\mathrm{mod}\text{\hspace{0.17em}}11\right)$ ...... (8)

Again compare the equations (7) and (8) with (1) and (2) to obtain the following values,

$m=30$ , $n=11$ , $a=21$ and $b=5$

Substitute 30 for m and 11 for n into the equation (4), and again find the values of u and v such that the equation (4) is satisfied.

$30u+11v=1$

From the heat and trial method, above equation holds true for and

Now substitute 3 for b , 30 for m , -3 for u , 12 for a , 7 for n and 13 for v into the equation (3)

$\begin{array}{c}t=bmu+anv\\ =5×30×\left(-4\right)+21×11×11\\ =1941\end{array}$ ........ (9)

Now from the equation (7), (8) and (9), the required solution can be calculated,

$\begin{array}{c}x\equiv 1941\left(\mathrm{mod}\text{\hspace{0.17em}}30×11\right)\\ \equiv 822\text{\hspace{0.17em}}\left(\mathrm{mod}\text{\hspace{0.17em}}330\right)\\ \equiv -39\left(\mathrm{mod}\text{\hspace{0.17em}}330\right)\end{array}$ ...... (10)

## Evaluating the system of congruence for  x≡10(mod 13)

Now the fourth congruence equation is given by,

$x\equiv 10\left(\mathrm{mod}\text{\hspace{0.17em}}13\right)$ ...... (11)

Now again compare the equation (10) and (11) with equation (1) and (2) to obtain the following values,

$m=330$, $n=13$ , $a=-39$ and $b=10$

Substitute 330 for m and 13 for n into the equation (4)

$330u+13v=1$

From the heat and trial method $u=8$ and $v=-203$ holds true for the above equation,

Now substitute 10 for b , 330 for m , 8 for u , -39 for a , 13 for n and -203 for v into the equation (3)

$\begin{array}{c}t=bmu+anv\\ =10×330×8+\left(-39\right)×13×\left(-203\right)\\ =129321\end{array}$ ....... (12)

Now from the equation (10), (11) and (12), the required solution of the congruence is,

$\begin{array}{c}x\equiv 129321\left(\mathrm{mod}\text{\hspace{0.17em}}330×13\right)\\ \equiv 129321\left(\mathrm{mod}\text{\hspace{0.17em}}4290\right)\\ \equiv 621\left(\mathrm{mod}\text{\hspace{0.17em}}4290\right)\end{array}$

Therefore the system of congruence is obtained as $x\equiv 621\left(\mathrm{mod}\text{\hspace{0.17em}}4290\right)$ .