フェルマーの小定理 | 簡単に理解できる例と厳密な証明
" フェルマーの小定理 “を簡単に理解して使うための具体例を知っておくと役に立つかと思います。
例を通じて親しみ、その後に厳密な証明を述べています。
証明の部分は、大学の代数学の入門的な内容へとつながっています。
そのため、大学数学で環や群に慣れるためのものとして、フェルマーの小定理に触れるのも良いかと思います。
まずは、シンプルな例を通じて、定理の内容を説明します。
フェルマーの小定理 :簡単に理解できる例
有名なフェルマーの名前が使われている定理なので、難しそうですが、具体的な例を通して定理の意味と使い方をすぐに理解できます。
知っておくと、役に立つ定理なので、シンプルな例を通じて押さえておくと良いかと思います。
【具体例】
整数 11 と素数 7 が与えられたとします。
11 と素数 7 の最大公約数は 1 となっています。
このとき、117-1 ÷ 7 を計算したときの余りは 1 となります。
与えられた整数と素数の最大公約数が 1 となっているときに、その整数を（素数－1）乗したものを、その素数で割ったときの余りが、必ず 1 となるということを意味している定理です。
ですので、（素数－1）乗をした整数を、その素数で割った余りに注目するときには、この定理を使うチャンスです。
ただし、与えられた整数と素数の最大公約数が 1 となっていないときには、反例が確認されているので、使うことができません。
反例の確認
他の例で、フェルマーの小定理を見る前に、最大公約数が 1 となっていないときの反例を述べておきます。
整数 6 と素数 3 が与えられたとします。
6 と 3 の最大公約数は 3 なので、最大公約数 1 という仮定条件を満たしていません。
実際に 63-1 を素数 3 で割ったときの余りを計算して、余りが 1 となっていないことを確認します。
63-1 ÷ 3 = 62 ÷ 3
= 36 ÷ 3 = 12 あまり 0
63-1 ÷ 3 は割り切れたので、余りが 0 となっています。定理の結論である余りが 1 ということになっていません。
このように、最大公約数が 1 という仮定を満たさないときに、成立しない反例があります。
フェルマーの小定理を使うときには、最大公約数が 1 となっているかということに注意です。
定理を使う練習
整数 2 と素数 5 が与えられたとします。
このとき、25-1 ÷ 5 の余りを求めてください。
慣れていると、即答ですが、フェルマーの小定理の仮定条件を満たしているかを確認するところから説明します。
2 と素数 5 の最大公約数は 1 となっています。そして、2 の指数は割る数となっている素数から 1 だけをマイナスしたものになっています。
確かに、フェルマーの小定理が使える状況なので、定理を適用すると、求める余りが 1 だということが分かります。
実際に計算して、本当に余りが 1 になっているのかを確かめてみます。
25-1 ÷ 5 = 24 ÷ 5 = 16 ÷ 5
16 ÷ 5 を計算すると、商が 3 で余りが 1 です。
確かにフェルマーの小定理の結論となっている余り 1 です。
【使い方まとめ】
与えられた整数と素数の最大公約数が 1 となっているときに、その整数を（素数－1）乗したものを、その素数で割ったときの余りが、必ず 1 となる。
この実質的な算数だけで、定理の意味と使い方が表せてしまうのが、フェルマーの小定理の良いところです。
難解な数式を用いずに、まずは扱いやすい例から。
さらに良いこととして、厳密な証明は、大学受験の整数分野の記述証明の練習になりますし、大学の代数学の入門的な内容にもつながります。
フェルマーの小定理 :厳密な証明
ここからは、フェルマーの小定理の証明について説明します。
高校数学の内容で証明するために、次の補題を使って命題を一つ導きます。
そして、その命題と補題を使って、フェルマーの小定理を証明するという流れです。
【補題】
整数 a を 0 ではなく整数 m との最大公約数が 1 だとする。
このとき、整数 x と y について、
ax ≡ ay ならば x ≡ y (mod m)
この補題は、余り-整数問題というブログ記事で証明をしています。
※ リンク先の記事の【命題 4】に当たります。
※ m を法として合同というのは、m で割ったときの余りが等しいということです。
この【補題】を使って、次の命題を導きます。
【命題】
正整数 a と b の最大公約数が 1 であるとする。
このとき、
a, 2a, 3a, … , (b -1)a, ba たちをそれぞれ b で割った余りは全て異なる。
＜証明＞
k と h を b 以下の自然数とし、k ≠ h だったと仮定します。
もし ka ≡ ha (mod b) とすると、a と b の最大公約数が 1 であることから、
【補題】より、k ≡ h (mod b)
よって、k – h = qb（q は整数） と表すことができます。
【k > h の場合】
b > k – h > 0 なので、正整数 b の倍数となっている非負整数で、b よりも小さいものは 0 しかないため、q = 0 でなければなりません。
しかし、このとき k = h となってしまい、
k ≠ h であったことに矛盾します。
よって、【k < h の場合】を考えることとなります。
k < h のとき、
h ≡ k (mod b), b > h – k > 0
ゆえに、同様に、
正整数 b の倍数となっている非負整数で、b よりも小さいものは 0 しかないので、h = k となってしまいます。
これは、 h > k に矛盾です。
以上より、背理法から k = h でなければなりません。
つまり、a, 2a, 3a, … , (b -1)a, ba たちをそれぞれ b で割った余りは全て異なるということになります。【証明完了】
b で割ったときの余りで、相異なるものが b 個出てきました。
高校の数学で有名な部屋割り論法が絡む内容になります。
今、証明に使った【補題】は、
合同方程式の解き方にも関係してきます。
ここを正確に使わないと、余りが等しいのか異なるのかの議論に支障が出てくるので、注意が必要な内容になります。
それでは、いよいよフェルマーの小定理を証明します。定理を合同式を使った形で述べておきます。
定理の証明
【フェルマーの小定理】
整数 z と素数 p の最大公約数が 1 とする。
このとき、zp-1 ≡ 1 (mod p)
zp-1 ≡ 1 (mod p) は、「zp-1 – 1 が p の倍数となっている」ということが定義ですが、zp-1 を p で割ったときの余りが 1 である」ということと同値です。
＜証明＞
z と p の最大公約数が 1 なので、【補題】から、a, 2a, … , (p -1)a を p で割った余りは全て異なります。
これら (p – 1) 個の余りは、1, 2, … , p -1 となっています。
※ どの余りが 1 や 2 かなどは不明ですが。
自然数 k について、ka を p で割ったときの余りを r(k) と置きます。
ただし、k = 1, 2, … , p -1 です。
p を法として、
a ≡ r(1), 2a ≡ r(2), … , (p -1)a ≡ r(p -1) となっています。
これらをすべて掛け合わせると、
合同式の性質から、
(p – 1)! × ap-1 ≡ r(1)r(2) … r(p – 1)
r(1), r(2), … , r(p – 1) は、
1, 2, … , p -1 という余りたちを適宜並び替えたものなので、すべて掛け合わせた値です。
そのため、
r(1)r(2) … r(p – 1) = (p – 1)! となります。
よって、(p – 1)! × ap-1 ≡ (p – 1)!
法としている p と (p – 1)! の最大公約数は 1 なので、【補題】より、ap-1 ≡ 1 (mod p)【証明完了】
この【補題】は、
合同式で割り算ができるかどうかについての基本となる大切な内容になります。
最後に、大学の数学の内容を使って、フェルマーの小定理を一般化したオイラーの定理について述べておきます。
フェルマーの小定理 :さらに一般化
この φ(n) はオイラーのファイ関数の値で、n 以下の自然数で n との最大公約数が 1 となっているものの個数を表しています。
有限群 G について、gm が G の単位元になる最小の自然数 m を 元 g の位数といいます。
ラグランジュの定理から、元の位数は |G| の約数となることが証明されます。
この群論の入門的な内容で学習する定理から、オイラーの定理が導かれます。
G として、(Z/nZ)× という剰余環 Z/nZ の乗法群を考えます。
n = 1 のときは、n との最大公約数が 1 となるのは a = 1 しかなく、φ(1) = 1 なので、成立します。
したがって、以下で、n ≧ 2 のときについて示します。
自然数 n と a の最大公約数が 1 であることから、a + nZ ∈ (Z/nZ)×
です。φ(n) = |(Z/nZ)×| であり、(Z/nZ)× は Z/nZ の乗法について有限群となっています。
乗法単位元は、1 + nZ です。元 a + nZ の位数は、φ(n) = |(Z/nZ)×| の約数ですから、指数が φ(n) だと必ず乗法単位元になります。
そのため、
1 + nZ
= (a + nZ)φ(n) = aφ(n) + nZ
よって、aφ(n) + nZ = 1 + nZ となります。
Z/nZ の元について、等しいということは、
aφ(n) － 1 が n で割り切れるということでした。このことを合同記号で表すと、
aφ(n) ≡ 1 (mod n) です。
これで、オイラーの定理が示せました。
このオイラーの定理は、先ほど示したフェルマーの小定理を一般化したものになります。
オイラーの定理は、2 以上の自然数について、(Z/nZ)× = φ(n) についての群論で示しました。
この n が素数 p のときが、フェルマーの小定理です。
φ(p) = p － 1 = (Z/nZ)× という特殊な場合となっています。
関連するブログ
今回のフェルマーの小定理の証明で、余りについて等しいのか異なるのかという議論をしました。
同じく余りに関連する連立合同式の定理で、中国剰余定理があります。
中国剰余定理も、定理の意味と使い方を算数の具体例で習得することができます。
知っておくと役に立ちますし、厳密な証明を理解することは、大学の数学への架け橋にもなってくれます。
また、フェルマーの小定理を極大イデアルの観点からも考察をすることができます。
素数 p について、剰余環 Z/pZ の議論と、Z において pZ が極大イデアルであるということが関連します。
それでは、これで今回のブログ記事を終了します。
読んで頂き、ありがとうございました。