「割った余り」での割り算は、既約分数にしなくても答えは変わらない

この記事では, $P$ を素数とし, $\textrm{mod } P$ の下での割り算について述べます.

整数 $a,b$ に対する $\textrm{mod } P$ の下での割り算 $a\times b^{-1}$ では,
分数 $a/b$ が既約分数になっていなくても計算結果は変わりません.

そのことを述べていきます.

復習

wakabame.hatenablog.com
でも触れましたが, まずは逆元とは何かを述べます.
$P$ の倍数ではない $a=0,1, \cdots$ に対して, $a$ の法 $P$ の下での逆元 $a^{-1}$ を求めましょう.
まず,

$x =0,1, \cdots , P-1$ が $a$ の法 $P$ の下での逆元であるとは,
ある $y_a \in \mathbb{N}$ が存在して,
\begin{equation}
ax+Py_a =1
\end{equation}
を満たすこと

と定式化できたのでした.
そのような $x$ は $a$ が $P$ の倍数でない限り一意に存在し, 以後これを $a^{-1}$ と表します.

このような $a^{-1}$ がなぜとれるかについては,
拡張ユークリッドの互除法について述べられている @drken さんの記事
qiita.com
を参考にしてみてください.

示すべきこと

$a\times b^{-1} \textrm{mod } P$ は既約でなくても計算結果が変わらないことを示すために,

$P$ 未満の自然数 $k$ に対して, $ka\times (kb)^{-1}$ を計算して, その差を観察しましょう.

まずは, 拡張ユークリッドの互除法から $b^{-1}$ , $(kb)^{-1}$ はある整数 $y_b, y_{kb}$ を用いて,
\begin{equation}
b^{-1} = \dfrac{1-Py_b}{b},\quad (kb)^{-1} = \dfrac{1-Py_{kb}}{kb}
\end{equation}
と表せたことに注意します.

これにより,
\begin{align*}
ab^{-1} - ka(kb)^{-1}
&= a\dfrac{1-Py_b}{b} -ka \dfrac{1-Py_{kb}}{kb}\\
&= \dfrac{a(y_{kb}-y_{b})}{b}P
\end{align*}

を得ます.

ここで, 左辺は整数だから右辺も整数であり, $b$ は $P$ の倍数ではないので
$\dfrac{a(y_{kb}-y_{b})}{b}$
は整数です.

したがって両辺は $P$ の倍数であることから,
\begin{equation}
ab^{-1} \textrm{mod } P = ka(kb)^{-1} \textrm{mod } P
\end{equation}

が従います.

別の説明

積 $kb$ についての逆元は,
\begin{equation}
(kb)^{-1} \equiv b^{-1}k^{-1} \pmod P
\end{equation}
を満たします.

これにより,
\begin{equation}
ka(kb)^{-1} \equiv kab^{-1}k^{-1} \equiv ab kk^{-1} \equiv ab\pmod P
\end{equation}
を示すこともできます（指摘されるまで気が付きませんでいた。。）.