Question

Question: If (m,n) =d ,prove that$\mathbf{\text{x}}\mathbf{\equiv }\mathbf{\text{a(mod m)}}$ and $\mathbf{\text{x}}\mathbf{\equiv }\mathit{b}\mathbf{\text{(mod m)}}$has a solution if and only if$\mathbf{\text{a}}\mathbf{\equiv }\mathbf{\text{b(mod d)}}$ .

Short answer

Answer:-

In the below solution, It is proven that: $x\equiv a\left(\text{mod} m\right)$ and $x\equiv b\left(\text{mod} m\right)$ has a solution.

Step-by-step solution

Conceptual Introduction 

Let $m_1, m_2 ....m_f$ be pair wise relatively prime positive integers, (it means that $\left(m_i,m_j\right)=1$, whenever $I\ne J$) . Assume that the $a_1, a_2....., a_r$, are any integers.

Then the system,

$$\begin{gathered} 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{gathered}$$

has a solution.

The greatest common divisor is d.

If the value is:

(m,n) = d

Then, $d=gcd\left(m,n\right)$

Let d be the divisor dividing both and , and be the integer in the equation,

$mr+ns=d$

Take d from the right-hand side to the left-hand side.

$r\left(\frac{m}{d}\right)+s\left(\frac{n}{d}\right)=1$

Rewrite the equation as an Chinese algorithm equation.

Convert the algebraic equation to an equation similar to Chinese algorithm equation.

Let the value be:

$$\begin{gathered} r=br, \\ s=as \end{gathered}$$

Where r,s are the elements of Z .

$x=br\left(\frac{m}{d}\right)+as\left(\frac{n}{d}\right)$

Differentiate the equation  

On differentiating,

$$\begin{gathered} dx=brm+asn \\ dx\left(mod m\right)=asn \end{gathered}$$

So,

$$\begin{gathered} dx=da\left(mod m\right) \\ dx=db\left(mod n\right) \end{gathered}$$

The equation is rewritten by introducing congruence, on further solving, the equation becomes.

$$\begin{gathered} x\equiv a\left(mod m\right) \\ x\equiv b\left(mod n\right) \end{gathered}$$

Hence, the congruent equations $x\equiv a\left(mod m\right)andx\equiv b\left(mod n\right)$are obtained.