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

Posted by Bitssam
2015. 7. 18. 07:57 전공수학/Number Theory

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)







'전공수학 > Number Theory' 카테고리의 다른 글

6. 이차잉여 (르장드르기호, 야코비기호)  (2) 2015.07.18
5. 원시근과 이산로그  (0) 2015.07.18
4. 페르마소정리, 오일러정리  (0) 2015.07.18
3. 합동식  (0) 2015.07.18
2. 소수와 소인수분해  (0) 2015.07.17
1. 정수의 성질  (0) 2015.07.17