Question

Solve the congruence $4x=5\left(\mathrm{mod}9\right)$using the inverse of 4 modulo9 found in part (a) of Exercise 5.

Short answer

The congruence is solved

$x=8\left(\mathrm{mod}9\right)$

Step-by-step solution

Step 1

We have to solve this

$4x=5\left(\mathrm{mod}9\right)$

We use Bezout’s Theorem to express $\gcd \left(9,4\right)$, as a lineal combination of 9 and 4. Thus we can observe that the inverse of 4 is $-2$, but if we add 9 to $-2$, we obtain7, so the inverse is, as well, 7

$9=(2\ast 4)+1$

So

$1=(9\ast 1)-(2\ast 4)=(9\ast 1)+\left(\right(-2)\ast 4)$

Step 2

So we can multiply both sides by 7to obtain that is equivalent with $8\left(\mathrm{mod}9\right)$

$$\begin{gathered} 7\ast 4x=7\ast 5(mod9) \\ x=35(mod9) \end{gathered}$$

$x=8(mod9)$