どうも、佐野です。前回は $n$ 時間時計の環 $\mathbb{Z}_ n$ を作り、 $n = 5$ のときこれが体となることを見ました。今回は $\mathbb{Z}_ n$ が体となる条件を明らかにし、その体をプログラムで実現しましょう。
目次：
剰余環が体になる条件は？
前回 Z_5 は体で Z_6 は体でないこと確認しました。
n = 2 ... 10 の範囲で Z_<n> の乗法表を出力してみましょう。 Z_<n> が体になるということは「$0$ 以外の全ての数は、掛けて $1$ になる数（逆数）がある」ということです。行を順番に見て行って、一つでも 1 を含まないものがあったら NG です。
n = 2:
* | 0 1
--------------
0 | 0 0
1 | 0 1
n = 3:
* | 0 1 2
------------------
0 | 0 0 0
1 | 0 1 2
2 | 0 2 1
n = 4:
* | 0 1 2 3
----------------------
0 | 0 0 0 0
1 | 0 1 2 3
2 | 0 2 0 2 // NG
3 | 0 3 2 1
n = 5:
* | 0 1 2 3 4
--------------------------
0 | 0 0 0 0 0
1 | 0 1 2 3 4
2 | 0 2 4 1 3
3 | 0 3 1 4 2
4 | 0 4 3 2 1
n = 6:
* | 0 1 2 3 4 5
------------------------------
0 | 0 0 0 0 0 0
1 | 0 1 2 3 4 5
2 | 0 2 4 0 2 4 // NG
3 | 0 3 0 3 0 3 // NG
4 | 0 4 2 0 4 2 // NG
5 | 0 5 4 3 2 1
n = 7:
* | 0 1 2 3 4 5 6
----------------------------------
0 | 0 0 0 0 0 0 0
1 | 0 1 2 3 4 5 6
2 | 0 2 4 6 1 3 5
3 | 0 3 6 2 5 1 4
4 | 0 4 1 5 2 6 3
5 | 0 5 3 1 6 4 2
6 | 0 6 5 4 3 2 1
n = 8:
* | 0 1 2 3 4 5 6 7
--------------------------------------
0 | 0 0 0 0 0 0 0 0
1 | 0 1 2 3 4 5 6 7
2 | 0 2 4 6 0 2 4 6 // NG
3 | 0 3 6 1 4 7 2 5
4 | 0 4 0 4 0 4 0 4 // NG
5 | 0 5 2 7 4 1 6 3
6 | 0 6 4 2 0 6 4 2 // NG
7 | 0 7 6 5 4 3 2 1
n = 9:
* | 0 1 2 3 4 5 6 7 8
------------------------------------------
0 | 0 0 0 0 0 0 0 0 0
1 | 0 1 2 3 4 5 6 7 8
2 | 0 2 4 6 8 1 3 5 7
3 | 0 3 6 0 3 6 0 3 6 // NG
4 | 0 4 8 3 7 2 6 1 5
5 | 0 5 1 6 2 7 3 8 4
6 | 0 6 3 0 6 3 0 6 3 // NG
7 | 0 7 5 3 1 8 6 4 2
8 | 0 8 7 6 5 4 3 2 1
n = 10:
* | 0 1 2 3 4 5 6 7 8 9
----------------------------------------------
0 | 0 0 0 0 0 0 0 0 0 0
1 | 0 1 2 3 4 5 6 7 8 9
2 | 0 2 4 6 8 0 2 4 6 8 // NG
3 | 0 3 6 9 2 5 8 1 4 7
4 | 0 4 8 2 6 0 4 8 2 6 // NG
5 | 0 5 0 5 0 5 0 5 0 5 // NG
6 | 0 6 2 8 4 0 6 2 8 4 // NG
7 | 0 7 4 1 8 5 2 9 6 3
8 | 0 8 6 4 2 0 8 6 4 2 // NG
9 | 0 9 8 7 6 5 4 3 2 1
NG が一つも付いてないのは n = 2, 3, 5, 7、そうでないものは n = 4, 6, 8, 9, 10 です。Z_<n> が体となる n の条件はなんだか分かりますか？
（はい、答えどうぞ！）
分からないという方は素数を数えて落ち着いた上で、もう一度見てみてください（答えは記事の後半で！）
「ユークリッド互除法」と「ベズーの等式」
Z_<n> が体となる n の条件を明らかにするため、「ユークリッド互除法」と「ベズーの等式」を紹介します。この議論は次回より一般化して使うので、詳しめに説明します。
「ユークリッドの互除法」は二つの数の最大公約数を求めるためのアルゴリズムです。「互除」という言葉の通り、数を交互に割っていって、「最後の余り」が最大公約数になるというものです。
試しに $\gcd(1732, 194)$ を求めてみましょう。
\begin{eqnarray}
\bf{1732} &=& 8 &\cdot& \bf{194} &+& 180 \\
194 &=& 1 &\cdot& 180 &+& 14 \\
180 &=& 12 &\cdot& 14 &+& 12 \\
14 &=& 1 &\cdot& 12 &+& 2 \\
12 &=& 6 &\cdot& \bf{2} &+& 0
\end{eqnarray}
割った数が次に割られる数に、余った数が次に割る数に、数が左下へと移っているのが見えますか？最後は余り $0$ となるので、そのときの除数 $2$ が最大公約数だということです。
\begin{eqnarray}
\gcd(1732, 194) &=& \gcd(194, 180) \\
&=& \gcd(180, 14) \\
&=& \gcd(14, 12) \\
&=& \gcd(12, 2) \\
&=& 2
\end{eqnarray}
gcd の実装はこんなです：
func gcd(a: Z, _ b: Z) -> Z {
switch b {
case 0:
return a
default:
return gcd(b, a % b)
}
}
簡単ですね。
ちなみにこの実装、 $a < b$ でもちゃんと動くのは分かりますか？
次に「ベズーの等式」を紹介します：
$0$ でない整数 $a, b$ に対し、$ax + by = \gcd(a, b)$ となる整数 $x, y$ が存在する。
この定理は「左右に $a$歩、$b$歩 進むのを何回か繰り返してれば、いずれスタート地点から右に $d = \gcd(a, b)$ 歩進んだところに辿り着ける」という感じです。
先ほどの例では $\gcd(1732, 194) = 2$ だったので「ベズーの等式」を満たす $1732x + 194y = 2$ となる $(x, y)$ があるということなのですが、これはユークリッド互除法を下から解き直せば自ずと求まります。
互除法の計算式を「余り $= \cdots$」の形に書き直すと：
\begin{eqnarray}
\bf{2} &=& 14 &-& 1 &\cdot& 12\\
12 &=& 180 &-& 12 &\cdot& 14\\
14 &=& 194 &-& 1 &\cdot& 180\\
180 &=& \bf{1732} &-& 8 &\cdot& \bf{194}\\
\end{eqnarray}
これを上に向かって順に代入していけば、
\begin{eqnarray}
\bf{2} &=& 14 \ \ &-& 1 \cdot 12\\
&=& 14 \ \ &-& 1 \cdot (180 - 12 \cdot 14)\\
&=& -1 \cdot 180 \ \ &+& 13 \cdot 14 \\
&=& -1 \cdot 180 \ \ &+& 13 \cdot (194 - 1 \cdot 180) \\
&=& 13 \cdot 194 \ \ &-& 14 \cdot 180\\
&=& 13 \cdot 194 \ \ &-& 14 \cdot (1732 - 8 \cdot 194)\\
&=& -14 \cdot \bf{1732} \ &+& 125 \cdot \bf{194}\\
\end{eqnarray}
というわけで、$(x, y) = (-14, 125)$ が得られます（実際 $14\cdot1732 + 125\cdot194 =$ $-24248 + 24250 = 2$ ）。
このまま実装するのは難しいので、もう少し議論を一般化します。 $(a_0, b_0) = (a, b)$ から始めて、順に「被除数 $a_n$」と「除数 $b_n$」を作っていきます。$n$ 回目の割り算における商を $q_n$, 余りを $r_n$ とすると：
a_n = p_n \cdot b_n + r_n \ \ (0 \le r_n \lt \left|b_n\right|)
その次は $b_n$ を $r_n$ で割るので、
\begin{eqnarray}
a_{n+1} &=& b_n \\
b_{n+1} &=& r_n = a_n - p_n \cdot b_n
\end{eqnarray}
これで最後に $b_N = 0$ となったときの $a_N$ が $\gcd(a_0, b_0)$ です。この漸化式を「行列とベクトルの積」の形で書き直すと：
\begin{eqnarray}
\left(
\begin{array}{c}
a_{n+1} \\
b_{n+1}
\end{array}
\right)
&=&
\left(
\begin{array}{c}
b_n \\
a_n - p_n \cdot b_n
\end{array}
\right) \\
\\
&=&
\left(
\begin{array}{cc}
0 & 1 \\
1 & -p_n
\end{array}
\right)
\left(
\begin{array}{c}
a_n \\
b_n
\end{array}
\right)
\end{eqnarray}
これを $N$ から $0$ まで下げていけば、
\begin{eqnarray}
\left(
\begin{array}{c}
a_N \\
0
\end{array}
\right)
&=&
\left(
\begin{array}{cc}
0 & 1 \\
1 & -p_{N-1}
\end{array}
\right)
\left(
\begin{array}{c}
a_{N-1} \\
b_{N-1}
\end{array}
\right)
\\ \\
&=&
\left(
\begin{array}{cc}
0 & 1 \\
1 & -p_{N-1}
\end{array}
\right)
\left(
\begin{array}{cc}
0 & 1 \\
1 & -p_{N-2}
\end{array}
\right)
\left(
\begin{array}{c}
a_{N-2} \\
b_{N-2}
\end{array}
\right)
\\
\\
&=&\cdots
\\
\\
&=&
\left(
\begin{array}{cc}
0 & 1 \\
1 & -p_{N-1}
\end{array}
\right)
\cdots
\left(
\begin{array}{cc}
0 & 1 \\
1 & -p_{0}
\end{array}
\right)
\left(
\begin{array}{c}
a_0 \\
b_0
\end{array}
\right)
\end{eqnarray}
となります。
つまり $(a_0, b_0)$ に掛かってる $N$ 個の行列の積：
\left(
\begin{array}{cc}
0 & 1 \\
1 & -p_{N-1}
\end{array}
\right)
\cdots
\left(
\begin{array}{cc}
0 & 1 \\
1 & -p_{0}
\end{array}
\right)
=
\left(
\begin{array}{cc}
x & y \\
? & ?
\end{array}
\right)
の一行目こそが「ベズーの等式」に出てくる整数の組 $(x, y)$ です！
ここまで分かれば実装できますね！
整数 a, b に対して「ベズーの等式」$ax + by = \gcd(a, b) = d$ を満たす (x, y, d) を返す関数 bezout を実装します。まずは互除法で商の列 $(q_0, q_1, ..., q_N)$ と余り $d$ を求め、その後に商の列から定まる行列の積を計算して $(x, y)$ を求めます：
func bezout(a: Z, _ b: Z) -> (x: Z, y: Z, d: Z) {
typealias M = Matrix<Z, TPInt_2, TPInt_2>
func euclid(a: Z, _ b: Z, _ qs: [Z]) -> (qs: [Z], d: Z) {
switch b {
case 0:
return (qs, a)
default:
let (q, r) = (a / b, a % b)
return euclid(b, r, [q] + qs)
}
}
let (qs, d) = euclid(a, b, [])
let m = qs.reduce(M.identity) { (m: M, q: Z) -> M in
m * M(0), 1, 1, -q)
}
return (x: m[0, 0], y: m[0, 1], d: d)
}
いきなり未定義の型 M = Matrix<Z, TPInt_2, TPInt_2> を出してしまいましたが、これはあらかじめ作ってあった「$\mathbb{Z}$係数の2次正方行列」です。追って実装は公開するので許してください
確認してみましょう：
let (x, y, d) = bezout(1732, 194) // (-14, 125, 2)
1732 * x + 194 * y == d // true
めでたく上の計算で求めた通りの結果が得られました！
改めて、剰余環が体になる条件とは？
元々考えたかったのは「 $\mathbb{Z}_ n$ が体になる条件は何か？」ということです。ここで $a \in \mathbb{Z}_n$ と $n$ に対する「ベズーの等式」は：
ax + ny = \gcd(a, n)
これを $\bmod{n}$ すると、$ny$ の部分は $n$ の倍数なので消えて、
a \cdot x \equiv \gcd(a, n) \pmod{n}
ここでもし $\gcd(a, n) = 1$ ならば、まさしくこの $x$ が $\bmod{n}$ における $a$ の逆数ということになります。逆に $\gcd(a, n) = d \ne 1$ ならば、$a \cdot x \equiv 1 \pmod{n}$ なる $x$ はあり得ません（$1$ が $d$ の倍数ということになってしまいます）。
$\bmod{n}$ で $a$ の逆数が存在する条件は「$\gcd(a, n) = 1$」すなわち「$a, n$ は互に素」ということです。そして $\mathbb{Z}_ n$ が「体」だということは、$a = 1 ... n-1$ の全てに対して $n$ が互いに素ということなので、求める条件は：
$\mathbb{Z}_n$ が体 $\ \Leftrightarrow\ $ $n$ は 素数
ということでした！
素数（Prime Number）$p$ に対して $\mathbb{Z}_ p$ を体と見たものを $\mathbb{F}_ p$ と書き「位数 $p$ の 有限体」と言います。冒頭で見たのは位数 $p = 2, 3, 5, 7$ の有限体 $\mathbb{F}_ 2, \mathbb{F}_ 3, \mathbb{F}_ 5, \mathbb{F}_ 7$ の乗算表でした。
有限体を実装しよう！
最後にこの有限体 F_<p> を実装して終わりましょう。環としての演算は Z_<n> で実装済みなので、「積に関する逆元」を実装すればそれで体となります。上で実装した bezout を使って：
struct F_<p: TPInt>: Field {
let value: Z
...
var inverse: F_<p> {
if value == 0 {
fatalError("0-inverse")
}
// find: a * x + p * y = 1
// then: a^-1 = x (mod p)
let (x, _, r) = bezout(a, mod)
if r != 1 {
fatalError("\(mod) is non-prime.")
}
return F_(x)
}
}
めでたく $\mathbb{F}_p$ できました！
最後にオマケとして $\mathbb{F} _p$ の「べき乗表」を見てみましょう：
p = 2:
^ | 0 1
--------------
1 | 1 1
p = 3:
^ | 0 1 2
------------------
1 | 1 1 1
2 | 1 2 1
p = 5:
^ | 0 1 2 3 4
--------------------------
1 | 1 1 1 1 1
2 | 1 2 4 3 1
3 | 1 3 4 2 1
4 | 1 4 1 4 1
p = 7:
^ | 0 1 2 3 4 5 6
----------------------------------
1 | 1 1 1 1 1 1 1
2 | 1 2 4 1 2 4 1
3 | 1 3 2 6 4 5 1
4 | 1 4 2 1 4 2 1
5 | 1 5 4 6 2 3 1
6 | 1 6 1 6 1 6 1
この表には (a, n) 成分に「a の n 乗」が表示されています。列の一番右側が全部 1 になっています。これは 0 でない a in F_p に対して a ^ (p - 1) が F_p として 1 に等しいということです。つまり：
【フェルマーの小定理】
素数 $p$ と整数 $a$ が互に素のとき、 $a^{p-1} \equiv 1 \pmod{p}$
を示しています！
前回紹介した『時計の世界の整数論』では他にも「オイラー基準」や「平方剰余の相互法則」などべき乗法則に関する面白い話が紹介されています。是非見てみてください！
次回は「多項式環」を作ります。整数環から有限体を作ったように多項式環から拡大体を作るのがシリーズのゴールであった「代数拡大」です…！
ソースコード
GitHub: SwiftyAlgebra
宣伝
- 3/19(土) 「第6回 プログラマのための数学勉強会」
- プログラマのための数学勉強会 Facebook ページ
- 個人ブログ Imaginary & Imaginative