このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

目次

はじめに

 例えばp=7(素数)として、a=1からp-1までの整数について、mod pでべき乗(何回も同じ数値で掛け算していくこと)して、観察してみる。その結果を表にまとめると次のようになる。

a123456
a1123456
a2142241
a3116166
a4124421
a5145236
a6111111
a7123456

 まず、表の見方を説明する。
 1行目はaの1〜6(=p-1=7-1)の値になり、縦にその値をどんどん掛けていくことになる。あくまでmod 7で考えていくので、すべての数値は6以下の値になっている。
 a6(p-1乗)の行でaの値に限らず、すべてが1になっていることに注目して欲しい。

 次に、pが合成数のときを考えてみる。pといったら普通素数(prime)を意味 してしまうので、ここでは合成数であることを意味するためにhとしておいた。例えば、合成数h=8として、mod hでべき乗して、観察してみる。

a1234567
a11234567
a21410141
a31030507
a41010101
a51030507
a61010101
a71030507
a81010101

 pが素数のときと異なり不規則になっていることがわかる。合成数の表では0が登場していることがわかる。一度0が登場してしまうと、列のそれ以降はすべて0になってしまう。0が登場しているので、a7(h-1乗)の行で、aの値はすべて1になることはありえない。

 以上の数値実験の結果によると、p=7の場合には、p-1乗のときに必ず1になることがわかった。この事実はpが素数であるときに一般的に成り立つ。これこそがフェルマーの小定理である。詳細は次の項で解説する。

フェルマーの小定理

[定理]フェルマーの小定理
p:素数、(a,p)=1とする。このとき、次が成り立つ。
a^{p-1}~\equiv~1~\,~(mod~\,~p)

[証明]pは素数なので、1≦i≦pとすれば、次の2項係数はi<pのとき分母がpで割り切れない。

_p~C_i~=~\frac{p(p-1)~\cdots~(p-i+1)}{1~\cdot~2~\cdots~i}

 よって、p~|~_p~C_iとなる(i=1,2,…,p-1)。なお、_p~C_0=1,~\,~_p~C_{p}=1である。

 ここで、定理はaに関する帰納法で証明される。

[1]a=1のとき、自明に成り立つ。

[2]a=k-1のとき、定理が成り立つと仮定する。

(k-1)^{p-1}~\equiv~1~(mod~p)

 よって、両辺にk-1を掛けると、次が成り立つ。

(k-1)^p~\equiv~k-1~(~mod~p~)

 このとき、a=kのとき定理が成り立つことを主張したい。

a^p
=~((a-1)+1)^p
=(a-1)^p~+~_p~C_1~(a-1)^{p-1}~+~_p~C_2~(a-1)^{p-2}~+~\cdots~+~_p~C_{p-1}~(a-1)~+~1
\equiv~(a-1)+1~\,~(mod~\,~p)
=a □

[別明]mod pの既約代表系は{1,2,…,p-1}である。これを(*)とする。また、(a,p)=1であるaを(*)の各項に掛けると、{1・a,2・a,…,(p-1)・a}になる。これを(**)とする。

 (*)(**)は全体としてmod pで一致しているから(これは定理として存在する)、全部の積もmod pで合同である。

1~\cdot~2~\cdot~(p-1)~\equiv~(1a)~\cdot~(2a)~\cdots~((p-1)a)~\,~(mod~\,~p)
(p-1)!~\equiv~(p-1)!~\cdot~a^{p-1}
1~\equiv~a^{p-1}~\,~(mod~\,~p) (∵((p-1)!,p)だから両辺から(p-1)!を割ることができる) □

[別証](ディリクレの証明)

[定理]「pを素数、pはaを割り切らないとする。
[1]x2≡aに解がない場合、a^{\frac{p-1}{2}}~\equiv~1
[2]x2≡aに解がある場合、a^{\frac{p-1}{2}}~\equiv~-1」において、両辺を2乗すると、フェルマーの小定理そのものである。 □

 フェルマーの小定理の(a,p)=1という条件のところを書き換えて、既約剰余類の要素と考えてもよい。

[系]
p:素数
a~\in~Z_p^*=\{1,2,\cdots,p-1|(a,p)=1\}
とする。このとき、次が成り立つ。
\forall~a;~a^{p-1}~\equiv~1~\,(mod~\,~p)

[系]
p|aでないならば、a^{p-1}~\equiv~1~\,~(mod~\,~p)

フェルマーの小定理を用いてべき乗計算

 フェルマーの小定理を使うと、mod pのべき乗計算を楽にできる。

[例]

x~\equiv~123^{45}~\,~(mod~\,~13)
\equiv~6^{145}~\,~(mod~\,~13) (∵123≡6 (mod 13))
=6^{12~\cdot~3+9} (∵フェルマーの小定理を使いたいため、12(=13-1)で累乗を割っておく)
=(6^{12})^{3}~\cdot~6^9
\equiv~1^3~\cdot~6^9
=6^9
\equiv~5~\,~(mod~\,~13) ◇

[例]1^2~+~2^2~+~\cdots~+~99^2は3で割り切れることを示す。

[1](a,3)=1の場合

 フェルマーの小定理より、a^2~\equiv~1~\,~(mod~\,~3)

 1〜99の間で3で割り切れない数の個数は、次のように計算でき、66個ある。ただし、[ ]はfloor functionである。

99-[\frac{99}{3}]=99-33=66

 1が66個あるので合計は66だが、mod 3の世界なので、0になる。

[2](a,3)≠1の場合

 [1]の残りの数(3で割り切れる数)たちは、{3,6,9,…,99}の33個ある。この33個の数の合計は次のように計算できる。

\sum_{i=1}^{33}~{3i}=3~\cdot~\sum_{i=1}^{33}~{i}~=~3~\cdot~\frac{33(33+1)}{2}=~3~\cdot~33~\cdot~17~\equiv~0~\,~(mod~\,~3)

 従って、[1][2]より、題意が成り立つ。 ◇

フェルマーの小定理の拡張

[定理]
p:素数とする。このとき次が成り立つ。
a^p~\equiv~a~\,~(mod~\,~p)

[証明]フェルマーの小定理より、a^{p-1}~\equiv~1~\,~(mod~\,~p)が成り立つ。

 合同式では掛け算可能なので、両辺にaを掛けると、「a^{p-1}~\equiv~1~\,~(mod~\,~p)」⇒「a^p~\equiv~a~\,~(mod~\,~p)」が成り立つ。 □

[補講]証明の逆が成り立つためには(a,p)=1という条件が必要。 ◇

[定理]
pが素数で、xがx≡1 mod p-1を満たすとき、任意の整数aに対して次が成り立つ。
a^x~\equiv~a~\,~\pmod{p}

[証明]

x~\equiv~1~\,~(mod~\,~p-1)
x-1~\equiv~0~\,~(mod~\,~p-1)
p-1~|~x-1
\exist~q~\in~Z;~x-1~=~q(p-1)

 a'~=~a~\,~(mod~\,~p)とする。

[1]a'~\in~Z_p^*のとき

a^x
\equiv~(a')^x~\,~(mod~\,~p)
\equiv~(a')^{q(p-1)+1}
\equiv~(a')^{q(p-1)}~\times~a'
\equiv~a' (∵フェルマーの小定理)
=~a

[2]a'~\not{\in}~Z_p^*、即ちa'=0のとき

 「a'~\equiv~0~\,~(mod~\,~p)」かつ「(a')^x~\equiv~0~\,~(mod~\,~p)」より、0のところで繋げれば、(a')^x~\equiv~a'~\,~(mod~\,~p)が成り立つ。 □

参考文献

  • 『なっとくするオイラーとフェルマー』