2
$\begingroup$

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?

2 Answers 2

7

$\!\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},\,$ lifting inverse from $\!\bmod n\,$ to $\bmod{n^2}\,$

which 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. 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.

3

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