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

Hint:
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$.