晴耕雨読

working in the fields on fine days and reading books on rainy days

剰余の逆元 (modinv) の手計算

剰余演算の逆元を手計算で求める方法についての備忘録です。 例えば $16$ を法とする $3$ の逆元 $x$ を求める例を考えてみます。

まず、与式と $16$ を法とする式 $16x \equiv 0$ で一次合同式を立てます。

次に、式変形をして左辺の $x$ の係数が $1$ になるようにします。

よって、$16$ を法とする $3$ の逆元 $x$ は $11$ となります。