오일러 정리
$a^{\varphi(n)}\equiv 1 \pmod{n}$ if $gcd(a,n)=1$ ($a$와 $n$이 서로소) $\varphi(n)$: $n$과 서로소인 $n$이하의 자연수의 갯수 증명 $Z_n^* = S = \{b_1, b_2, \cdots , b_{\varphi(n)}\}$ ($Z_n^*$은 양의 정수 n이하의 n과 서로소인 자연수 집합) $aS = \{ab_1, ab_2, \cdots , ab_{\varphi(n)}\}$ 일 때, S의 임의의 서로 다른 두 원소 $b_i$와 $b_j$ 는 n으로 나눈 나머지가 항상 다르다...(1) ($\because b_i, b_j$두 수의 차의 범위는 $0 < |b_i - b_j| \leq (n-2)$이다. 이 범위에서 $n$의 배수는 없다. 즉 $|b_..