Question

Question:- If (a,n) = dand,s,tare solution of $\mathbf{\text{ax}}\mathbf{\equiv }\mathbf{\text{b(modn)}}$ prove that $\mathit{s}\mathbf{\equiv }\mathit{t}\mathbf{(}\mathit{m}\mathit{o}\mathit{d}\mathbf{ }\mathbf{ }\frac{\mathbf{n}}{\mathbf{d}}\mathbf{)}$ .

Short answer

Answer:-

In the below solution, It has been proved that:$s\equiv t(mod \frac{n}{d})$ .

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_i,a_2·\dots ,a$ , 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.

By using the theorem 1.4, and as (a,n) = d the algebraic equation of the congruent is:

The congruent equation is:

$ax\equiv b(mod n)$

, rewritten as an algebraic equation, with congruent replaced by an equal to sign.

$$\begin{gathered} ax\equiv b(mod n) \\ ax-ny=b \end{gathered}$$

Replace the values in the equation

If the value is:

(a,n) = d

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

Replace s as b and as t , in this equation $ax-ny=b$.

$$\begin{gathered} ax-ny=b \\ sx-ny=t \end{gathered}$$

The algebraic equation is represented as an congruence equation as

...... (1)

$sx\equiv t(mod n)$

The greatest common divisor is d.  

If the value is:

( a ,n)= d

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

Let d be the divisor dividing both a and n , replace n by $\frac{n}{d}$ into the equation (1)

$s\equiv t\left(mod\frac{n}{d}\right)$

Hence, proved