Security Akademeia

目次 †

目次
はじめに
フェルマーの小定理
フェルマーの小定理を用いてべき乗計算
フェルマーの小定理の拡張
参考文献

はじめに †

　例えば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とする。このとき、次が成り立つ。
$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)$ が成り立つ。　□

↑

参考文献 †

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

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

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

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

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

Top / フェルマーの小定理フェルマーの小定理