-
フェルマーの小定理(2002-06-16)
フェルマーの定理「 n が素数なら an ≡ a (mod n) 」を、(a+b)n の展開から説明。原始根の概念まで
フェルマーの定理「 n が素数なら an ≡ a (mod n) 」を、(a+b)n の展開から説明。原始根の概念まで
フェルマーの小定理というのは、「素数 p に対して、勝手な整数 n の p 乗を p で割ると余りは n に戻る」というようなものです。例えば、7は素数ですが、
27 = 128 → 7で割ると商18、余り2
37 = 2187 → 7で割ると商312、余り3
47 = 16384 → 7で割ると商2340、余り4
57 = 78125 → 7で割ると商11160、余り5
……
てな感じで、余りは7乗されたもとの数に戻ります。式で書けば、
np ≡ n (mod p)
mod pというのは、pで割った余りで分類して考える、という意味です。例えば、
107 = 10000000
の場合、7で割ると商1428571、余り3ですが、3は7を法として10と合同ですから、やっぱり
107 ≡ 10 (mod 7)
が成り立ってます。「7を法にすると合同」というのは初めて聞くと難しそうですが、なーに、3も10も7で割れば3余るなかまどうし、というだけのことです。それが mod 7 の意味です。「7で割った余りで考えるモード」では、3も10も73も「同じグループ」として同一視できるわけです。この場合の「同じ」は等号 ＝ の「等しい」とは意味が違うので三本線の合同記号 ≡ を書いて「合同だ」といいます。107 も 10 も「7で割った余りで考えるモード」では、どっちも「3余るグループ」なので、こいつらは合同です。
もっと大きい素数、例えば23で試してみます。23乗する数は何でもいいのですが……
523 = 1 1920 9289 5507 8125
→ 23で割ると商518301258916440、余り5
2023 = 83 8860 8000 0000 0000 0000 0000 0000
→ 23で割ると商36472208695652173913043478260、余り20
5の23乗は1京1920兆なんたらというでかい数ですが、23で割ったら余りはズバリ5。20の23乗なんて言い出すと83
素数じゃない場合には、このことは言えません。例えば、
38 = 6561 → 8で割ると商820余り1
となって、余りは3に戻りません。素数じゃない8では、うまくいきませんでした。しかし、
35 = 243 → 5で割ると余り3
37 = 2187 → 7で割ると余り3
のよーに、右上にくっつく指数が5や7といった素数のときは、ちゃんと余りがもとの数と合同になります。
別記事「高校数学で遊ぶ公開鍵暗号RSA」を読んだかたなら、こういった計算が、公開鍵暗号理論の基礎とつながってくることが、なんとなく分かるかと思います。暗号理論をもっとホントにちゃんと理解するには、こうした整数論の基礎知識が必要なのです。また、そうした暗号理論への応用などがなくても、これはこれ自体として純粋におもしろいもので、小定理をもとに、さらにいろいろと宝石のように美しい整数のふしぎな奥深さをさぐってゆくことができます。
なお、フェルマーの「小定理」という呼び名の「小」ですが、単に「フェルマーの定理」というと、フェルマーの最終定理の話と紛らわしいので、区別するために「小」定理と呼んでます。フェルマーの最終定理（大定理）については、ぜんぜん知らなくてもべつにこの記事的には関係ないので気にしないでください。あくまで小定理のほうです。大定理ってどんなのだか参考までにだいたいでも教えて！というかたもおられるかもしれませんが、その説明を書くにはこの記事のスペースは狭すぎます。
フェルマーの小定理は、オイラーの定理の特殊例として導入するのが論理的にスッキリするのですが、ここではもっと厨房で強引なやり方で、やってみます。
(a + b)2 = a2 + 2ab + b2
てなことは、ご存じと思います。イメージとしては辺の長さが a+b な正方形の面積。
形式的には、(a+b)(a+b) のうしろの(a+b)をひとかたまりと思って a(a+b) + b(a+b) と展開して、さらに(a+b)を分配法則でばらしたら、
aa + ab + ba + bb
になって、公式の通りになるでしょう。
でもって、次に (a+b)3 を考えます。これは
(a+b)(a+b)(a+b)
という3重の積なので、展開しつくすと、3重の積がわらわら出てくるハズですね。どうわらわら出るにせよ、1個めの(a+b)から発生するのはaかb、2個めの(a+b)から発生するのもaかb、3個めの(a+b)から発生するのもaかb、なのだから、結局 a か b かを3個、並べる話になるでしょう……
つまり、aaa, aab, aba, abb, baa, bab, bba, bbb の8項が発生し――辺の長さが (a+b) である立方体の体積をイメージすると、角砂糖が2列2行2段で8個つみかさなってるよーな状態になるから、項が8個あるのは直感的にも分かるハズ――この8項を整理せいとんすると、要するに、
a3 が1個、a2b が3個、ab2 が3個、b3 が1個（合計8個）
になります。公式としては、
(a + b)3 = a3 + 3a2b + 3ab2 + b3
ここで重要なのは、この公式そのものというより、1,3,3,1という係数の部分です。
なんで1,3,3,1になったか深く考えると――我々は、いずれにせよ、aまたはbを3個、ピックアップして並べなければいけないのですが、「aばっかり3個がいい。bなんか1個もほしくない」という並べ方はaaaの1通りしかないのは明らかです。でもって「aが2個、bが1個がワタシの趣味」という人には、aab、aba、baaの3通りの並べ方が与えられるでしょう。「aが1個、bが2個がイイ！」という人にも、bba、bab、abbの3通りが与えられるでしょう。で「bばっかり3個がいい。bたん萌え〜」という人にはbbbです。bだけしか使ったらいけないんだから、そういう並べ方はbbbという一通りしかないのは当たり前。
このことを別の角度からみなおすと、1,3,3,1という係数は、「3個のものから3個を選ぶ選び方のパターン数」「3個のものから2個を選ぶ選び方のパターン数」「3個のものから1個を選ぶ選び方のパターン数」「3個のものから0個を選ぶ選び方のパターン数」です。なぜかというと――3匹のこぶたブー、フー、ウーで説明してみます……
3軒のかわいいおうち、ブーさんち、フーさんち、ウーさんちがあるとして、あなたは3軒を順に訪問します。どのおうちでもaまたはbを1個だけ分けてもらいます。aばっかり3個集めたい人は、ブーさんち、フーさんち、ウーさんちの全部からaをもらわねばなりません。3軒のおうちから「aをもらう場所」として3軒すべてを選ぶ必要があります。次に「aが2個、bが1個」を集めるには、3軒のおうちのうち、どこでもいいからどこか2軒でaをもらって、残りの1軒でbをもらうことになります。つまり「aをもらう場所」として3軒から2軒を選ぶことになります。「aが1個、bが2個」を集めるには、3軒のうち「aをもらう場所」をどこでもいいから1軒だけ選ぶ必要があります。最後にaなんかほしくない「bたん萌え」の人は、「aをもらう場所」は0軒です。ブーさんち、フーさんち、ウーさんち、の全部で「bをくれ」と要求することになるでしょう。
つまり、1,3,3,1というのは、コンビネーション記号を使って書いたら、
3C3 = 1
3C2 = 3
3C1 = 3
3C0 = 1
にほかなりません！ 「3軒の家から☆個のaをもらう場所を選ぶときの選び方の数」だからです。
(a + b)3 = 3C3a3 + 3C2a2b + 3C1ab2 + 3C0b3
このシクミが分かってしまえば、(a+b)4, (a+b)5, (a+b)6, ... , (a+b)n は、すべていっきょに理解できるでしょう。
(a + b)n = nCnan + nCn-1an-1b + nCn-2an-2b2 + ... + nC0bn
この形は実際に (a+b) のなんとか乗、を計算するときの実用上は、べんりじゃないですが、このように透きとおらせておくと、以下でみるように、フェルマーの小定理がほとんど自明になります。なお、ご存じかもしれませんが、nCr は、具体的には次の値になります。
nCr = n! / ( r!(n-r)! )
公式は分数の形ですが、もちろん分子は分母で割り切れて、実際の値は整数です。
ここで右肩の数 n が素数だと思ってみましょう。(a + b)5 とか (a + b)7 とか (a + b)11 など。で、これを展開した場合、bを1個も含まない項の係数は1です。bばっかりの項の係数も1です。例えば、
(a + b)7 = a7 + なんかの係数a6b + 複雑な展開式ぐちゃぐちゃ... + b7
てな感じで、まんなかは難しそうだけど、両端はa7とb7がスッピンで出てきます。で、まんなかのぐちゃぐちゃ部分には「aの何乗かとbの何乗かの積」にnCrの形の係数がかかっています。この係数は具体的には
nCr = n! / ( r!(n-r)! )
であって、その左辺の分子は n! だから、もちろん n で割り切れます。分母は……とみると、両端の2項を除外してまんなかだけ考えてるので、r=0 または r=n ということは、ないです。rは1以上n未満の数です。nからそういうrを引いた(n-r)も、同じく1以上n未満の数です。ところが、いま n は素数と仮定してるので、1以上n未満の数なんてどうかけあわせても、nの倍数は発生しません。例えば、n=7 だとすると、1,2,3,4,5,6 をどうかけあわせても、7の倍数なんか作れるわけないです。7は素数、孤高のプリンセス、7自身が因数に入らない限り、7の倍数は生まれないのです。それにひきかえ6（や6の倍数）なんかは自分より小さい2と3とかから作れちゃうけどね。
つーことは、r! (n-r)! は、しょせん n より小さいもののかけあわせなので、素数 n の倍数には、ならないです。
n! / ( r!(n-r)! )
の分子 n!は n で割り切れる。
上記のように分母 r! (n-r)!は n で割り切れない。
なので、この分数は、実際には割り切れてある整数になるわけだが、その整数は n で割り切れる（分子が n の倍数だから、分母の因数に n が入ってない限り、分子を分母で割った結果には、もともと分子にあった n という因子が残っているので）。二項展開の係数にあらわれる
nCr = n! / ( r!(n-r)! )
は、もしも n が素数だったなら、n=0 と n=r の場合をのぞいて、ことごとく n で割り切れる。
だから、素数 n に対する (a + b)n を展開すると、両端に出る an と bn は別として、そのほかのまんなかにわらわら出てくる項は、ぜーんぶ n で割り切れる――こいつらは n を法として≡0 な連中、いかにややこしい形をしてようが実際に計算してやるまでもなく瞬殺できるザコキャラっす。
(a + b)n ≡ an + 0 + 0 + ... + 0 + bn (mod n)
すなわち、
(a + b)n ≡ an + bn (mod n)
ここまで来たらフェルマーの定理を手に入れたも同然でしょう。
証明を完成させるために、任意の素数 p に対して成り立つことが分かった式:
(a + b)p ≡ ap + bp (mod p)
にて、a=1, b=1 としてみます。
(1 + 1)p ≡ 1p + 1p (mod p)
左辺は 2p、右辺は1なんか何乗しても1なので、1+1=2、つまり
2p ≡ 2 (mod p)
これでフェルマーの小定理は下の数が2について証明されました。あとは a を1ずつ増加させながら数学的帰納法で楽勝です。
3p = (2 + 1)p ≡ 2p + 1p (mod p)
右辺の 2p が≡2 なことは、既に分かっています。1pは1なんか何乗しても1だから1です。要するに、この右辺は2+1=3であり、3p ≡ 3 (mod p) が言えました。以下同様に、4=3+1の場合を考えると3の場合に帰着され、5を考えると4の場合に帰着され……となります。しめくくりとして、下の数が0のときを考えると、
0p ≡ 0 (mod p)
……こんなのはpが素数じゃなくても成り立ちます。0は何乗しようが0だし、何で割っても商は0余り0。
以上によって、次の定理が得られました。
p が素数なら、任意の自然数 a について、
ap ≡ a (mod p)
実用上、この定理は、両辺を a で割った形で参照されることが多いです。ただし、a で割ることがゆるされるためには、a と p が互いに素でなければいけません。法pで割った余りを考えているのだから、法である p と1以外の公約数を持つような（pとなれあった秘密の関係のある）数で割ったら、余りの計算が狂って≡が成り立たなくなってしまうからです。通常の等号 = の等式についても0で割ることは許されませんが、それと同じように合同式の場合は、法となれあった数で割ることは許されません。互いに素である「無関係」な数でなら割って良いです。（RSA暗号についての解説で、秘密の指数βを求めるとき互いに素であることを確認したりしてたのは、この点と関係あります。）フェルマーの定理の場合、この制限は、実際には難しい問題じゃありません。p は素数なので「pと互いに素でないa」というのは要するに、aがpの倍数でなければ良いわけです（pの倍数ならpを法として≡0だから、要はゼロで割ってはいけません！という当たり前のこと）――そのような特殊な場合を除けば、上の定理は次のようにも書けます（単に両辺を a で割っただけ）。
p が素数なら、pと互いに素である任意の自然数 a について、
ap-1 ≡ 1 (mod p)
この定理の意味は――「どんな自然数でもp-1回かけあわせてpで割ると余りは1だ」ということ。（ただし、pは素数で、かけあわせる自然数とは互いに素。）以下の実例をみれば、だんだん納得がいくと思います。
でたらめな数――例えば123という数と素数7を考えると、「123を6回かけあわせて7で割ったら余りは1」ということが、実際に計算しなくても予言できるわけです。実際に計算すれば、
1236 = 3 4628 2599 1689 = 4946 8942 7384×7 + 1
てなわけで、フェルマーの定理の通りです。さらに、定理の両辺から1を引くと、またおもしろいことが出てきます。
ap-1 - 1 ≡ 0 (mod p)
あるいは、同じことですが、1ずらして、n+1が素数のとき、
an - 1 ≡ 0 (mod n+1)
例えば、
210-1 = 1024-1 = 1023
なんてのは、ちょっと素数みたいな顔をしてますが、1023は素数でしょうか？ あいにく10に1をたした11が素数なので、210-1 = 1023 は11で割れてしまいます。1023=11×93。合成数なのです。
316-1 = 43046720
この4304万6720という数は指数の16に1たした17で割り切れるはずです。実際、17×2532160です。
10012-1 = 9999 9999 9999 9999 9999 9999
この9が24個ならんだでかい数は13で割り切れる……はずです。指数の12に1たした13が素数ですからね。実際、
999999999999999999999999 = 76923076923076923076923×13
フェルマーの定理は、「pを法とする世界で考えると、どんな数もp乗すれば自分自身に戻る」というようなことを意味しています。例えば13を法とした世界では、3の13乗は3自身と合同、4の13乗は4自身と合同、5の13乗は5自身と合同……
313 = 1594323 → 13で割ると余り3
413 = 67108864 → 13で割ると余り4
513 = 1220703125 → 13で割ると余り5
...
上の各行の左端には3とか4とか5があって、右端には、ふたたびその左端の数が現れてます。このことを公開鍵暗号系のイメージと重ねると、エンクリプト変換とデクリプト変換の合成写像がちょうど上の計算になるようにエンクリプトとデクリプトをうまく定義すると、受信者は暗号化された文章をもとの文章に復元できることになるでしょう……あくまでイメージ的な説明であり、予備知識がないと、この説明では、かえって分かりにくと思います。詳しくは「高校数学で遊ぶ公開鍵暗号RSA」以下の一連の記事をみていただくとして、この計算は、「もとに戻ることが保証されている」ってところがミソです。いくら解読が難しい暗号文を作っても元に戻せなければだれにも読めない無意味な暗号文になってしまいますからね。
それはそれとして、aをp乗するとaに戻るってことは、p-1乗した時点での値は1と合同になっているわけです。p-1乗で1と合同なので、もういっかいaをかけるとaと合同になるってわけです。例えば、
312 = 531441 → 13で割ると余り1
412 = 16777216 → 13で割ると余り1
512 = 244140625 → 13で割ると余り1
...
どんな数でもp-1乗すると1と合同になるわけです。それがフェルマーの小定理の意味です。再掲すると……
p が素数なら、pと互いに素である任意の自然数 a について、
ap-1 ≡ 1 (mod p)
ところで、p-1乗すると≡1になるのは分かったとして、p-1回までかけて初めて≡1になるものなのでしょうか？ 例えば、13で割ったあまりというのは、0〜12の13通りがあるわけですけど、どんな数にせよ12乗したら余りが1になるのはそれとして、12乗よりもっと小さいべき乗で≡1になる可能性はないのでしょうか。可能性がないどころか、おおありです。そうなってしまうことのほうが多いです。13を法として、3で調べてみましょう:
31 = 3 → 13で割ると余り3
32 = 9 → 13で割ると余り9
33 = 27 → 13で割ると余り1
34 = 81 → 13で割ると余り3
35 = 243 → 13で割ると余り9
36 = 729 → 13で割ると余り1
37 = 2187 → 13で割ると余り3
38 = 6561 → 13で割ると余り9
39 = 19683 → 13で割ると余り1
310 = 59049 → 13で割ると余り3
311 = 177147 → 13で割ると余り9
312 = 531441 → 13で割ると余り1
ごらんのように、3乗した時点ですでに≡1です。1になってしまえば、それに元の数をかけると2乗のときと同じ話になって、以下同じパターンのループになります。3について、≡1になる最小指数は3です。このような最小指数は、必ずp-1の約数になります。きっちり整数回ループしてp-1の地点で≡1で着地するためには、ループの周期はp-1の約数じゃなければならないからです。つまり「≡1になる最小指数がp-1の約数だ」というのはフェルマーの定理の系です。
そんなことはどうでもいいのですが、逆に、p-1乗して初めて≡1になるようなケースもあるのでしょうか。4でやったらどうでしょう？
41 = 4 → 13で割ると余り4
42 = 16 → 13で割ると余り3
43 = 64 → 13で割ると余り12
44 = 256 → 13で割ると余り9
45 = 1024 → 13で割ると余り10
46 = 4096 → 13で割ると余り1
47 = 16384 → 13で割ると余り4
48 = 65536 → 13で割ると余り3
49 = 262144 → 13で割ると余り12
410 = 1048576 → 13で割ると余り9
411 = 4194304 → 13で割ると余り10
412 = 16777216 → 13で割ると余り1
残念ながら、p-1=12にいたる道の中間地点の6乗ですでに1になって、ループしてしまいます。
13を法としたときの2は、もっと良い性質を持っています:
21 = 2 → 13で割ると余り2
22 = 4 → 13で割ると余り4
23 = 8 → 13で割ると余り8
24 = 16 → 13で割ると余り3
25 = 32 → 13で割ると余り6
26 = 64 → 13で割ると余り12
27 = 128 → 13で割ると余り11
28 = 256 → 13で割ると余り9
29 = 512 → 13で割ると余り5
210 = 1024 → 13で割ると余り10
211 = 2048 → 13で割ると余り7
212 = 4096 → 13で割ると余り1
ごらんのように、1〜12乗するあいだに1〜12のそれぞれに合同な数がもれなく重複なくちょうど1回ずつ現れました。このような性質を持つ2は、13を法とする原始根である、と言われます。原始根が1個あれば、それひとつを出発点として掛け算を繰り返すことで（自乗、三乗……） 1, 2, ... , p-1 を生成することができます。原始根をめぐっては、おもしろい性質がいろいろあります。
実際の計算の話としては、13を法としてp-1=12だとすると、6乗した時点で≡1にならなければ、その時点で原始根だと分かります。すでに説明したように、≡1となる最小指数は12の約数なので6じゃないとしたら、もう12まで可能性は無いわけです。
そして、法が素数の原始根の場合、まんなかの (p-1)/2 乗においては≡-1です。うえの例では、26≡12≡-1となっています。
どうしてそうなるか。
p-1乗したら≡1になることはフェルマーの定理から確定してます。ってことは……半分の (p-1)/2 乗のときは「2乗すると1になる数」じゃなきゃいけないってことです。2乗すると1になる数の有力候補は1自身ですが、いま考えてるのは原始根だから、(p-1)乗して初めて1になるのであって、(p-1)/2 乗の現段階では ≢ 1（1と不合同）。で、1じゃない数で二乗すると1になる数といえば、つまり -1 です
（このことは厳密には証明を必要としますが、法が素数であるときは成り立つ）。
26 ≡ -1
1 ≡ 212 = (26)2 ≡ (-1)2
これは何となく……
"√1 = -1"
のような感じです……。
原始根2を「
24 ≡ 3
ということは……
"log23 = 4 (mod 13)"
のような離散対数のようなものを考えることもできるでしょう……たとえば……この世界において、3と6の積を求めたいとしましょう。上の表を「対数表」だと思うと、
"log23 = 4 (mod 13)"
"log26 = 5 (mod 13)"
なので、掛け算のかわりに、「対数」の足し算をして、4+5=9
29 ≡ 5
このようにして、3と6の積がこの世界では5であることを知ることができます。直接、3×6=18≡5（18を13で割ると余り5）と計算すると、たしかに一致します。いまやった計算は、104=10000と105=100000の積を求めるとき、実際に掛け算を行うことなく4+5=9であることから答は109だ、と計算するのと似ています。上記くらいの大きさの数では、このような「指数・対数」の計算が実用上べんりということはありませんが、こういうことができる、ってこと自体がちょっとおもしろい。
どのような素数に対しても、それを法とする原始根は1つ以上存在します。もちろん、このことは証明を必要とします。一般に、与えられた素数の最小原始根を求めるのは（手動でやるのは）面倒です。プログラミングをなさるかたは「原始根の表を作るスクリプト」を書いてみるとおもしろいかもしれません。
Note: この記事や関連するほかの記事では、「剰余類」と「余りの整数」をわざとあいまいに同一視しています。例えば、13で割ったときの余りで自然数を0,1,2,...,12の13グループに分類できる、という話では――とくに群論的な議論では――演算子の対象となる要素は本当は整数でなく抽象的な「類」です。類を「点化」して二項演算を入れているわけです。8+9≡4を厳密にいうと「8を含む類」と「9を含む類」に演算+をほどこした結果は「4を含む類」だ、ということですし、12≡-1を厳密にいうと「12を含む類」と「-1を含む類」は同じ要素の別名だ、ということです。
