4. 페르마소정리, 오일러정리

IV.페르마소정리, 오일러정리

1. 페르마소정리

페르마소정리는 소수p를 법으로 하는 합동식에 관하여 거듭제곱을 간단히 할 수 있는 정리이다.

소수 p, $a \in Z$에 대하여 (1) ${a^p} \equiv a$ (mod p) (2) 특히 (a, p)=1이면 a를 약분하여 ${a^{p-1}} \equiv 1$ (mod p)

수학적귀납법과 신입생의지수법칙을 이용해서 증명할 수 있으나 생략한다.

<신입생의 지수법칙> 소수 p , $a,b \in Z$에 대하여 ${(a+b)^p} \equiv {a^p} + {b^p}$

페르마 소정리에 의하여 이러한 결과도 도출된다.

p : 홀수인 소수 ,  (a, p)=1일 때 ${a^{\frac{{p - 1}}{2}}} \equiv 1$ , ${a^{\frac{{p + 1}}{2}}} \equiv - 1$ (mod p)중 꼭 하나만 만족한다. 왜냐하면 $0 \equiv {a^{p-1}} - 1 \equiv ({a^{\frac{{p - 1}}{2}}} - 1 ) ({a^{\frac{{p + 1}}{2}}} - 1 )$ (mod p)이므로 ${a^{\frac{{p - 1}}{2}}} \equiv \pm 1$ (mod p)이 성립하나 $1 \equiv - 1$ (mod p)이려면 p|2 인데 이는 모순이다.

2. 오일러 $\phi$ 함수

Euler $\phi$ 함수는 곱셈함수로서 다음과 같이 정의되는 함수이다.

$\phi : \mathbb{N} \to \mathbb{N} \;,\;\phi (m) = \left| {U({Z_m})} \right|$                                   =1에서 m까지의 m과 서로소인 정수의 개수

Euler $\phi$ 함수의 계산방법은 다음과 같다.

소수p, $k \ge 1$에 대하여 $\phi ({p^k}) = {p^k} - {p^{k - 1}}$ $\phi (p) = p - 1$

이 계산법을 통하여 가우스 정리의 결과가 도출된다.

$\sum\limits_{0 < d|m} {\phi (d) = m}$

3. 오일러정리

오일러정리는 임의의 수 m을 법으로 하는 합동식에 관하여 거듭제곱을 간단하게 할 수 있는 정리이다.

$m \ge 2$ , (a, m)=1 에 대하여 ${a^{\phi (m)}} \equiv 1$ (mod m)