アルゴリズム論特論（塩田）第6回 (5) 逆数の手計算
前へ / 戻る / 次へ
$\newcommand{\inv}[1]{\displaystyle{\frac{1}{#1}}}$
$\newcommand{\binv}{\displaystyle{\frac{1}{b}}}$
法 $n$ での逆数の手計算
多少は手計算でも逆数が求められるようになりましょう。
Prop.9 任意の法 $n$ で
$\inv{1} \equiv 1\qquad$ $\inv{n-1} \equiv n-1$
証明 $(n-1)^2 \equiv (-1)^2 \equiv 1 $. (証明終)
Prop.10 法 $n$ が奇数であれば
$\inv{2} \equiv \displaystyle{\frac{n+1}{2}}$
Prop.11
- $n=3k+1$ のとき
$\inv{3} \equiv \displaystyle{\frac{2n+1}{3}}$
- $n=3k+2$ のとき
$\inv{3} \equiv \displaystyle{\frac{n+1}{3}}$
Prop.10-11 の証明 $n \equiv 0$ ゆえ。 (証明終)
※ Prop.10-11 は
右辺が整数である ところが肝心です。
Ex.12 法 $101$ で
$\inv{2} \equiv \displaystyle{\frac{101+1}{2}} = 51$,
$\qquad\inv{3} \equiv \displaystyle{\frac{101+1}{3}} = 34$
これらを組み合わせると、
$\inv{4} \equiv \left(\inv{2}\right)^2
\equiv 51^2 = 50^2 + 100 + 1 = 2500 + 101 \equiv -25$,
$\inv{12} \equiv \inv{4} \times \inv{3}
\equiv -25 \times 34 \equiv 59$
といった計算もできます。
$\inv{12} \equiv \inv{4} \times \inv{3}
\equiv -25 \times \inv{3} \equiv (202 - 25) \times \inv{3} \equiv \displaystyle{\frac{177}{3}} = 59$
とすれば電卓がなくてもできます。
Rem.13 $b$ が小さいときは
$\inv{b} \equiv \displaystyle{\frac{n+1}{b}}
\equiv \displaystyle{\frac{2n+1}{b}}
\equiv \cdots$
のように分子に $n$ を足して、いって割り切れたところが答えになります。
（ $b$ が小さいので、じきにみつかります。）
Ex.14 法 $37$ で
$\inv{7} \equiv \displaystyle{\frac{38}{7}}
\equiv \displaystyle{\frac{75}{7}}
\equiv \displaystyle{\frac{112}{7}} = 16$