 Suggested languages for you:

Europe

Answers without the blur. Sign up and see all textbooks for free! Q11E

Expert-verified Found in: Page 448 ### 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 congruences11.${\mathbit{x}}{\mathbf{\equiv }}{\mathbf{2}}\mathbf{\left(}\mathbf{m}\mathbf{o}\mathbf{d}\mathbf{5}\mathbf{\right)}\phantom{\rule{0ex}{0ex}}{\mathbit{x}}{\mathbf{\equiv }}{\mathbf{0}}\mathbf{\left(}\mathbf{m}\mathbf{o}\mathbf{d}\mathbf{6}\mathbf{\right)}\phantom{\rule{0ex}{0ex}}{\mathbit{x}}{\mathbf{\equiv }}{\mathbf{3}}\mathbf{\left(}\mathbf{m}\mathbf{o}\mathbf{d}\mathbf{7}\mathbf{\right)}$

The system of congruence is obtained as $x\equiv -18\left(mod210\right)$.

See the step by step solution

## Step 1: Conceptual Introduction

Let ${{\mathbit{m}}}_{{\mathbf{1}}}{\mathbf{,}}{{\mathbit{m}}}_{{\mathbf{2}}}{\mathbf{.}}{\mathbf{.}}{\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}}{\mathbf{}}{\mathbit{w}}{\mathbit{h}}{\mathbit{e}}{\mathbit{n}}{\mathbit{e}}{\mathbit{v}}{\mathbit{e}}{\mathbit{r}}{\mathbf{}}{\mathbit{i}}{\mathbf{\ne }}{\mathbit{j}}$) . Assume that the ${{\mathbit{a}}}_{{\mathbf{1}}}{\mathbf{,}}{{\mathbit{a}}}_{{\mathbf{2}}}{\mathbf{.}}{\mathbf{.}}{\mathbf{.}}{\mathbf{.}}{\mathbf{,}}{{\mathbit{a}}}_{{\mathbf{r}}}$, are any integers.

Then the system,

role="math" localid="1659451269093" ${x}{\equiv }{{a}}_{{1}}\left({\mathrm{modm}}_{1}\right)\phantom{\rule{0ex}{0ex}}{x}{\equiv }{{a}}_{{2}}\left({\mathrm{modm}}_{2}\right)\phantom{\rule{0ex}{0ex}}{x}{\equiv }{{a}}_{{3}}\left({\mathrm{modm}}_{3}\right)\phantom{\rule{0ex}{0ex}}{.}\phantom{\rule{0ex}{0ex}}{.}\phantom{\rule{0ex}{0ex}}{.}\phantom{\rule{0ex}{0ex}}{x}{\equiv }{{a}}_{{r}}\left(mod{m}_{r}\right)$

has a solution.

## Step 2: Evaluating the system of congruence for x≡2(mod5) and x≡(mod6)

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

$x\equiv a\left(modm\right)\dots \dots \left(1\right)\phantom{\rule{0ex}{0ex}}x\equiv b\left(modn\right)\dots \dots \left(2\right)$

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

$t=bmu+anv$ …… (3)

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

mu + nv = 1 …… (4)

Now the given congruence equations are:

$x\equiv 2\left(mod5\right)$ …… (5)

And,

$x\equiv 0\left(mod6\right)$ ……. (6)

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

m = 5 , n = 6 , a = 2 and b = 0

Now find out the values of u and v 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 0 for b , 5 for m, -1 for u, 2 for a, 6 for n and 1 for v into the equation (3)

$\begin{array}{rcl}t& =& 0×5×\left(-1\right)+2×6×1\\ & =& 12\end{array}$

So the required solution is given by,

$\begin{array}{rcl}x& \equiv & 12\left(mod6×5\right)\\ & \equiv & 12\left(mod30\right)\end{array}$ ...... (7)

## Step 3: Evaluating the system of congruence for x≡2(mod7)

Now the third system of congruence is given by,

$x\equiv 3\left(mod7\right)$ ...... (8)

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

$m=30,n=7,a=12andb=3$

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

$30u+7v=1$

From the heat and trial method, above equation holds true for u = -3 and v = 13

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}{rcl}t& =& bmu+an\\ & =& 3×30×\left(-3\right)+12×7×13\\ & =& 822\end{array}$ ........ (9)

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

role="math" localid="1659452713423" $\begin{array}{rcl}x& \equiv & 822\left(mod30×7\right)\\ & \equiv & 822\left(mod210\right)\\ & \equiv & -18\left(mod210\right)\end{array}$

Therefore the final solution is $x\begin{array}{rcl}& \equiv & \end{array}\begin{array}{rcl}& & -\end{array}\begin{array}{rcl}& & 18\end{array}\begin{array}{rcl}& & \left(mod210\right)\end{array}$. ### Want to see more solutions like these? 