前へ / 戻る / 次へ $\newcommand{\inv}[1]{\displaystyle{\frac{1}{#1}}}$ $\newcommand{\binv}{\displaystyle{\frac{1}{b}}}$

法 $n$ での逆数の手計算

　多少は手計算でも逆数が求められるようになりましょう。 証明　$(n-1)^2 \equiv (-1)^2 \equiv 1$.
証明　$n$ が奇数ゆえ右辺は整数で、 $2 \times \displaystyle{\frac{n+1}{2}} \equiv n+1 \equiv 1.$
証明　いずれも右辺は整数で、 (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}$$ といった計算もできます。

前へ / 戻る / 次へ