Question

In exercise 8-13, solve the system of congruences

12.

$\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}$

Short answer

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

Step-by-step solution

Conceptual Introduction

Let ${\mathit{m}}_{\mathbf{1}}\mathbf{,}{\mathit{m}}_{\mathbf{2}}\mathbf{.}\mathbf{...}{\mathit{m}}_{\mathbf{f}}$ be pair wise relatively prime positive integers, (it means that $\left(m_i,m_j\right)\mathbf{=}\mathbf{1}$ whenever $\mathit{i}\mathbf{\ne }\mathit{j}$) . Assume that the ${\mathit{a}}_{\mathbf{1}}\mathbf{,}{\mathit{a}}_{\mathbf{2}}\mathbf{.}\mathbf{....}\mathbf{,}{\mathit{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}\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}5\right)$ …… (5)

And,

$\mathrm{x}\equiv 3\left(\mathrm{mod}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\times 5\times \left(-1\right)+1\times 6\times 1\\ =-9\end{array}$

So the required solution is given by,

$\begin{array}{c}x\equiv -9\left(\mathrm{mod}6\times 5\right)\\ \equiv -9\left(\mathrm{mod}30\right)\\ \equiv 21\left(\mathrm{mod}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}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\times 30\times \left(-4\right)+21\times 11\times 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}30\times 11\right)\\ \equiv 822\left(\mathrm{mod}330\right)\\ \equiv -39\left(\mathrm{mod}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}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\times 330\times 8+\left(-39\right)\times 13\times \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}330\times 13\right)\\ \equiv 129321\left(\mathrm{mod}4290\right)\\ \equiv 621\left(\mathrm{mod}4290\right)\end{array}$

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