Question

If $\mathbf{\text{(a,n)=d}}$and$\mathbf{\text{d/b}}$ ,show that $\mathbf{\text{ax}}\mathbf{\equiv }\mathbf{\text{b(modn)}}$has a solution [Hint: for $\mathbf{\text{b=dc}}$some c, and $\mathbf{\text{au+nv=d}}$ for somelocalid="1659435259694" $\mathbf{\text{u,v}}$ (why?) multiply the last equation by ;what is$\mathbf{\text{auc}}$ congruent to modulo n?

Short answer

The congruent equation $auc$ is $ax$, where $x$ is an solution to the equation.

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.

The congruent equation can be written as an algebraic equation.

The congruent equation, $ax\equiv b\left(modn\right)$, rewritten as an algebraic equation, with congruent replaced by an equal to sign.

$\begin{array}{l}ax\equiv b\left(modn\right)\\ au+nv=d\end{array}$

The greatest common divisor is d.

If the value is:

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

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

The value of d is the divisor dividing both a and n .

$au+nv=d$

Where, u , v represents an integer, any equation can have solution as an integer only.

Multiply the equation by c.

It is solved as:

$\begin{array}{l}\left(au+nv=d\right)\times c\\ auc+nvc=dc\end{array}$

Substitute b as dc .

$auc+nvc=b$

This algebraic equation is written as congruence equation as:

$\begin{array}{c}a\left(uc\right)=b\left(modn\right)\\ ax=b\left(modn\right)\end{array}$

Here x represents the solution of the equation, and the solution of the equation is uc .

Hence, the congruent equation auc is nothing but ax and where x is an solution to the equation