本題に入る前にまたお知らせ.
Springerがオープンアクセスにしている本を追加しました.
今のところ数学書は少ないですが,計算機科学まわりなんかだとそれなりに本があります.
さらに,Tom Leinster 先生の本も追加させていただきました.Leinster の『Basic Category Theory』はすごくいい入門書なので,知らなかった人はぜひこの機に読んでください.
それでは『はじめての数論』の演習問題をやっていきます.
今回取り組むのは演習問題 10.1 です.
問題文
問a の問題文
$B \equiv 1$ $\mod m$ または $B \equiv -1 \mod m$ であることを示せ.
問b の問題文 (今回はやらない)
いくつかの小さな $m$ の値に対して $B$ を計算し,いつ $+1 \mod m$ となり,いつ $-1 \mod m$ となるかのパターンを見つけてみよ.
回答 - 問a
問題の背景
まず問題の背景を少し説明します.
この問題の法 $m$ が素数である場合には,これは有名なウィルソンの定理に帰着します.
この定理を素数とは限らない自然数 $m$ について拡張することを考えましょう.このとき単純に $(m-1)! \mod m$ を計算してしまうとゼロになるに決まっているので,自然とは言えない感じになります.
そこで,ゼロになるのを避けるために $m$ と互いに素な数全体で積を取ることにします.それが,この問題でいわれている $B$ そのものです.
つまりは,この問題はウィルソンの定理の一般化になっているわけです.
ウィルソンの定理の類推から
ウィルソンの定理の拡張になっているということは,ウィルソンの定理の証明が参考になる可能性があります.
ウィルソンの定理の証明をどのようにするか,参考のために思い出しましょう.
(証明)$p=2$ のときは自明なので,$p$ は奇素数だとします.
$p$ が素数ならば単元群 $G_p := (\mathbb{Z} / p \mathbb{Z})^{\times}$ は巡回群であり,原始根 $g$ が存在します.したがって件の積を $B$ とすると
$$ B = \prod_{i \in G_p} i = g^{p(p-1)/2} $$
というように原始根 $g$ のべき乗として表すことができます.
したがって $B^ 2 = g^ {p(p-1)}$ となり,Fermatの小定理より $B^ 2 = 1$ です.これは $(B-1)(B+1)$ が $p$ で割り切れることを意味しますが,$p$ は素数なので $B = \pm 1 \mod p$ がわかります.
仮に $B = 1$ だとしましょう.このとき $g$ の位数は $p(p-1)/2$ を割り切ります.$g$ は原始根なので,$p-1$ が $p(p-1)/2$ を割り切ることになります.ところが $p \geq 3$ より $p$ は奇数なので,これは矛盾.したがって $B =- 1$ です. □
でもこれを素直に一般の場合に拡張することはできません.次のような障害があります.
そもそも $G_m := (\mathbb{Z} / m \mathbb{Z})^{\times}$ は一般には巡回群とは限りません.
$B^ 2 = 1$ から $B = \pm 1$ を導くのは,一般の $G_m$ 上ではできません.たとえば $m = 8$ のとき $3^ 2 \equiv 1 \mod 8$ ですが,$3$ は $\pm 1$ とは合同ではありません.
こういったハードルがあるので,この問題は単純な議論の拡張ではうまくいきません.この時点で,私は「この問題難しいな~」と思いました.
中国式剰余定理を使えないか?
最初に考えたのは,中国式剰余定理を使って $m$ が素数の場合に帰着するというアプローチです.素数の場合はわかっているので,そこに帰着したいというのは自然な発想だと思います.
しかし,このアプローチはあっという間に行き詰りました.
中国式剰余定理は $m= ab$ ($a.b$ は互いに素)というときにしか使えないので,$m$ が素数のベキ $p^ e$ の形をしているときに困ってしまうのです.
しばらく試行錯誤しましたが,途中で断念.
具体例を計算する
いったん頭を冷やして,具体例の計算をすることにしました.
Julia を召喚して, $1$ から $1000$ までの数についてその圧倒的計算力でざあぁーっと計算していただきました.以下がそのときのコードです.
using Primes # ウィルソンの定理の拡張 in Julia for m = 1:1000 B = 1 for i = 1:m if gcd(i,m) == 1 B = (B * i) % m end end r = B % m if isprime(m) == false println(string(m) * ' ' * string(r)) end end
なお isprime
というのは素数かどうか判定するコマンドです.using Primes
と書いてあるのは,isprime
を使用するためのライブラリの仕様を宣言しています.素数についてはもう知ってるので,除外しているわけです.
私はその結果の表をじーっと眺めてひらめきがやってくるのを待っていましたが,遂にやってきませんでした.
かなしいね.
手計算をする
そろそろ手詰まり感が出てきました.
とりあえず手を動かし続けないといけないと思ったので,今度は Julia に頼まずに手計算で計算をすることにしました.
手計算で計算しようとすると,上記のコードのように計算するのでは計算ミスが頻発します.そこで,$xy \equiv 1 \mod m$ となる組 $(x,y)$ を括りだしていく手法を使いました.
以下がそのときのノートです.
青色と赤色の線が見えると思います.青色の線でつながれた数 $x,y$ は $xy \equiv 1 \mod m$ を満たしています.そして赤色の丸がついている数 $x$ は $x^ 2 \equiv 1 \mod m$ を満たしています.
このときのポイントは,$m$ が素数でなかったとしても $G_m := (\mathbb{Z} / m \mathbb{Z})^{\times}$ は群であり,したがってどのような元 $x \in G_m$ に対しても
$xy \equiv 1 \mod m$ を満たす $y \neq x$ がただ一つあるか,
あるいは $x^ 2 \equiv 1 \mod m$ が成り立つか
どちらかが成り立つ__ということです.
これを用いることで,検算が非常に容易になりますし,大きな数の掛け算をする回数を減らすことができます.
位数2の元がポイント
ここで,ようやく非自明な知見を得ました.
$B$ の値を計算するときには,$G_m$ の位数 $2$ の元(と単位元)だけで積をとればいいということです.
なぜかというと,他の元 $x \in G_m$ に対しては必ず逆元 $y \neq x$ が存在しているので,積を取るときにはキャンセルされてしまうからです.
$G_m$ の位数2以下の元からなる部分群を $K_m$ としましょう.示したいことは,$K_m$ の元すべての積が $\pm 1 \mod m$ であることです.
もしも $K_m$ の元がすべて $\pm 1$ であればこれで終了ですが,当然そんなことはないのでもう少し工夫が要ります.
位数2の元を詳しく調べる
ようやく手がかりが得られたので,位数2以下の元がなす部分群 $K_m$ についてもう少し調べましょう.
確定でここに属している元があります.$1$ と,あと $m-1$ (つまり $-1$ ) です.
それ以外の元についてはあるのかないのかも法則性がよくわかりません.しかし上の手計算で作った表をよく見ると,$\pm 1$ 以外の元はあるとしても偶数個であるように見えます.
これは偶然でしょうか……?
暫くぼーっと見つめているうちに気づいたのですが,偶然ではありませんでした.
仮に $x^ 2 = 1$ であるとすると,$(-x)^ 2 = 1$ です.だからマイナス1倍するという写像は写像 $φ: K_m \to K_m$ を誘導します.
この写像の固定点を調べておきましょう.$φ(x) = x$ とします.このとき $2x \equiv 0 \mod m$ なので,$m$ が $x$ と互いに素であるという条件から $2 \equiv 0 \mod m$ です.つまり $m=2$ でなければなりません.逆にいえば,$m \geq 3$ のときには $φ$ は固定点を持たないわけです.
したがって $φ$ によって $K_m$ の元は2つずつペアになり,ペアごとにその積の値は $-1$ になります.すなわち $K_m$ の元すべての積は $\pm 1$ のどちらかであり,これで証明が完結したことになります.
お疲れさまでした.
感想とまとめ
難しい問題でした.パッと問題文を見た感じでは簡単だろうと思っていたのに,やってみると結構手ごわくて「きゃー」って悲鳴あげてました.具体例を計算しても,いつ $1$ でいつ $-1$ になるのかの法則が割とみえにくいんですよね.
作意解はもっと簡単なのでしょうか?
あと今回の問題で特筆すべきは,せっかく Julia を召喚できるようになったのに,結局手計算の方が示唆的だったということですね.笑えました.
まだまだ Julia に習熟できていないからかもしれません.