Question

In exercise 8-13, solve the system of congruences

11.

$$\begin{gathered} \mathit{x}\mathbf{\equiv }\mathbf{2}\mathbf{\left(}\mathbf{m}\mathbf{o}\mathbf{d}\mathbf{5}\mathbf{\right)} \\ \mathit{x}\mathbf{\equiv }\mathbf{0}\mathbf{\left(}\mathbf{m}\mathbf{o}\mathbf{d}\mathbf{6}\mathbf{\right)} \\ \mathit{x}\mathbf{\equiv }\mathbf{3}\mathbf{\left(}\mathbf{m}\mathbf{o}\mathbf{d}\mathbf{7}\mathbf{\right)} \end{gathered}$$

Short answer

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

Step-by-step solution

Conceptual Introduction

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

Then the system,

role="math" localid="1659451269093" $$\begin{gathered} x\equiv a_1\left({\mathrm{modm}}_1\right) \\ x\equiv a_2\left({\mathrm{modm}}_2\right) \\ x\equiv a_3\left({\mathrm{modm}}_3\right) \\ . \\ . \\ . \\ x\equiv a_r\left(mod{m}_r\right) \end{gathered}$$

has a solution.

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.

$$\begin{gathered} x\equiv a\left(modm\right)\dots \dots \left(1\right) \\ x\equiv b\left(modn\right)\dots \dots \left(2\right) \end{gathered}$$

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\times 5\times \left(-1\right)+2\times 6\times 1\\ & =& 12\end{array}$

So the required solution is given by,

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

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\times 30\times \left(-3\right)+12\times 7\times 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\times 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}$.