aRiSA

第15話 フェルマーの小定理*

「さて、合同式に関してはもういいだろう。次は、RSA暗号の復号の決め手となるフェルマーの小定理を証明する。その前に、柴山。まず手始めに整数 a、b が互いに素だったら a x ＋ b y ＝ 1 となる整数 x、y が存在することを証明してくれ」

「はい」

　柴山はすんなり受け入れ教壇に上がり、すらすらと板書を始めた。

「a、 b を固定して

　　　a x ＋ b y　(x、yは整数)

と表される正の整数全体の集合を A とします」

　アリサは不意打ちを食らったようにふためき、急いでノートに写し始めた。

「A は空集合でないので、必ず最小元 d が存在します。 A の定義から

　　　d ＝ a x ＋ b y　(x、yはある整数)

と表せます。 a を d で割ったときの商を q、余りを r とすると

　　　a ＝ d q ＋ r,　 0 ≦ r ＜ d

と表せ、これに d ＝ a x ＋ b y に代入すると

　　　a ＝ (a x ＋ b y)q ＋ r

　　　⇔　 r ＝ a(1 − x q) ＋ b(− y q)

となるので、 r ＞ 0 を仮定すると、 r は A に属する条件を満たすので r ∈ A です。しかし、それは d の最小性に矛盾するので、 r ＝ 0 となります。つまり、 a は d で割り切れます。同様にすれば b も d で割り切れるので、 d は a, b の正の公約数です。 a, b は互いに素だから、 d ＝ 1 です。つまり、 a x ＋ b y ＝ 1 がいえました」

「よろしい」

「す、凄い。なんでそんなにすらすら出るんですか？」

　いきなりスイッチが入って証明を完結させた柴山に、アリサは畏れを感じたようであった。

「え、いやあ。この性質は結構使うので、よく先輩に確認させられるの」

　柴山はチョークをおいて、粉をはたいて落とした。

「あ、これまで習った定理がこうも簡単にできるわけじゃないよ。先輩が特に大事だってやつはしつこく復習してる感じかな」

　アリサは慈道の方へ視線を移す。数学に関して、柴山にとって慈道はいかに絶対的な存在か、そういった師弟間の強い繋がりのようなものをアリサは感じているだった。

「あ、ああ。多項式にも応用が効くし、この証明は整数環や体上の多項式環が単項イデアル整域であることの証明にもなっていてめちゃ重要なんだ」

　慈道はアリサの様子を見て、自分が何か悪いことをしてしまったのかと感じたのか控えめに言った。

「た、単項イデア……？」

「多項式 f(x)、g(x) が互いに素、すなわち、定数以外の共通因数を持たないとすると、必ず

　　　f(x)P(x) ＋ g(x)Q(x) ＝ 1

を満たす多項式 P(x)、Q(x) がとれる。この性質は非常に強力でよく使われる。例えばこの式の両辺を f(x)g(x) で割れば

　　　1/(f(x)g(x)) ＝ Q(x)/f(x) ＋ P(x)/g(x)

と書けるが、これは高校生が当たり前のようにやっている部分分数分解の可能性の証明になっている」

「ああ、一般論ではこうやって証明するんですね。深いです……」

「高校だと『なるものはなる』くらいにしか教えられないからなあ。例えば、俺が高校生の時に無理矢理覚えさせられた

　　　1/(x^3 ＋ 1) ＝ A/(x ＋ 1) ＋ (Bx ＋ C)/(x^2 − x ＋ 1)

っていう部分分数分解は本当に謎だった。なぜ Bx ＋ C としなければならないのか……」

　熱く語り始める慈道を見て、アリサは溜め息をついた。

「やっぱり数学科の学生だったら、そういうことを疑問に思わないといけないですよね。私なんか、問題が解ければいいっていう感じで、気にもとめていませんでした」

　アリサはやや俯いて自嘲し始める。

「あーいやあ、先輩は特殊な方だと思うからあまり気にしない方がいいと思うわ。私も先輩に師事するようになってから色々と見え方が変わってきたクチなので」

　柴山がフォローに入る。

「そうだな。ただ、数学科に入ったからには、あらゆることに何故と問いかけた方がいい。よく企業が求めている論理的思考ってやつだ。『多分こう』じゃなくて『これこれだから絶対こう』という論理的根拠を自信を持って提示するトレーニングを積むことだね」

「頑張ります」

　弱気になっていたアリサは、なんとか前向きな姿勢を取り繕うとしているようだった。

「あ、柴山。その証明で出てきた集合 A の最小元がとれる性質のことはなんと言った？」

「整列性ですよね」

「そう。鈴木さん。これはとても重要だからよく聞いてほしい。一年生の後期に、集合論で習ったはずだ。順序集合 W に対し、空でない任意の部分集合に必ず最小元が存在するとき、 W を整列集合といった」

「あ、はい。確かやりました」

　アリサにはやはり余裕がない。抽象的な順序集合の話なぞ、忘れていてもおかしくない。

「自然数全体の集合が整列集合であるという性質は超がつくほど重要だ。なぜか？」

「数学的帰納法と同値だからですよね」

　テンポよく柴山が答える。

「そうだ。帰納法は、普通だったら無限回の操作が必要な証明をたったの二項目で可能にさせる武器だ。この帰納法が妥当な証明法であるということと、整列性が同値という点は趣深い。というのも、これまでの講義ノートをよく見返してみるとわかるが、『これこれを満たす最小の n をとる』みたいな論法をしていることが多いことに気付くはずだ。例えば、線型代数で最小多項式というものをやったろう。正方行列 A に対して f(A) ＝ O を満たす多項式 f(x) で最小次数かつモニックなものを最小多項式としたはずだ。しかし、最小次数のものが果たして存在するのか？　答えはイエスだ。何故なら、ケーリー・ハミルトンの定理で f(A) ＝ O を満たす f(x) が一つ存在しているから、あ、つまり、特性多項式のことだけど、そのような多項式の集合は空でないので、整列性より最小次数のものが必ず存在するってことになるんだよ」

　コミュニケーション能力は欠如しているが、数学のことに関しては饒舌になる慈道である。

「ああ、やっぱり私ダメかも」

　アリサは目眩（めまい）を起こしたのか、目の周りを指でマッサージし始めた。

「だ、大丈夫だって……」

　柴山もなんとか励まそうとするが、言葉に力はない。

「柴山先輩は今の理解してます？」

「え、まあ。基本ですね……」

　きっぱりと返ってきたのでアリサのモチベーションは混沌とし始めた。

「そうだな……いずれ分かる！」

　慈道も色々言葉を選ぼうとしたが、結局その言葉に落ち着いた。

「高校生にもよく言うじゃん。微分積分は微かに分かれ、分かった積もりになれって。一回ですべてが分かる人間は天才なので、俺たち凡人は反復していくしかないと思うぞ。これは割とマジな話。学問に王道なしだ」

「ですよね」

　難破しかけていたアリサにも、なんとか浮輪にしがみついて生き延びようとする姿勢が見えてきた。

「そうだ、柴山。互いに素の話の続きで、合同式の割り算の話も普通するだろう」

「はいはい」

「m を正の整数とするとき、 a, m が互いに素となるような整数 a に対して

　　　a x ≡ 1 mod m

を満たす整数 x が必ず存在します。つまり、あくまで m を法とした場合限定の話ですが、 a の逆数が存在するわけです。なんでこんなことがいえるかというと、 a, m が互いに素より

　　　a x ＋ m y ＝ 1

なる x, y がとれます。よって m を法としているならば

　　　a x ≡ 1 mod m

が成り立ちます。この x を用いると、例えば

　　　a b ≡ c mod m

だったときに、両辺に x を掛けることで

　　　b ≡ x c mod m

となって、あたかも両辺を a で割ったような計算が可能になります」

「ご苦労。どれ、フェルマーの小定理を示す上で補題を示していく。素数 p に対し、二項係数 pCk が mod p で 0 に合同になることを示そう。ただし、 0 ＜ k ＜ p とする。まず

　　　pCk ＝ p(p − 1)(p − 2)…(p − k ＋ 1)/k!

と書けるが、 p は素数故に、 1 と p 以外に正の約数はない。それに k ＜ p だから、

　　　k! ＝ k(k − 1)(k − 2)…1

のどの因数も p を約数に持ちえない。ということは、

　　　pCk ＝ p(p − 1)(p − 2)…(p − k ＋ 1)/k!

の分子の p は約分されることはない。よって pCk は p の倍数である。合同式で表せば

　　　pCk ≡ 0 mod p

だ」

<thm>

■ pCr ： p を素数とする。 0 ＜ k ＜ p に対して

　　　pCk ≡ 0 mod p

が成り立つ。

</thm>

「よって、任意の整数 a、b に対して、二項定理より (a ＋ b)^p は

　　　a^p ＋ pC1・a^(p − 1) b ＋ pC2・a^(p − 2) b^2 ＋ … ＋ b^p

と展開されるが、今示したことより、 mod p で pC1、pC2 などは 0 と合同。残るのは a^p、b^p だけだ。故に

　　　(a ＋ b)^p ≡ a^p ＋ b^p mod p

が成り立つ。俺は勝手にこれを mod p の二項定理と呼んでいる」

<thm>

■ mod p の二項定理： p を素数とする。任意の整数 a、b に対して

　　　(a ＋ b)^p ≡ a^p ＋ b^p mod p

</thm>

「よし、これで準備は整った。フェルマーの小定理はそもそも以下のような定理だ」

<thm>

■フェルマーの小定理： p を素数とする。任意の整数 a に対して

　　　a^p ≡ a mod p

が成り立つ。特に a と p が互いに素であるとき、すなわち a が p の倍数でないとき、

　　　a^(p − 1) ≡ 1 mod p

が成り立つ。

</thm>

「以下、 mod p で考える。 a^p ≡ a を示すわけだが、 a ＝ 0 のときは明らかに正しい。次に a が正の場合を、帰納法で一気に証明する。 a ＝ 1 のときは正しい。 a ＝ k のときに成り立つと仮定すると

　　　k^p ≡ k。

このとき、 mod p の二項定理より

　　　(k ＋ 1)^p ≡ k^p ＋ 1^p ≡ k ＋ 1

となるので、 a ＝ k ＋ 1 のときも成り立つ。ゆえに任意の正の整数 a に対して成り立つ。最後に a が負の場合を示す。 a ＝ − b と置けば、 b ＞ 0 だから、今示したことが使えて、 b^p ≡ b かつ a^p ＝ (− 1)^p b^p より

　　　a^p ≡ (− 1)^p b

p ＞ 2 のとき、 p は奇数だから (− 1)^p ＝ − 1 となるので

　　　a^p ≡ (− 1)^p b ＝ − 1 b ＝ − b ＝ a

p ＝ 2 のときは − 1 ≡ 1 だから、

　　　a^p ≡ (− 1)^p b ＝ (− 1)^2 b ＝ 1b ≡ − 1 b ＝ − b ＝ a

となり、どんな場合であろうが、 a^p ≡ a は成り立つ。最後に、 a が素数 p と互いに素、すなわち、 a が p の倍数でないとき、

　　　a x ＋ p y ＝ 1

となる整数 x、y をとると、さっき柴山にやってもらったが

　　　a x ≡ 1

だから、

　　　a^p ≡ a 　⇔　 a^(p − 1) a ≡ a

の両辺に x をかけて

　　　a^(p − 1) a x ≡ a x 　⇔　 a^(p − 1) ≡ 1

となる。証明完了！」

　アリサは勿論のこと、柴山も板書をしっかりとっていた。柴山は過去にフェルマーの小定理を学んだことはあるが、復習をしているのであろう。

「ふう。そろそろRSAいけますかね？　もう一時間半かかってますけど」

　柴山はスマートフォンの時計を見てからかうように言った。昨日（さくじつ）、慈道は一時間強あれば解説できると豪語していたのである。

「お、おう」

　慈道はようやく暗号理論入門の講義ノートを開き始めた。