Pebble's Diary

プログラマーの作業メモ

オイラーの φ 関数 とフェルマーの小定理

1以上の整数であるmで割った余りの値を同一とみなす演算の世界では元の数はm-1個である。
gcd(a, m) = 1である数aの総数をオイラー \phi関数と呼ぶ。
小さい方からどのような数なのかみておく。
1: {1} -> 1
2: {1} -> 1
3: {1, 2} -> 1
4: {1, 3} -> 2 (2は除外)
5: {1, 2, 3, 4} -> 4
6: {1, 5 } -> 2 (2, 3, 4は除外)
7: {1, 2, 3, 4, 5, 6} -> 6
8: {1, 3, 5, 7} -> 4 (2, 4, 6は 除外)
9: {1, 2, 4, 5, 7, 8} -> 6 (3, 6は除外)

よく知られたように素数pの場合は{1, 2, …, p-1}が全てgcd(a, p) = 1となるから、
 \phi(p) = p-1
である。

フェルマーの小定理

 gcd(a, m) = 1 であれば、a ^ { \phi(m)} = 1\mod m