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?

Solution 1:

$\!\bmod \color{#c00}{11^{\large 2}}\!:\, \dfrac{1}{324}\!\overset{\times\ {\bf {-}}2_{\phantom{|}}\!\!}\equiv \dfrac{-2}{\color{#0a0}{1\!-\!59\cdot 11}}\equiv\,-2(\overbrace{1\!+\!\color{#90f}{59}\cdot 11}^{\textstyle 1\,+\,\color{#90f}4\cdot 11})\equiv\overbrace{ -90}^{\textstyle 31}.\, $ Generally if $\,\overbrace{1/a\equiv a'\pmod{\!n}}^{\textstyle \color{#0a0}{aa' = 1+j\,n}}\,$

$\!\bmod \color{#c00}{n^2}\!:\ \dfrac{1}{a}\!\equiv\!\dfrac{a'}{\color{#0a0}{aa'}}\!\equiv\! \dfrac{a'}{\color{#0a0}{1+jn}}\!\equiv a'(1-jn),\ $ by $\ \color{#c00}{n^2\equiv 0},\,$ lifts an inverse $\!\bmod n\,$ to $\!\bmod{n^2}$
where above we used: $\ \dfrac{1}{1+jn}\,\equiv 1-jn,\,$ by $\, (1+jn)(1-jn) = 1-j^2\color{#c00}{n^2}\equiv 1$.

This can be viewed as using Hensel lifting (Newton's method) to compute inverses. In general, as above, it is trivial to invert a unit + nilpotent by using a (terminating) geometric series, which is a special case of the general method of simpler multiples.

Of course we can also use general inversion methods $\!\bmod n^2,\,$ but usually they will be less efficient than the the quadratic convergence of Newton's method. There are a few worked examples using a handful of such methods (including all those in the other answers) presented here and here and here. This includes most all the common known methods (and their optimizations).

Note $ $ Above we used $\,59\cdot 11 \bmod 11^2 = (\color{#90f}{59\bmod 11})\,11 = \color{#90f}4\cdot 11\ $ by the $\!\bmod\!$ Distributive Law. Notice the great simplification obtained by lifting the inverse up from $\!\bmod n,\,$ which made all the arithmetic so trivial it could be done in a minute of purely mental arithmetic.

Solution 2:

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