# Solving the equation $324 x \bmod {121} = 1$

On a practice final exam (for a Computer Security course), I am given the following equation to solve, but I have no idea how to solve it: $$324x \bmod 121 = 1.$$

Any direction?

-

HINT $\$ One can easily solve it mod $11$ then lift the solution to one mod $11^2$

$\rm\ \ mod\ 11:\ \ \ \ x = 1/(324) = 1/(-6) = -2\ \$ so $\rm\ x = -2 + 11\ n$

$\rm\ \ mod\ 121:\ \ \: 1 = 324\ x = (-6 + 11\cdot 30)\ (-2 + 11\ n)\ \ =\ 55\ n - 43\ \ \Rightarrow\ \ 55\ n = 44$

Dividing by $11$ we deduce $\rm\ 5\ n = 4\ \:(mod\ 11)\$ so $\rm\ n =\ \ldots\ \:$ The method generalizes, e.g.

$\rm\quad\quad a\ x\ =\ 1 + b\ m\ \ \Rightarrow\ \ a\ x\ (2-a\ x)\ =\ (1 + b\ m)\ (1-b\ m) = 1 - (b\ m)^2\equiv 1\:\ (mod\ m^2)$

so $\rm\ a^{-1}\equiv x\:\ (mod\ m)\$ lifts to $\rm\ a^{-1}\equiv x\ (2-a\ x)\ \ (mod\ m^2)\:.\:$ This method of lifting solutions is a special case of a very powerful generalization of Newton's method known as Hensel's Lemma.

-

You need the Extended Euclidean Algorithm which solves the problem of finding modular inverses. Bezout's identity guarantees that there is a solution.

-