# フェルマーの小定理

こんにちは。今回はフェルマーの小定理を取り上げます。本当は暗号について書きたいのですが、数学的な背景が必要になるため整理しておく必要があるためです。と書きながらも、どのように積み上げたらよいかを、私は十分に整理しきれていないため材料となるものを並べて、材料が揃ったところで俯瞰していこうと考えています。

## 余りと累乗の関係

フェルマーの小定理は累乗と剰余について成り立つ関係を定理としています（後述）。そこで累乗と剰余の関係について実際に計算して何か見つかるか確かめてみようと思います。

$$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$$の累乗を考えれば十分です。

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$$

により求めることができます。