フェルマーの小定理
こんにちは。今回はフェルマーの小定理を取り上げます。本当は暗号について書きたいのですが、数学的な背景が必要になるため整理しておく必要があるためです。と書きながらも、どのように積み上げたらよいかを、私は十分に整理しきれていないため材料となるものを並べて、材料が揃ったところで俯瞰していこうと考えています。
余りと累乗の関係
数学では、「定理 → 証明 → 例題 → 演習」というような流れが多いのですが、あえて「試行錯誤 → 発見 → 定理 → 証明」の流れで進めていきます。
フェルマーの小定理は累乗と剰余について成り立つ関係を定理としています（後述）。そこで累乗と剰余の関係について実際に計算して何か見つかるか確かめてみようと思います。
累乗の計算は大きな値になりがちなので、ちょっとだけ工夫をします。
\(n=qm+r(0 \leq r \lt m)\)とします。ここで、整数\(n\)を整数\(m\)で割ったとき、\(q\)は商、\(r\)は余り\((q,rは整数)\)です。このとき
\(n^2 \equiv (qm+r) \equiv (qm)^2 + 2qmr +r^2 \equiv r^2 (\bmod m)\)
\(n^3 \equiv (qm+r) \equiv (qm)^3 + 3(qm)^2r+3(qm)r^2 +r^3 \equiv r^3 (\bmod m)\)
\( \cdots \)
と余りの累乗だけ考えれば十分です。整数\(n\)の累乗を\(m\)で割ったときの余りを考えるとき、\(0 , 1, \cdots , m-1 \)の累乗を考えれば十分です。
次に何乗まで考えればよいか考えます。整数\(m\)で割ったときの余りは、\(0 , 1, \cdots , m-1 \)の\(m\)個のいずれかになります。\(n^0,n^1,n^2,\cdots,n^{m-1},n^m\)までで\(m+1\)個の数があります。ここで鳩ノ巣原理を使います。巣の数にあたる余りになりうる値が\(m\)個、鳩にあたる累乗の値は\(n^m\)までで\(m+1\)個。鳩の数が巣の数より多いので、いずれか1つ以上の巣に鳩が２羽以上入っているはずです。話を戻すと、\(n^0,n^1,n^2,\cdots,n^{m-1},n^m\)まで余りが同じになることが確実です。ちょうど巣の数と鳩の数が同じになる\(n^0,n^1,n^2,\cdots,n^{m-1}\)まで求めて余りがどうなっているか調べてみます。
調べるためのプログラムは
for m in range(1,20):
print('mod {} 指数'.format(m))
print( ' |', end='')
for p in range(m):
print( '{0:2d}'.format( p ) , end=' ' )
print()
print( '---+', end='' )
for p in range(m):
print( '---', end='')
print()
for n in range(m):
print( '{0:2d} |'.format(n), end='' )
r = 1
for p in range(m):
print( '{0:2d}'.format( r ) , end=' ' )
r = (r*n) % m
print()
print( '↑底\n\n' )
きれいでないプログラムですみません。実行結果は次の通りです。
mod 1 指数
| 0
---+---
0 | 1
↑底
mod 2 指数
| 0 1
---+------
0 | 1 0
1 | 1 1
↑底
mod 3 指数
| 0 1 2
---+---------
0 | 1 0 0
1 | 1 1 1
2 | 1 2 1
↑底
mod 4 指数
| 0 1 2 3
---+------------
0 | 1 0 0 0
1 | 1 1 1 1
2 | 1 2 0 0
3 | 1 3 1 3
↑底
mod 5 指数
| 0 1 2 3 4
---+---------------
0 | 1 0 0 0 0
1 | 1 1 1 1 1
2 | 1 2 4 3 1
3 | 1 3 4 2 1
4 | 1 4 1 4 1
↑底
mod 6 指数
| 0 1 2 3 4 5
---+------------------
0 | 1 0 0 0 0 0
1 | 1 1 1 1 1 1
2 | 1 2 4 2 4 2
3 | 1 3 3 3 3 3
4 | 1 4 4 4 4 4
5 | 1 5 1 5 1 5
↑底
mod 7 指数
| 0 1 2 3 4 5 6
---+---------------------
0 | 1 0 0 0 0 0 0
1 | 1 1 1 1 1 1 1
2 | 1 2 4 1 2 4 1
3 | 1 3 2 6 4 5 1
4 | 1 4 2 1 4 2 1
5 | 1 5 4 6 2 3 1
6 | 1 6 1 6 1 6 1
↑底
mod 8 指数
| 0 1 2 3 4 5 6 7
---+------------------------
0 | 1 0 0 0 0 0 0 0
1 | 1 1 1 1 1 1 1 1
2 | 1 2 4 0 0 0 0 0
3 | 1 3 1 3 1 3 1 3
4 | 1 4 0 0 0 0 0 0
5 | 1 5 1 5 1 5 1 5
6 | 1 6 4 0 0 0 0 0
7 | 1 7 1 7 1 7 1 7
↑底
mod 9 指数
| 0 1 2 3 4 5 6 7 8
---+---------------------------
0 | 1 0 0 0 0 0 0 0 0
1 | 1 1 1 1 1 1 1 1 1
2 | 1 2 4 8 7 5 1 2 4
3 | 1 3 0 0 0 0 0 0 0
4 | 1 4 7 1 4 7 1 4 7
5 | 1 5 7 8 4 2 1 5 7
6 | 1 6 0 0 0 0 0 0 0
7 | 1 7 4 1 7 4 1 7 4
8 | 1 8 1 8 1 8 1 8 1
↑底
mod 10 指数
| 0 1 2 3 4 5 6 7 8 9
---+------------------------------
0 | 1 0 0 0 0 0 0 0 0 0
1 | 1 1 1 1 1 1 1 1 1 1
2 | 1 2 4 8 6 2 4 8 6 2
3 | 1 3 9 7 1 3 9 7 1 3
4 | 1 4 6 4 6 4 6 4 6 4
5 | 1 5 5 5 5 5 5 5 5 5
6 | 1 6 6 6 6 6 6 6 6 6
7 | 1 7 9 3 1 7 9 3 1 7
8 | 1 8 4 2 6 8 4 2 6 8
9 | 1 9 1 9 1 9 1 9 1 9
↑底
mod 11 指数
| 0 1 2 3 4 5 6 7 8 9 10
---+---------------------------------
0 | 1 0 0 0 0 0 0 0 0 0 0
1 | 1 1 1 1 1 1 1 1 1 1 1
2 | 1 2 4 8 5 10 9 7 3 6 1
3 | 1 3 9 5 4 1 3 9 5 4 1
4 | 1 4 5 9 3 1 4 5 9 3 1
5 | 1 5 3 4 9 1 5 3 4 9 1
6 | 1 6 3 7 9 10 5 8 4 2 1
7 | 1 7 5 2 3 10 4 6 9 8 1
8 | 1 8 9 6 4 10 3 2 5 7 1
9 | 1 9 4 3 5 1 9 4 3 5 1
10 | 1 10 1 10 1 10 1 10 1 10 1
↑底
mod 12 指数
| 0 1 2 3 4 5 6 7 8 9 10 11
---+------------------------------------
0 | 1 0 0 0 0 0 0 0 0 0 0 0
1 | 1 1 1 1 1 1 1 1 1 1 1 1
2 | 1 2 4 8 4 8 4 8 4 8 4 8
3 | 1 3 9 3 9 3 9 3 9 3 9 3
4 | 1 4 4 4 4 4 4 4 4 4 4 4
5 | 1 5 1 5 1 5 1 5 1 5 1 5
6 | 1 6 0 0 0 0 0 0 0 0 0 0
7 | 1 7 1 7 1 7 1 7 1 7 1 7
8 | 1 8 4 8 4 8 4 8 4 8 4 8
9 | 1 9 9 9 9 9 9 9 9 9 9 9
10 | 1 10 4 4 4 4 4 4 4 4 4 4
11 | 1 11 1 11 1 11 1 11 1 11 1 11
↑底
mod 13 指数
| 0 1 2 3 4 5 6 7 8 9 10 11 12
---+---------------------------------------
0 | 1 0 0 0 0 0 0 0 0 0 0 0 0
1 | 1 1 1 1 1 1 1 1 1 1 1 1 1
2 | 1 2 4 8 3 6 12 11 9 5 10 7 1
3 | 1 3 9 1 3 9 1 3 9 1 3 9 1
4 | 1 4 3 12 9 10 1 4 3 12 9 10 1
5 | 1 5 12 8 1 5 12 8 1 5 12 8 1
6 | 1 6 10 8 9 2 12 7 3 5 4 11 1
7 | 1 7 10 5 9 11 12 6 3 8 4 2 1
8 | 1 8 12 5 1 8 12 5 1 8 12 5 1
9 | 1 9 3 1 9 3 1 9 3 1 9 3 1
10 | 1 10 9 12 3 4 1 10 9 12 3 4 1
11 | 1 11 4 5 3 7 12 2 9 8 10 6 1
12 | 1 12 1 12 1 12 1 12 1 12 1 12 1
↑底
mod 14 指数
| 0 1 2 3 4 5 6 7 8 9 10 11 12 13
---+------------------------------------------
0 | 1 0 0 0 0 0 0 0 0 0 0 0 0 0
1 | 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 | 1 2 4 8 2 4 8 2 4 8 2 4 8 2
3 | 1 3 9 13 11 5 1 3 9 13 11 5 1 3
4 | 1 4 2 8 4 2 8 4 2 8 4 2 8 4
5 | 1 5 11 13 9 3 1 5 11 13 9 3 1 5
6 | 1 6 8 6 8 6 8 6 8 6 8 6 8 6
7 | 1 7 7 7 7 7 7 7 7 7 7 7 7 7
8 | 1 8 8 8 8 8 8 8 8 8 8 8 8 8
9 | 1 9 11 1 9 11 1 9 11 1 9 11 1 9
10 | 1 10 2 6 4 12 8 10 2 6 4 12 8 10
11 | 1 11 9 1 11 9 1 11 9 1 11 9 1 11
12 | 1 12 4 6 2 10 8 12 4 6 2 10 8 12
13 | 1 13 1 13 1 13 1 13 1 13 1 13 1 13
↑底
mod 15 指数
| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
---+---------------------------------------------
0 | 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 | 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 | 1 2 4 8 1 2 4 8 1 2 4 8 1 2 4
3 | 1 3 9 12 6 3 9 12 6 3 9 12 6 3 9
4 | 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1
5 | 1 5 10 5 10 5 10 5 10 5 10 5 10 5 10
6 | 1 6 6 6 6 6 6 6 6 6 6 6 6 6 6
7 | 1 7 4 13 1 7 4 13 1 7 4 13 1 7 4
8 | 1 8 4 2 1 8 4 2 1 8 4 2 1 8 4
9 | 1 9 6 9 6 9 6 9 6 9 6 9 6 9 6
10 | 1 10 10 10 10 10 10 10 10 10 10 10 10 10 10
11 | 1 11 1 11 1 11 1 11 1 11 1 11 1 11 1
12 | 1 12 9 3 6 12 9 3 6 12 9 3 6 12 9
13 | 1 13 4 7 1 13 4 7 1 13 4 7 1 13 4
14 | 1 14 1 14 1 14 1 14 1 14 1 14 1 14 1
↑底
mod 16 指数
| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
---+------------------------------------------------
0 | 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 | 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 | 1 2 4 8 0 0 0 0 0 0 0 0 0 0 0 0
3 | 1 3 9 11 1 3 9 11 1 3 9 11 1 3 9 11
4 | 1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5 | 1 5 9 13 1 5 9 13 1 5 9 13 1 5 9 13
6 | 1 6 4 8 0 0 0 0 0 0 0 0 0 0 0 0
7 | 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7
8 | 1 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 | 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9
10 | 1 10 4 8 0 0 0 0 0 0 0 0 0 0 0 0
11 | 1 11 9 3 1 11 9 3 1 11 9 3 1 11 9 3
12 | 1 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0
13 | 1 13 9 5 1 13 9 5 1 13 9 5 1 13 9 5
14 | 1 14 4 8 0 0 0 0 0 0 0 0 0 0 0 0
15 | 1 15 1 15 1 15 1 15 1 15 1 15 1 15 1 15
↑底
mod 17 指数
| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
---+---------------------------------------------------
0 | 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 | 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 | 1 2 4 8 16 15 13 9 1 2 4 8 16 15 13 9 1
3 | 1 3 9 10 13 5 15 11 16 14 8 7 4 12 2 6 1
4 | 1 4 16 13 1 4 16 13 1 4 16 13 1 4 16 13 1
5 | 1 5 8 6 13 14 2 10 16 12 9 11 4 3 15 7 1
6 | 1 6 2 12 4 7 8 14 16 11 15 5 13 10 9 3 1
7 | 1 7 15 3 4 11 9 12 16 10 2 14 13 6 8 5 1
8 | 1 8 13 2 16 9 4 15 1 8 13 2 16 9 4 15 1
9 | 1 9 13 15 16 8 4 2 1 9 13 15 16 8 4 2 1
10 | 1 10 15 14 4 6 9 5 16 7 2 3 13 11 8 12 1
11 | 1 11 2 5 4 10 8 3 16 6 15 12 13 7 9 14 1
12 | 1 12 8 11 13 3 2 7 16 5 9 6 4 14 15 10 1
13 | 1 13 16 4 1 13 16 4 1 13 16 4 1 13 16 4 1
14 | 1 14 9 7 13 12 15 6 16 3 8 10 4 5 2 11 1
15 | 1 15 4 9 16 2 13 8 1 15 4 9 16 2 13 8 1
16 | 1 16 1 16 1 16 1 16 1 16 1 16 1 16 1 16 1
↑底
mod 18 指数
| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
---+------------------------------------------------------
0 | 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 | 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 | 1 2 4 8 16 14 10 2 4 8 16 14 10 2 4 8 16 14
3 | 1 3 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9
4 | 1 4 16 10 4 16 10 4 16 10 4 16 10 4 16 10 4 16
5 | 1 5 7 17 13 11 1 5 7 17 13 11 1 5 7 17 13 11
6 | 1 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7 | 1 7 13 1 7 13 1 7 13 1 7 13 1 7 13 1 7 13
8 | 1 8 10 8 10 8 10 8 10 8 10 8 10 8 10 8 10 8
9 | 1 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9
10 | 1 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
11 | 1 11 13 17 7 5 1 11 13 17 7 5 1 11 13 17 7 5
12 | 1 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
13 | 1 13 7 1 13 7 1 13 7 1 13 7 1 13 7 1 13 7
14 | 1 14 16 8 4 2 10 14 16 8 4 2 10 14 16 8 4 2
15 | 1 15 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9
16 | 1 16 4 10 16 4 10 16 4 10 16 4 10 16 4 10 16 4
17 | 1 17 1 17 1 17 1 17 1 17 1 17 1 17 1 17 1 17
↑底
mod 19 指数
| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
---+---------------------------------------------------------
0 | 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 | 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 | 1 2 4 8 16 13 7 14 9 18 17 15 11 3 6 12 5 10 1
3 | 1 3 9 8 5 15 7 2 6 18 16 10 11 14 4 12 17 13 1
4 | 1 4 16 7 9 17 11 6 5 1 4 16 7 9 17 11 6 5 1
5 | 1 5 6 11 17 9 7 16 4 1 5 6 11 17 9 7 16 4 1
6 | 1 6 17 7 4 5 11 9 16 1 6 17 7 4 5 11 9 16 1
7 | 1 7 11 1 7 11 1 7 11 1 7 11 1 7 11 1 7 11 1
8 | 1 8 7 18 11 12 1 8 7 18 11 12 1 8 7 18 11 12 1
9 | 1 9 5 7 6 16 11 4 17 1 9 5 7 6 16 11 4 17 1
10 | 1 10 5 12 6 3 11 15 17 18 9 14 7 13 16 8 4 2 1
11 | 1 11 7 1 11 7 1 11 7 1 11 7 1 11 7 1 11 7 1
12 | 1 12 11 18 7 8 1 12 11 18 7 8 1 12 11 18 7 8 1
13 | 1 13 17 12 4 14 11 10 16 18 6 2 7 15 5 8 9 3 1
14 | 1 14 6 8 17 10 7 3 4 18 5 13 11 2 9 12 16 15 1
15 | 1 15 16 12 9 2 11 13 5 18 4 3 7 10 17 8 6 14 1
16 | 1 16 9 11 5 4 7 17 6 1 16 9 11 5 4 7 17 6 1
17 | 1 17 4 11 16 6 7 5 9 1 17 4 11 16 6 7 5 9 1
18 | 1 18 1 18 1 18 1 18 1 18 1 18 1 18 1 18 1 18 1
↑底
となります。ここで、\(m-1\)乗に注目すると値がほとんど\(1\)になっているものがあります。該当箇所だけ抽出してみます。
mod 2 指数
| 0 1
---+------
0 | 1 0
1 | 1 1
↑底
mod 3 指数
| 0 1 2
---+---------
0 | 1 0 0
1 | 1 1 1
2 | 1 2 1
↑底
mod 5 指数
| 0 1 2 3 4
---+---------------
0 | 1 0 0 0 0
1 | 1 1 1 1 1
2 | 1 2 4 3 1
3 | 1 3 4 2 1
4 | 1 4 1 4 1
↑底
mod 7 指数
| 0 1 2 3 4 5 6
---+---------------------
0 | 1 0 0 0 0 0 0
1 | 1 1 1 1 1 1 1
2 | 1 2 4 1 2 4 1
3 | 1 3 2 6 4 5 1
4 | 1 4 2 1 4 2 1
5 | 1 5 4 6 2 3 1
6 | 1 6 1 6 1 6 1
↑底
mod 11 指数
| 0 1 2 3 4 5 6 7 8 9 10
---+---------------------------------
0 | 1 0 0 0 0 0 0 0 0 0 0
1 | 1 1 1 1 1 1 1 1 1 1 1
2 | 1 2 4 8 5 10 9 7 3 6 1
3 | 1 3 9 5 4 1 3 9 5 4 1
4 | 1 4 5 9 3 1 4 5 9 3 1
5 | 1 5 3 4 9 1 5 3 4 9 1
6 | 1 6 3 7 9 10 5 8 4 2 1
7 | 1 7 5 2 3 10 4 6 9 8 1
8 | 1 8 9 6 4 10 3 2 5 7 1
9 | 1 9 4 3 5 1 9 4 3 5 1
10 | 1 10 1 10 1 10 1 10 1 10 1
↑底
mod 13 指数
| 0 1 2 3 4 5 6 7 8 9 10 11 12
---+---------------------------------------
0 | 1 0 0 0 0 0 0 0 0 0 0 0 0
1 | 1 1 1 1 1 1 1 1 1 1 1 1 1
2 | 1 2 4 8 3 6 12 11 9 5 10 7 1
3 | 1 3 9 1 3 9 1 3 9 1 3 9 1
4 | 1 4 3 12 9 10 1 4 3 12 9 10 1
5 | 1 5 12 8 1 5 12 8 1 5 12 8 1
6 | 1 6 10 8 9 2 12 7 3 5 4 11 1
7 | 1 7 10 5 9 11 12 6 3 8 4 2 1
8 | 1 8 12 5 1 8 12 5 1 8 12 5 1
9 | 1 9 3 1 9 3 1 9 3 1 9 3 1
10 | 1 10 9 12 3 4 1 10 9 12 3 4 1
11 | 1 11 4 5 3 7 12 2 9 8 10 6 1
12 | 1 12 1 12 1 12 1 12 1 12 1 12 1
↑底
mod 17 指数
| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
---+---------------------------------------------------
0 | 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 | 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 | 1 2 4 8 16 15 13 9 1 2 4 8 16 15 13 9 1
3 | 1 3 9 10 13 5 15 11 16 14 8 7 4 12 2 6 1
4 | 1 4 16 13 1 4 16 13 1 4 16 13 1 4 16 13 1
5 | 1 5 8 6 13 14 2 10 16 12 9 11 4 3 15 7 1
6 | 1 6 2 12 4 7 8 14 16 11 15 5 13 10 9 3 1
7 | 1 7 15 3 4 11 9 12 16 10 2 14 13 6 8 5 1
8 | 1 8 13 2 16 9 4 15 1 8 13 2 16 9 4 15 1
9 | 1 9 13 15 16 8 4 2 1 9 13 15 16 8 4 2 1
10 | 1 10 15 14 4 6 9 5 16 7 2 3 13 11 8 12 1
11 | 1 11 2 5 4 10 8 3 16 6 15 12 13 7 9 14 1
12 | 1 12 8 11 13 3 2 7 16 5 9 6 4 14 15 10 1
13 | 1 13 16 4 1 13 16 4 1 13 16 4 1 13 16 4 1
14 | 1 14 9 7 13 12 15 6 16 3 8 10 4 5 2 11 1
15 | 1 15 4 9 16 2 13 8 1 15 4 9 16 2 13 8 1
16 | 1 16 1 16 1 16 1 16 1 16 1 16 1 16 1 16 1
↑底
mod 19 指数
| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
---+---------------------------------------------------------
0 | 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 | 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 | 1 2 4 8 16 13 7 14 9 18 17 15 11 3 6 12 5 10 1
3 | 1 3 9 8 5 15 7 2 6 18 16 10 11 14 4 12 17 13 1
4 | 1 4 16 7 9 17 11 6 5 1 4 16 7 9 17 11 6 5 1
5 | 1 5 6 11 17 9 7 16 4 1 5 6 11 17 9 7 16 4 1
6 | 1 6 17 7 4 5 11 9 16 1 6 17 7 4 5 11 9 16 1
7 | 1 7 11 1 7 11 1 7 11 1 7 11 1 7 11 1 7 11 1
8 | 1 8 7 18 11 12 1 8 7 18 11 12 1 8 7 18 11 12 1
9 | 1 9 5 7 6 16 11 4 17 1 9 5 7 6 16 11 4 17 1
10 | 1 10 5 12 6 3 11 15 17 18 9 14 7 13 16 8 4 2 1
11 | 1 11 7 1 11 7 1 11 7 1 11 7 1 11 7 1 11 7 1
12 | 1 12 11 18 7 8 1 12 11 18 7 8 1 12 11 18 7 8 1
13 | 1 13 17 12 4 14 11 10 16 18 6 2 7 15 5 8 9 3 1
14 | 1 14 6 8 17 10 7 3 4 18 5 13 11 2 9 12 16 15 1
15 | 1 15 16 12 9 2 11 13 5 18 4 3 7 10 17 8 6 14 1
16 | 1 16 9 11 5 4 7 17 6 1 16 9 11 5 4 7 17 6 1
17 | 1 17 4 11 16 6 7 5 9 1 17 4 11 16 6 7 5 9 1
18 | 1 18 1 18 1 18 1 18 1 18 1 18 1 18 1 18 1 18 1
↑底
となっています。\(\bmod p\)の\(p\)が素数の場合に成り立っていそうです。
フェルマーの小定理
ここまでの計算から \[a^{p-1} \equiv 1 \bmod m(pは素数、a,pは互いに素)\]
が成り立ちそうと推測できます。これがフェルマーの小定理です。
証明は次になります。
\(a,p\)は互いに素であるときに、\(x \neq y\)とする。（\(1 \leq x,y \leq p-1\)）
このとき、\(ax \equiv ay \bmod p\)が成り立つ\(x,y\)が存在すると仮定すると
\(ax-by \equiv 0 \bmod p\)
\(a(x-y) \equiv 0 \bmod p\)
\(a,p\)は互いに素（\(a\)を\(p\)で割った余りは\(0\)にならない）なので
\(x-y \equiv 0 \bmod p\)
\(1 \leq x,y \leq p-1\)なので、\(x=y\)となり仮定と矛盾するので、\(a,2a,3a,\cdots,(p-1)a\)を\(p\)で割ったときの余りはすべて異なる値\(1,2,3,\cdots,p-1\)になります。そのことから
\(a^{p-1} \times (p-1)! \equiv (p-1)! \bmod p\)
となります。\(p\)は素数なので\((p-1)!\)と互いに素なので、両辺を\((p-1)!\)で割って
\(a^{p-1} \equiv 1 \bmod p\)
が得られます。
逆元を求める
フェルマーの小定理を変形すると
\(a^{p-2} \times a \equiv 1 \bmod p\)
となるので、\(a\)の逆元は\(a^{p-2} \bmod p\)により求められます。すなわち
\(a^{-1} \equiv a^{p-2} \bmod p\)
により求めることができます。
例えば、\(\bmod 11\)で\(5\)の逆元（\(5^{-1} \equiv 1 \bmod 11\)）を求めるには、\(5^{-1} \equiv 5^{11-2} \equiv 5^9 \bmod 11\)を求めればよいことになります。先ほどの表を見ると\(5^{-1} \equiv 5^9 \equiv 9 \bmod 11\)であることがわかります。
今回はこれでおしまい。それではまた。