オイラーの定理 (数論)
nと互いに素なn以下の正の整数の集合を
A = { b 1 , b 2 , . . . , b φ ( n ) } {\displaystyle A=\{b_{1},b_{2},...,b_{\varphi (n)}\}} とする。
この要素のそれぞれにaを乗じた集合
B = { a b 1 , a b 2 , . . . , a b φ ( n ) } {\displaystyle B=\{ab_{1},ab_{2},...,ab_{\varphi (n)}\}}
を考えればaとnは互いに素だから、集合A,Bは法をnとしたときに一致し、当然その積も法nにおいて等しくなる。すなわちAの要素の積をPとすれば、
P ≡ a φ ( n ) P ( mod n ) {\displaystyle P\equiv a^{\varphi (n)}P{\pmod {n}}}
nとPは互いに素だから
a φ ( n ) ≡ 1 ( mod n ) {\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}} (証明終)