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

Question

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?

Answer 1

Inverses mod power moduli $n^k$ can be very efficiently calculated by Hensel lifting an inverse $\!\bmod n\,$ up to $\!\bmod n^k\,$ via Newton iteration (similar to familiar calulus methods), e.g. here

$\!\bmod \color{#c00}{11^{\large 2}}\!:\, {\large \frac{1}{324}}\!\overset{\times\ {\bf {-}}2_{\phantom{|}}\!\!}\equiv {\Large \frac{-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^{\phantom{|}}}{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.

Answer 2

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