Question 12 Marks
Solve: $12 x \equiv 44(\bmod 59)$
Answer
View full question & answer→We know that $a \equiv b (\bmod m ) \Rightarrow \frac{a}{x} \equiv \frac{b}{x}\left(\bmod \frac{m}{d}\right)$, where $d =( x , m )$.
$
\begin{array}{l}
\therefore 12 x \equiv 44(\bmod 59) \\
\Rightarrow 3 x \equiv 11(\bmod 59)[\because(4,59)=1]
\end{array}
$
We find that $(3,59)=1$, hence it has unique solution $(\bmod 59)$. Using division algorithm, we obtain
$
\begin{array}{l}
59=19 \times 3+2 \\
3=2 \times 1+1
\end{array}
$
Using back substitution, we obtain
$
\begin{array}{l}
1=3-2 \times 1 \\
\Rightarrow 1=3-(59-19 \times 3) \times 1 \\
\Rightarrow 1=59 \times(-1)+20 \times 3
\end{array}
$
The coefficient of 3 i.e. 20 is the inverse of $3(\bmod 59)$
Now,
$
\begin{array}{l}
3 x \equiv 11(\bmod 59) \\
\Rightarrow 20 \times 3 x \equiv 20 \times 11(\bmod 59) \text { [Multiplying throughout by inverse of } 3 \text { i.e. } 20 \text { ] } \\
\Rightarrow(20 \times 3) x \equiv 220(\bmod 59) \\
\Rightarrow x \equiv 43(\bmod 59)
\end{array}
$
Hence $x \equiv 43(\bmod 59)$ is the solution of the given linear congruence.
$
\begin{array}{l}
\therefore 12 x \equiv 44(\bmod 59) \\
\Rightarrow 3 x \equiv 11(\bmod 59)[\because(4,59)=1]
\end{array}
$
We find that $(3,59)=1$, hence it has unique solution $(\bmod 59)$. Using division algorithm, we obtain
$
\begin{array}{l}
59=19 \times 3+2 \\
3=2 \times 1+1
\end{array}
$
Using back substitution, we obtain
$
\begin{array}{l}
1=3-2 \times 1 \\
\Rightarrow 1=3-(59-19 \times 3) \times 1 \\
\Rightarrow 1=59 \times(-1)+20 \times 3
\end{array}
$
The coefficient of 3 i.e. 20 is the inverse of $3(\bmod 59)$
Now,
$
\begin{array}{l}
3 x \equiv 11(\bmod 59) \\
\Rightarrow 20 \times 3 x \equiv 20 \times 11(\bmod 59) \text { [Multiplying throughout by inverse of } 3 \text { i.e. } 20 \text { ] } \\
\Rightarrow(20 \times 3) x \equiv 220(\bmod 59) \\
\Rightarrow x \equiv 43(\bmod 59)
\end{array}
$
Hence $x \equiv 43(\bmod 59)$ is the solution of the given linear congruence.
