アルゴリズム論特論（塩田）第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}
といった計算もできます。