アルゴリズム論特論（塩田）第6回 (2) ちゃんとした定義
法演算における逆数
$\newcommand{\inv}[1]{\displaystyle{\frac{1}{#1}}}$
$\newcommand{\binv}{\displaystyle{\frac{1}{b}}}$
普通の数では
$a \div b = a \times \binv$
なので、法演算でもまず「逆数」を考えましょう。
Def.1（ 法演算の逆数 ） 法 $n$ と $b$, $x$ が
$b \times x \equiv 1 \pmod n$
を満たすとき、$x$ を「法 $n$ での $b$ の逆数」と呼び、
$x \equiv b^{-1} \pmod n\quad$ あるいは $\quad x \equiv \binv \pmod n$
と書き表す。
Ex.2 $\bmod 7$ では
$\inv{1} \equiv 1$,
$\quad\inv{2} \equiv 4$,
$\quad\inv{3} \equiv 5$,
$\quad\inv{4} \equiv 2$,
$\quad\inv{5} \equiv 3$,
$\quad\inv{6} \equiv 6$
実際、
$1 \times 1 = 1$,
$\quad 2 \times 4 = 8 \equiv 1$,
$\quad 3 \times 5 = 15 \equiv 1$,
$\quad 6 \times 6 = 36 \equiv 1$
Exercise 3 $\bmod 11$ で $1$ ～ $10$ の逆数を求めてみましょう。
答え
$\inv{1} \equiv 1$,
$\quad\inv{2} \equiv 6$,
$\quad\inv{3} \equiv 4$,
$\quad\inv{4} \equiv 3$,
$\quad\inv{5} \equiv 9$,
$\inv{6} \equiv 2$,
$\quad\inv{7} \equiv 8$,
$\quad\inv{8} \equiv 7$,
$\quad\inv{9} \equiv 5$,
$\quad\inv{10} \equiv 10$
Th.4 法 $n$ の $\binv$ は、
存在すれば ( 法 $n$ で ) 唯一つしか無い。
証明 $x$, $y$ が共に $b$ の逆数とすると、
$b \times x \equiv 1$ かつ
$b \times y \equiv 1$
ゆえ
$x \equiv x \times 1 \equiv x \times ( b \times y ) \equiv ( x \times b ) \times y
\equiv 1 \times y \equiv y$
(証明終)
法演算の除算
Th.5（ 法演算の除算 ） 法 $n$ の $\binv$ が存在すれば、
$b \times x \equiv a \pmod n$
を満たす $x$ が存在し、かつ ( 法 $n$ で ) 唯一つしか無い。
これを $x=\displaystyle{\frac{a}{b}}$ と表すこととする。
証明 $x$, $y$ が
$b \times x \equiv a$ かつ
$b \times y \equiv a$
を満たすとすると
\begin{align}
x \equiv 1 \times x \equiv \left( \binv \times b \right) \times x
&\equiv \binv \times ( b \times x ) \equiv \binv \times a \\
&\equiv \binv \times ( b \times y ) \equiv \left( \binv \times b \right) \times y \equiv y \\
\end{align}
(証明終)