アルゴリズム論特論(塩田) 2020年度教材 第6回

  • 出席代わりに、塩田 ( shiota@is.kochi-u.ac.jp ) 宛てにメールを出してください。
  • 件名は「アルゴリズム論特論第6回出席」とでもしてください。

今日のテーマ

  • 法演算における除算
 前回、法演算の加法・減法・乗法・べき乗を定義しました。 今日はさらに除算を定義します。

1. 割り算と除算の違い

 何を今更、と思うかもしれませんが
 $11 \div 3$ って何だ??
解釈1 3つに均等に割る
  • 長さ 11cm の羊羹なら 11/3 cm に切り分ければ良し
  • でも、11個の飴だと、そうはいかないよね
解釈2 3人に分ける
  • 11個の飴を、
  • 3人にまず1個ずつ配る → まだ8個ある
  • もう1個ずつ配る → まだ5個ある
  • もう1個ずつ配る → まだ2個ある
  • 2個余ったけど仕方ない
 解釈1は均等に「割る」ので「割り算」、 解釈2は3個ずつ「除いてゆく」ので「除算」という感じがしませんか?

2. 法演算で行うべきは割り算か除算か?

 $\bmod 7$ で $11 \div 3$ って何だ??
解釈1かな?
  • $11 \equiv 4 \equiv -10 \pmod 7$ なので、法演算では「大きさ」の概念がありません。 大きさの無いものを均等に割れ、と言われても困りますね。
解釈2かな? 
  • 11個の飴を、
  • 3人にまず1個ずつ配る → まだ8個ある
  • もう1個ずつ配る → まだ5個ある
  • もう1個ずつ配る → まだ2個ある
  • $2 \equiv 9 \pmod 7$ なのでもう1個ずつ配れる → まだ6個ある
  • もう1個ずつ配る → まだ3個ある
  • もう1個ずつ配る → 丁度無くなった
結局 6個ずつ配ったので
$11 \div 3 \equiv 6 \pmod 7$
なのかな?
 最後の式を見れば、確かに
$6 \times 3 = 18 \equiv 11 \pmod 7$
なので、正しいような気もします。ということは
$x \times b \equiv a \pmod n$
が成り立つときに
$a \div b \equiv x \pmod n$
ということにすればいいのでしょうか?

3. ちゃんとした定義

$\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$ の逆数を求めてみましょう。

4. 法演算の逆数の性質

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}
(証明終)
Th.6 法 $n$ で $\binv$ が存在すること $\Leftrightarrow$ $\gcd(b,n)=1$
証明 $\Rightarrow$) $x=\binv$ とおくと定義より
$\exists\ y\ $ such that $\ b \times x = 1 + n \times y$
$\gcd(b,n)$ は $b$ と $n$ の公約数であるので
$1 = b \times x - n \times y$
の約数でもあり、$\gcd(b,n)=1$.

$\Leftarrow$) は次のアルゴリズムより。(証明終)
Algorithm 7 (法 $n$ での逆数)
  • 入力:$b$, $n$
  • 出力:法 $n$ での $b$ の逆数 $\binv$
  1. 拡張ユークリッドアルゴリズムを引数 $b$, $n$ で実行し、$d=\gcd(b,n)$ と、$d=bx+ny$ を満たす $x$, $y$ を求める。
  2. $d \neq 1$ ならば「逆数は存在しません」と表示し、終了。
  3. $x$ を出力。
計算のテクニック 
  • Alg.7 では $y$ は出力に関与しませんので、 拡張ユークリッドを呼び出すよりも、 拡張ユークリッドから $y$ の計算式を除いた専用ルーティンを組んだ方が速くなります。

5. $\gcd(b,n) \gt 1$ のとき

 (1) $4 \times x \equiv 3 \pmod{10}$ は解を持つか?
(2) $4 \times x \equiv 6 \pmod{10}$ は解を持つか?
 これを一般化すると
Prop.8 $d = \gcd(b,n) \gt 1$ とする。このとき、合同式
$b \times x \equiv a \pmod n$
の解は
  • $a$ が $d$ の倍数でなければ存在しない。
  • $a$ が $d$ の倍数であれば $\bmod n$ で $d$ 個の解が存在する。
証明 は上の と同じことを記号で書くだけです。(証明終)

 ということで、 法 $n$ の除算を考えるときは大抵、除数 $b$ が $n$ と互いに素 であることを仮定します。

6. 法 $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 
  1. $n=3k+1$ のとき  $\inv{3} \equiv \displaystyle{\frac{2n+1}{3}}$
  2. $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$

まとめ

  • 法演算の除算は、逆数を先に定義してから考える。
  • 法 $n$ と互いに素な数 $b$ だけが逆数を持つ。
  • 逆数は、拡張ユークリッドアルゴリズムを応用して求められる。

自宅学習の例

 法 $11$ では、$2$ から $9$ が互い逆数になるペアに分かれて
$2 \times 6 \equiv 3 \times 4 \equiv 5 \times 9 \equiv 7 \times 8 \equiv 1$
となっています。このことから
$10\,! \equiv ( 2 \times 6 ) \times ( 3 \times 4 ) \times ( 5 \times 9 ) \times ( 7 \times 8 ) \times 10 \equiv 10 \pmod{11}$
が導かれます。
 では、法が素数 $p$ のとき、同じ考え方で
$(p-2)\,! \equiv 1 \pmod p$ ( ウィルソンの定理 )
を導いてみましょう。

戻る