オイラーの定理(整数)

定義. \(n\)以下の 自然数 \(1,\cdots,n\) のうち, \(n\)と互いに素であるものの個数を \(\varphi(n)\)で表す.

定理(Euler). \(n\)を正の整数とし, \(a\)を\(n\)と互いに素な整数とする. このとき,次が成り立つ. $$ a^{\varphi(n)}\equiv 1 \ \mod n $$
注意 \(n\)が素数\(p\)なら, \(\varphi(p)=p-1\)なので, このとき, $$ a^{p-1}\equiv 1 \mod p $$ が成り立つ. これは, フェルマーの小定理 に他ならない.


PDF