Question

The solution of the linear congruence $4x = 5\left( {\bmod 9} \right)$ is:
A) $6\left( {\bmod 9} \right)$
B) $8\left( {\bmod 9} \right)$
C) $9\left( {\bmod 9} \right)$
D) $10\left( {\bmod 9} \right)$

Answer 1

First of all, find the $\gcd \left( {4,9} \right)$. If the $\gcd \left( {4,9} \right)$ is 1, then the inverse exists. Write the $\gcd \left( {4,9} \right)$=1 as the multiple of 4 and 9. Then, the coefficient of 4 will be its inverse. Next, make the inverse positive by finding its equivalent expression. The, we will solve for the value of $x$.

Complete step by step solution:
We will first find the $\gcd \left( {4,9} \right)$
By Euclid’s division lemma, we have,
$9 = 2\left( 4 \right) + 1 \\\ 4 = 4\left( 1 \right) + 0 \\\$
Hence, $\gcd \left( {4,9} \right) = 1$
Therefore, the inverse of 4 modulo 9 exists.
Now, we write the $\gcd \left( {4,9} \right) = 1$ as a multiple of 4 and 9.
$9 = 2\left( 4 \right) + 1 \\\ 1 = - 2\left( 4 \right) + 9 \\\$
Hence, the inverse is $- 2$
Also, $- 2\bmod 9 = 7\bmod 9$, this implies 7 is also an inverse.
Multiply each side by 7, we get,
$7\left( {4x} \right) = 7\left( 5 \right)\bmod 9 \\\ 28x = 35\bmod 9 \\\$
Now, on dividing 28 by 9, we will get remainder as 1, therefore, we will get
$x = 35\bmod 9$
Next, on dividing 35 by 9, we will get remainder as 8, therefore, we will get
$x = 8\bmod 9$

Hence, option B is correct.

Note:
If a number is written in the form of $a = b\bmod c$ and $\gcd \left( {a,c} \right) = 1$ , then the inverse of the expression exists. Also, if we have $a = b\bmod c$, then $a$ is the value of remainder that we get after we divide $b$ by $c$.