アルゴリズム論特論（塩田） 2020年度教材 第6回
- 出席代わりに、塩田 ( shiota＠is.kochi-u.ac.jp ) 宛てにメールを出してください。
- 件名は「アルゴリズム論特論第６回出席」とでもしてください。
今日のテーマ
前回、法演算の加法・減法・乗法・べき乗を定義しました。
今日はさらに除算を定義します。
1. 割り算と除算の違い
何を今更、と思うかもしれませんが
問 $11 \div 3$ って何だ？？
解釈１ 3つに均等に割る
- 長さ 11cm の羊羹なら 11/3 cm に切り分ければ良し
- でも、11個の飴だと、そうはいかないよね
解釈２ 3人に分ける
- 11個の飴を、
- 3人にまず1個ずつ配る → まだ8個ある
- もう1個ずつ配る → まだ5個ある
- もう1個ずつ配る → まだ2個ある
- 2個余ったけど仕方ない
解釈１は均等に「割る」ので「割り算」、
解釈２は３個ずつ「除いてゆく」ので「除算」という感じがしませんか？
2. 法演算で行うべきは割り算か除算か？
問 $\bmod 7$ で $11 \div 3$ って何だ？？
解釈１かな？
- $11 \equiv 4 \equiv -10 \pmod 7$ なので、法演算では「大きさ」の概念がありません。
大きさの無いものを均等に割れ、と言われても困りますね。
解釈２かな？
- 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$ の逆数を求めてみましょう。
答え
$\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$
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$
- 拡張ユークリッドアルゴリズムを引数 $b$, $n$ で実行し、$d=\gcd(b,n)$ と、$d=bx+ny$ を満たす $x$, $y$ を求める。
- $d \neq 1$ ならば「逆数は存在しません」と表示し、終了。
- $x$ を出力。
計算のテクニック
- Alg.7 では $y$ は出力に関与しませんので、
拡張ユークリッドを呼び出すよりも、
拡張ユークリッドから $y$ の計算式を除いた専用ルーティンを組んだ方が速くなります。
5. $\gcd(b,n) \gt 1$ のとき
問 (1) $4 \times x \equiv 3 \pmod{10}$ は解を持つか？
答え
$4x$ を $10$ で割った余りは偶数しかあり得ませんので、$3$ にはなりません。
よって解はありません。
(2) $4 \times x \equiv 6 \pmod{10}$ は解を持つか？
答え
問題は
$4 x = 6 + 10y$ は整数解 $(x,y)$ を持つか
と言い換えられます。両辺を $2=\gcd(4,10)$ で割れば
$2 x = 3 + 5y$ は整数解 $(x,y)$ を持つか
となり、結局
$2 \equiv 3 \pmod 5$ は解 $x$ を持つか
という問題に帰着します。
これは
Th.5 より $\bmod 5$ で唯一の解 $x \equiv 4 \pmod 5$ を持ちますが、
$\bmod 10$ では 2 つの解 $x \equiv 4,\,9 \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
- $n=3k+1$ のとき
$\inv{3} \equiv \displaystyle{\frac{2n+1}{3}}$
- $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$ ( ウィルソンの定理 )
を導いてみましょう。
戻る