Question

(a) How can an inverse of modulo be used to solve the congruence $\mathit{a}\mathit{x}\mathbf{\equiv }\mathbf{b}\mathbf{(}\mathit{m}\mathit{o}\mathit{d}\mathbf{}\mathbf{}\mathbf{m}\mathbf{)}$when$\mathbf{gcd}\mathbf{(}\mathbf{a}\mathbf{,}\mathbf{m}\mathbf{)}\mathbf{=}\mathbf{1}$ ?

(b) Solve the linear congruence $\mathbf{7}\mathbf{x}\mathbf{\equiv }\mathbf{13}\mathbf{(}\mathbf{mod}\mathbf{}\mathbf{19}\mathbf{)}$.

Short answer

(a) Multiply by inverse of , we get $x\equiv \overline{a}b(modm)$

(b) The solution of given linear congruent is .$x\equiv 10(mod19)$

Step-by-step solution

Linear congruence

A linear congruence of the form$\mathbf{ax}\mathbf{\equiv }\mathbf{b}\mathbf{(}\mathbf{mod}\mathbf{}\mathbf{}\mathbf{m}\mathbf{)}$where,$\mathbf{a}\boxed{\mathbf{\equiv }}\mathbf{}\mathbf{0}\mathbf{(}\mathbf{mod}\mathbf{}\mathbf{}\mathbf{m}\mathbf{)}$ and$\mathbf{a}\mathbf{,}\mathbf{b}\mathbf{,}\mathbf{m}\mathbf{>}\mathbf{0}$ are fixed integer is called a linear congruence.

Finding that how can an inverse of  a modulo m be used to solve the congruence ax≡b(mod  m)

(a)

Let$\overline{a}$ be the inverse of modulo m.

So,$\mathrm{a}\cdot ¯\mathrm{a}\equiv 1(\mathrm{mod}\mathrm{m})$ where$\gcd (\mathrm{a},\mathrm{m})=1$

Now for$\mathrm{ax}\equiv \mathrm{b}(\mathrm{mod}\mathrm{m})$

Multiplying$\overline{a}$ both the side we get,

$$\begin{gathered} \overline{a}ax\equiv \overline{a}b(modm) \\ x\equiv \overline{a}b(modm) \end{gathered}$$

Solving the linear congruence 7x≡13(mod  19)

(b)

Here we have given that$7x\equiv 13(mod19)$.

Here,$gcd(7,19)=1$

Now, we know that $7\cdot 11=77\equiv 1(mod19)$.

So, 11 is inverse of 7

Now, by step 1, multiply 11 on both side,

$$\begin{gathered} 11\cdot 7x\equiv 11\cdot 13(mod19) \\ x\equiv 143(mod19) \\ x\equiv 10(mod19) \end{gathered}$$

Hence, the solution of given linear congruent is $x\equiv 10(mod19)$.