アルゴリズム論特論(塩田)第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$ の逆数を求めてみましょう。
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}}$ と表すこととする。
証明 法 $n$ の $\binv$ が存在するとき、$x=\binv\times a$ とおけば
$b \times x \equiv b \times \left(\binv \times a\right) \equiv \left(b \times \binv\right) \times a \equiv 1 \times a \equiv a$
が成り立つ。逆に $x$ が
$b \times x \equiv a$
を満たせば
\begin{align} x \equiv 1 \times x \equiv \left( \binv \times b \right) \times x &\equiv \binv \times \left( b \times x \right) \equiv \binv \times a \\ \end{align}
(証明終)