오일러 정리

$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_i - b_j|$는 $n$의 배수가 아니다...(i) 그러므로 $(b_i\mod n) \neq (b_j\mod n)$이다)

그 나머지는 $b_i = b_i \mod n$이다...(2)

그리고 $ab_i$와 $ab_j$ 역시 n으로 나눈 나머지가 항상 다르다...(3)

($\because$ 두 수의 차는 $a(b_i - b_j)$이다. (i)에 따라 $b_i - b_j$는 n의 배수가 아니고(n의 인수를 만족 못하고), gcd(a,n)=1이므로(a는 1외에 n과 인수를 공유 하지 않으므로), $a(b_i - b_j)$역시 n의 배수가 아니다.  그러므로 $(ab_i\mod n) \neq (ab_j\mod n)$이다)

 

$gcd(ab_i,n)=1$ 이고 $(ab_i\mod n)\in S$이다...(4)(유클리드 호제법에 따라 $a=bq+r, 0\leq r < b$ 이면  $gcd(a,b)=gcd(r,b)$이므로)

(1),(2),(3),(4)에 따라 aS의 원소를 n으로 나눈 나머지의 집합은 S와 같고, aS의 모든 원소의 곱과, S의 모든 원소의 곱은 n으로 나눈 나머지가 같다.

 

$\therefore a^{\varphi(n)} b_1b_2b_3\cdots b_{\varphi(n)}\equiv b_1b_2b_3\cdots b_{\varphi(n)} \pmod{n}$

$a^{\varphi(n)} \equiv 1 \pmod{n}$