彼らは数学しか勉強できない

フェルマーの小定理の証明とオイラーの定理

　整数問題で合同式を使う際、フェルマーの小定理を知っていると応用の幅が広がる。

　フェルマーの小定理は整数aとpにおいて、次の式が成り立つ。

　a（　　p－1）≡1(mod p)

　aとpは互いに素で、pは素数。

「pが素数じゃない場合はどうなるの？」

「合成数の場合はオイラーの定理というものがある。でも、今はフェルマーの小定理が先だ。問題に入る前に定理の証明をしておこう」

「私、証明苦手なんだけど……」

「証明と言っても専門的な知識は必要ない。今から説明するのは英語版のWikipediaを参考にしたものだ」

　まず任意のアルファベットをa個選び、横にp個並べる。

　a＝2、p＝3の場合、並べ方は2（　3）＝8通り。文字をP、Qとして文字列をすべて列挙すると

　PPP、PQQ、QPQ、QPP、QPP、PQP、PPQ、QQQ

　同じ文字で作られたPPPとQQQを除いた残り2（　3）－2個、つまり6個の文字列を考える。

　PQQ、QPQ、QQP、QPP、PQP、PPQ

「今度は残った6個の文字列を2つのグループに分ける」

　PQQとQPQとQQPをグループ1

　PQPとPPQとQPPをグループ2

「このとき、グルーブ1にはPが3個、Qが6個。グルーブ2はPが6個、Qが3個ある。2つのグループにはPとQの個数が、3もしくは3の倍数なので、2（　3）－2は3で割りきれる」

　実は残った文字列をグループに分けるとき、ちょっとしたコツがある。

「次はa＝4、p＝5として、文字をP、Q、R、Sとする」

　文字列の長さは5だから、並べ方は4（　5）＝1024通り。

　一つの文字で作られた文字列PPPPP、QQQQQ、RRRRR、SSSSSを除いた4（　5）－4個の文字列を考える。

「さすがに全部は挙げられないから、一部だけ例を出す。Wikipediaではネックレスで解説されていたが、ここでは都合上、頂点だけの五角形で説明する」

「ネックレス？」

「ああ。手元に紙とペンがあれば、実際に図を書いて、各頂点に文字を当てはめてみてほしい」

　俺がそう言うと、愛華は俺の勉強机にルーズリーフとシャープペンを置き、辺がない五角形を描いた。

　　　　P　　　　　　　

　　Q　　　P

　　　R　S

「PQRSPの5つで作られた五角形を、右回転させる（左でもよい）」

　　　P　　　　　　　P　　

　Q　　　P　→　 P　　　S

　　R　S　　　　　 Q　R

「すると、各頂点が一つずれてPPQRSになった」

「右端の文字を左端に移動させると考えてもいいよね」

「そう言ってもいい」

　同じ要領で進めていくと、PQRSP→PPQRS→SPPQR→RSPPQ→QRSPP　

「QRSPPの右端のPを左側に移動させてPQRSP……あ、最初と同じになった」

「つまり、5つの文字列PQRSP、PPQRS、SPPQR、RSPPQ、QRSPPは同じものと見なすことができる」

　これを1つのグループにすると、Pは10個。Q、R、Sは5個ずつある。

「感覚を掴んでもらうために、ほかのグループもいくつか挙げておこう」

（PPQPQ、QPPQP、PQPPQ、QPQPP、PQPQP）Pが15個でQが10個。

（RQSSR、RRQSS、SRRQS、SSRRQ、QSSRR）Qが5個でRとSがそれぞれ10個。

「結局、どのグループも異なる文字の個数が、5または5の倍数になっている。よって、4（　5）－4は5で割りきれる」

　これを一般化してa、pで考えると、文字列の個数はaだから、文字列の並べ方はa（　p）通り。

　AAA……AAA（Aがp個並んでいる）のように、一つの文字で構成された文字列はa個あるから、異なる文字で構成された文字列の個数は、a（　p）－a個。

　残ったa（　p）－a個の文字列を、前述した方法でグループに分けると、各グループには異なる文字の個数が、pまたはpの倍数になっている。よって、a（　p）－aはpで割りきれる。

「合同式で表すとa（　p）－a≡0(mod p)　方程式と同じように－aを右辺に移項して、a（　p）≡a(mod p)」

　合同式の割り算は、aとpが互いに素、またはpが素数のときだけ可能。よって、両辺をaで割ってa（　　p－1）≡1(mod p)

「一般的には二項定理を用いた数学的帰納法か、整数の性質を利用した背理法で証明するんだが、分かりやすさを考慮した」

　実際、英語版のWikipediaには『This is perhaps the simplest known proof, requiring the least mathematical background（これはおそらく最も単純な知られている証明であり、必要な数学の予備知識は最小限である）』と記されている。

　愛華はノートを見ながら顎に手を当てる。

「……完全には理解できなかったけど、雰囲気は掴めた」

「最初はそんなもんさ。じゃあ、実際に問題を解いてみよう」

　7（　　100）を17で割った余りを求めよ。

「これは簡単、7（　　16）≡1(mod 17)で100＝16・6＋4だから、7（　4）で割った余りと同じ」

　7（　　100）≡7（　4）

「7（　4）は7・7で49　その2乗だから……」

「待った」

　直接7（　4）を求めるよりも、7（　2）・7（　2）に分けて計算した方がいい。

　7（　2）≡49≡－2(mod 17)より、7（　4）≡(－2)（　2）≡4(mod 17)

「なるほど。余りをマイナスで考えた方が計算するときに楽だね」　

「考え方次第で労力をだいぶ減らせる。もう1問解いてみよう」

　aが2以上の整数のとき、a（　23）－aは6で割りきれることを示せ。

「この問題はa（　23）－a≡0(mod 6)を示せってことだよね。法が素数じゃないじゃん」

「そういうときは6を素因数分解して、(mod 2)と(mod 3)でそれぞれ考えればいい。a（　23）－a≡0を、a（　　p－1）≡1の形にして示す」

　a（　23）－a≡0(mod 6)　

　a（　23）≡a(mod 6)　aを右辺に移項する。

　　　　　　　　　　　　　23と6は互いに素なので割り算可能。　

　a（　22）≡1(mod 6)　両辺をaで割る。

　フェルマーの小定理より、a（　1）≡1(mod 2)、a（　2）≡1(mod 3)

　22＝1・22より、a（　22）≡1(mod 2)

　22＝2・11より、a（　22）≡1(mod 3)

「式の形は違うが、a（　23）－a≡0(mod 6)とa（　22）≡1(mod 6)は同じものだ」

　つまり、a（　23）－a≡0(mod 2)とa（　23）－a≡0(mod 3)が成り立つ。

「a（　23）－aは2と3で割りきれるから、2と3の積、6でも割りきれる」

「ねぇ、法が素数じゃないときはオイラーの定理っていうのがあるんだよね。それは使えないの？」

「使えるけど、すべてのaに対して示すことはできない」

　オイラーの定理はnを正の整数として、整数aとnが互いに素のとき、　

　a（　　φ(n)）≡1(mod n)

「φはギリシャ文字で『ファイ』と読む。φ(n)はn以下に、互いに素である正の整数が何個あるかを示している」

「6だったら、1と5だからφ(6)＝2で合ってる？」

「合ってる。この場合、a（　2）≡1(mod 6)が成り立つ」

　ちなみにnが素数の場合、n以下に共通の約数はないので、互いに素の正の整数はn－1個。

　つまり、a（　　n－1）≡1(mod n)となりフェルマーの小定理と同じ形になる。

　φ(n)の値は10の倍数だと、φ(10)＝4、φ(20)＝8、φ(30)＝8、φ(40)＝16、φ(50)＝20、φ(60)＝16、φ(70)＝24、φ(80)＝32、φ(90)＝24、φ(100)＝40

「φ(100)＝40を頭に入れておけば、7の1000乗を100で割った余りを知りたいとき、7（　40）≡1(mod 100)で、1000は40で割りきれるから、余りは1だとすぐに分かる」

「計算で求めたい場合は？」

「オイラーのφ関数というのを使えば、φ(n)の値を求められる」

　ただ、オイラーのφ関数にはΠ（積を表す記号）が出てくるので敷居がやや高くなる。まあ、フェルマーの小定理だけでも整数問題には充分対応できるし、オイラーの定理を使う機会はあまりないかもしれない。

　あとがき

　本文中の『This is perhaps the simplest known proof, requiring the least mathematical background』の日本語訳は、作者がGoogle翻訳で訳した文を、自然な日本語になるようにしたものです。そのため、訳の正確さは保証できません。予めご了承ください。