Question

Find all solutions, if any, to the system of congruences $\mathbf{x}\mathbf{\equiv }\mathbf{5}\mathbf{(}\mathbf{mod}\mathbf{6}{\mathbf{)}}_{\mathbf{2}}\mathbf{x}\mathbf{\equiv }\mathbf{3}\mathbf{(}\mathbf{mod}\mathbf{10}\mathbf{)}$, and$\mathbf{x}\mathbf{\equiv }\mathbf{8}\mathbf{(}\mathbf{mod}\mathbf{15}\mathbf{)}$

Short answer

The solution is $\mathrm{x}\equiv 23(mod30)$.

Step-by-step solution

Theorem 4(section 4.1)

According to theorem 4, letbe a positive integer. The integers are congruent modulo c if and only if there is an integer p such that $\mathit{a}\mathbf{=}\mathit{b}\mathbf{+}\mathit{p}\mathit{c}$.

Finding appropriate system of congruence relation

Here we have given that,

$\mathrm{x}\equiv 5(mod6),\mathrm{x}\equiv 3(mod10),\mathrm{and}\mathrm{x}\equiv 8(mod15)$

In above system we can see that, 6,10,15 are not relatively prime.

So, we have to make arrangements.

We know that $6=2\cdot 3$.

So, the congruence$\mathrm{x}\equiv 5(mod6)$ is equivalent to$\mathrm{x}\equiv 1(mod2)$ and $\mathrm{x}\equiv 2(mod3)$.

We know that $10=5·2$.

So, the congruence$x\equiv 3(mod10)$ is equivalent to $x\equiv 1(mod2)$and $x\equiv 3(mod5)$.

Also,$15=5·3$

So, the congruence$x\equiv 8(mod15)$ is equivalent to$x\equiv 3(mod5)$ and $x\equiv 2(mod3)$.From above 6 congruence relation, we get 3 disjoint relation as,

$\mathrm{x}\equiv 1(mod2),\mathrm{x}\equiv 3(mod3),\mathrm{and}\mathrm{x}\equiv 3(mod5)$

Finding the solution of the given system using back substitution

Here we have given that,

$\mathrm{x}\equiv 1(mod2),\mathrm{x}\equiv 3(mod3),\mathrm{and}\mathrm{x}\equiv 3(mod5)$

Now, for $x\equiv 1(mod2)$, from theorem 4 we can say that there is integer k such that $x=1+2k$

Also we have, $x\equiv 2(mod3)$,

Now, substitute the value of $x=1+2k$in $x\equiv 2(mod3)$. We get,

$$\begin{gathered} 1+2k\equiv 2(mod3) \\ 2k\equiv 1(mod3) \\ k\equiv (2{)}^{-1}\cdot 1(mod3) \end{gathered}$$

Now, we know that $k\equiv 2\cdot \left(2\right)=4=1(mod3)$

So,

$$\begin{gathered} k\equiv \left(2{)}^{-1}1\right(mod3) \\ k\equiv 2\cdot 1(mod3) \\ k\equiv 2(mod3) \end{gathered}$$

Now, again from theorem 4 we can say that there is integer l such that $k=2+3l$

Also, we have $x=1+2k$.

Now, substitute the value of $k=2+3l\mathrm{in}x=1+2k$. We get,

$$\begin{gathered} x=1+2(2+3l) \\ x=5+6l \end{gathered}$$

For some integer l.

Now, also we have, $x\equiv 3(mod5)$

Now, substitute the value of $x=3+6l\mathrm{in}x\equiv 3(mod5)$. We get,

$$\begin{gathered} 5+6l\equiv 3(mod5) \\ 6l\equiv -2(mod5) \\ 6l\equiv 3(mod15) \\ l\equiv \left(6{)}^{-1}3\right(mod5) \end{gathered}$$

Now, we know that$l\equiv 6\cdot 1=6=1(mod5)$

So,

$$\begin{gathered} l\equiv \left(6{)}^{-1}3\right(mod5) \\ l\equiv 3(mod5) \end{gathered}$$

Now, again from theorem 4 we can say that there is integer m such that$l=3+5m$

Also, we have $x=5+6l$.

Now, substitute the value of $l=3+5m$in $x=5+6l$. We get,

$$\begin{gathered} x=5+6(3+5m) \\ x=23+30m \end{gathered}$$

For some integer m.

Now, again by theorem 4 we can write $x\equiv 23(mod30)$.

Hence, the solution is $x\equiv 23(mod30)$.