Fussy's Diary

明後日は「秋分の日」ですが、明日も休みという方も多いのではないでしょうか。そうすると 4 連休ですね。

今回は「フェルマーの小定理」の証明方法を紹介したいと思います。もちろん自力で解いたわけではなく「はじめての数論 (ISBN 978-4-89471-421-2)」の内容そのままです。

前提知識としてまずは「合同式」を説明しておきます。

a - b が m で割り切れるとき、a は m を法として b に合同であるといい、

a ≡ b ( mod m )

で表します。これを「合同式」といいます。合同式では以下の式が成り立つので、フェルマーの小定理の証明でこれらを利用します。

a ≡ b ( mod m )
c ≡ d ( mod m )

ならば

a・c ≡ b・d ( mod m )

an ≡ bn ( mod m ) で n と m が互いに素なら a ≡ b ( mod m )

-----------------------------------------------------------------------------
フェルマーの小定理

p を素数、a を p と互いに素な整数とするとき、

a^p-1 ≡ 1 ( mod p )

が成り立つ。
-----------------------------------------------------------------------------

(証明)

p - 1 個の整数 a, 2a, 3a, ... ( p - 1 )a を p で割ったときの剰余を考えます。その中の任意の二つの整数 ja, ka ( 但し 0 < k ≤ j < p ) が

ja ≡ ka ( mod p )

だとすると、( j - k )a は p で割り切れることになります。しかし a は p と互いに素なので、j - k が p で割り切れることになり、0 ≤ j - k < p なので j - k = 0 すなわち j = k であることになります。よって、a, 2a, 3a, ... ( p - 1 )a を p で割った時の剰余は全て異なることになります。ところが、これらの整数は p - 1 個あり、p で割った剰余も 1 から p - 1 までの p - 1 個なので、全てが相異なるためには 1 から p - 1 までの数を必ず含む必要があります。つまり、a, 2a, 3a, ... ( p - 1 )a を p で割った剰余は適当に順番を入れ替えることで 1 から p - 1 までの数となります。よって、

a・2a・3a・...・( p - 1 )a ≡ 1・2・3・...・( p - 1 ) ( mod p )

が成り立ちます。左辺は a^p-1( p - 1 )! であり、右辺は ( p - 1 )! です。( p - 1 )! は p と互いに素なので、両辺を ( p - 1 )! で割れば

a^p-1 ≡ 1 ( mod p )

となって、フェルマーの小定理が証明されました。