剰余演算の逆元を手計算で求める方法についての備忘録です。 例えば $16$ を法とする $3$ の逆元 $x$ を求める例を考えてみます。
\[3x \equiv 1 \pmod{16}\]まず、与式と $16$ を法とする式 $16x \equiv 0$ で一次合同式を立てます。
\[\begin{cases} 3x &\equiv 1 \pmod{16} \;\;\;\;\;\;\;\;\;\;(1) \\ 16x &\equiv 0 \pmod{16} \;\;\;\;\;\;\;\;\;\;(2) \end{cases}\]次に、式変形をして左辺の $x$ の係数の差が $1$ になるようにします。
\[\begin{cases} 15x &\equiv 5 \pmod{16} \;\;\;\;\;\;\;\;\;\;(1)' \\ 16x &\equiv 0 \pmod{16} \;\;\;\;\;\;\;\;\;\;(2) \end{cases}\] \[\begin{aligned} \;\;\;\; x &\equiv -5 \pmod{16} \;\;\;\;\;\;\;\;(2) - (1)' \\ x &\equiv 11 \pmod{16} \end{aligned}\]よって、$16$ を法とする $3$ の逆元 $x$ は $11$ となります。