アルゴリズム論特論（塩田）第6回 (5) 逆数の手計算
前へ / 戻る / 次へ
\newcommand{\inv}[1]{\displaystyle{\frac{1}{#1}}}
\newcommand{\binv}{\displaystyle{\frac{1}{b}}}
法 n での逆数の手計算
多少は手計算でも逆数が求められるようになりましょう。
Prop.9 任意の法 n で
\inv{1} \equiv 1,\quad \inv{n-1} \equiv n-1 \pmod{n}
証明 (n-1)^2 \equiv (-1)^2 \equiv 1 .
Prop.10 法 n が奇数であれば
\inv{2} \equiv \displaystyle{\frac{n+1}{2}} \pmod{n}
証明 n が奇数ゆえ右辺は整数で、
2 \times \displaystyle{\frac{n+1}{2}} \equiv n+1 \equiv 1.
Prop.11
- n=3k+1 のとき
\inv{3} \equiv \displaystyle{\frac{2n+1}{3}} \pmod{n}
- n=3k+2 のとき
\inv{3} \equiv \displaystyle{\frac{n+1}{3}} \pmod{n}
証明 いずれも右辺は整数で、
(1) なら
3 \times \displaystyle{\frac{2n+1}{3}} \equiv 2n+1 \equiv 1.
(2) も同様。
※ 右辺が整数である ところが肝心です。
同様に、
b が小さいときは
\inv{b} \equiv \displaystyle{\frac{n+1}{b}}
\equiv \displaystyle{\frac{2n+1}{b}}
\equiv \cdots
のように分子に
n を足していって ( 引いてもいいです ) 割り切れたところが答えになります。
（
b が小さいので、じきにみつかります。）
たとえば、法
37 では
\inv{7} \equiv \displaystyle{\frac{38}{7}}
\equiv \displaystyle{\frac{75}{7}}
\equiv \displaystyle{\frac{112}{7}} = 16 \pmod{37}
となります。
合わせ技の例も挙げておきましょう。法
101 で
\displaystyle{\frac{1}{12}} を求めたいときは
\inv{4} \equiv \displaystyle{\frac{-101+1}{2}} = -25
から
\begin{align}
\inv{12} &\equiv \inv{4} \times \inv{3}
\equiv \displaystyle{\frac{-25}{3}}
\equiv -8 -\displaystyle{\frac{1}{3}} \\
&\equiv -8 -\displaystyle{\frac{101+1}{3}}
\equiv -8 -34
\equiv -42
\equiv 59 \pmod{101} \\
\end{align}
といった計算もできます。