例えばp=7(素数)として、a=1からp-1までの整数について、mod pでべき乗(何回も同じ数値で掛け算していくこと)して、観察してみる。その結果を表にまとめると次のようになる。
a | 1 | 2 | 3 | 4 | 5 | 6 |
a1 | 1 | 2 | 3 | 4 | 5 | 6 |
a2 | 1 | 4 | 2 | 2 | 4 | 1 |
a3 | 1 | 1 | 6 | 1 | 6 | 6 |
a4 | 1 | 2 | 4 | 4 | 2 | 1 |
a5 | 1 | 4 | 5 | 2 | 3 | 6 |
a6 | 1 | 1 | 1 | 1 | 1 | 1 |
a7 | 1 | 2 | 3 | 4 | 5 | 6 |
まず、表の見方を説明する。
1行目はaの1〜6(=p-1=7-1)の値になり、縦にその値をどんどん掛けていくことになる。あくまでmod 7で考えていくので、すべての数値は6以下の値になっている。
a6(p-1乗)の行でaの値に限らず、すべてが1になっていることに注目して欲しい。
次に、pが合成数のときを考えてみる。pといったら普通素数(prime)を意味 してしまうので、ここでは合成数であることを意味するためにhとしておいた。例えば、合成数h=8として、mod hでべき乗して、観察してみる。
a | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
a1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
a2 | 1 | 4 | 1 | 0 | 1 | 4 | 1 |
a3 | 1 | 0 | 3 | 0 | 5 | 0 | 7 |
a4 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
a5 | 1 | 0 | 3 | 0 | 5 | 0 | 7 |
a6 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
a7 | 1 | 0 | 3 | 0 | 5 | 0 | 7 |
a8 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
pが素数のときと異なり不規則になっていることがわかる。合成数の表では0が登場していることがわかる。一度0が登場してしまうと、列のそれ以降はすべて0になってしまう。0が登場しているので、a7(h-1乗)の行で、aの値はすべて1になることはありえない。
以上の数値実験の結果によると、p=7の場合には、p-1乗のときに必ず1になることがわかった。この事実はpが素数であるときに一般的に成り立つ。これこそがフェルマーの小定理である。詳細は次の項で解説する。
[定理]フェルマーの小定理
p:素数、(a,p)=1とする。このとき、次が成り立つ。
[証明]pは素数なので、1≦i≦pとすれば、次の2項係数はi<pのとき分母がpで割り切れない。
よって、となる(i=1,2,…,p-1)。なお、
である。
ここで、定理はaに関する帰納法で証明される。
[1]a=1のとき、自明に成り立つ。
[2]a=k-1のとき、定理が成り立つと仮定する。
よって、両辺にk-1を掛けると、次が成り立つ。
このとき、a=kのとき定理が成り立つことを主張したい。
□
[別明]mod pの既約代表系は{1,2,…,p-1}である。これを(*)とする。また、(a,p)=1であるaを(*)の各項に掛けると、{1・a,2・a,…,(p-1)・a}になる。これを(**)とする。
(*)(**)は全体としてmod pで一致しているから(これは定理として存在する)、全部の積もmod pで合同である。
∴ (∵((p-1)!,p)だから両辺から(p-1)!を割ることができる) □
[別証](ディリクレの証明)
[定理]「pを素数、pはaを割り切らないとする。
[1]x2≡aに解がない場合、
[2]x2≡aに解がある場合、」において、両辺を2乗すると、フェルマーの小定理そのものである。 □
フェルマーの小定理の(a,p)=1という条件のところを書き換えて、既約剰余類の要素と考えてもよい。
[系]
p:素数
とする。このとき、次が成り立つ。
[系]
p|aでないならば、
フェルマーの小定理を使うと、mod pのべき乗計算を楽にできる。
[例]
(∵123≡6 (mod 13))
(∵フェルマーの小定理を使いたいため、12(=13-1)で累乗を割っておく)
◇
[例]は3で割り切れることを示す。
[1](a,3)=1の場合
フェルマーの小定理より、
1〜99の間で3で割り切れない数の個数は、次のように計算でき、66個ある。ただし、[ ]はfloor functionである。
1が66個あるので合計は66だが、mod 3の世界なので、0になる。
[2](a,3)≠1の場合
[1]の残りの数(3で割り切れる数)たちは、{3,6,9,…,99}の33個ある。この33個の数の合計は次のように計算できる。
従って、[1][2]より、題意が成り立つ。 ◇
[定理]
p:素数とする。このとき次が成り立つ。
[証明]フェルマーの小定理より、が成り立つ。
合同式では掛け算可能なので、両辺にaを掛けると、「」⇒「
」が成り立つ。 □
[補講]証明の逆が成り立つためには(a,p)=1という条件が必要。 ◇
[定理]
pが素数で、xがx≡1 mod p-1を満たすとき、任意の整数aに対して次が成り立つ。
[証明]
とする。
[1]のとき
(∵フェルマーの小定理)
[2]、即ちa'=0のとき
「」かつ「
」より、0のところで繋げれば、
が成り立つ。 □