お知らせ

ただいま、シンタックスハイライターの設定を見直しております。
プログラムが見にくくなっているページがありますが、ご容赦ください。

フェルマーの小定理

数学

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

余りと累乗の関係

数学では、「定理 → 証明 → 例題 → 演習」というような流れが多いのですが、あえて「試行錯誤 → 発見 → 定理 → 証明」の流れで進めていきます。

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

累乗の計算は大きな値になりがちなので、ちょっとだけ工夫をします。

\(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つ以上の巣に鳩が2羽以上入っているはずです。話を戻すと、\(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\)であることがわかります。

今回はこれでおしまい。それではまた。

この記事を書いた人
春日井 優

高校で情報科という教科を担当しています。以前は数学科も担当していました。(今でも数学科の教員免許状は有効です。)プログラムを覚えたのは、「ゲームセンターあらし」という漫画のキャラクターがBASICを解説する「こんにちはマイコン」を読んだことがきっかけでした。

Posted by kasugai