1以上の整数であるmで割った余りの値を同一とみなす演算の世界では元の数はm-1個である。
gcd(a, m) = 1である数aの総数をオイラーの関数と呼ぶ。
小さい方からどのような数なのかみておく。
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となるから、
である。
フェルマーの小定理
