페르마의 소정리
수론에서 페르마의 소정리(Fermat小定理, 영어: Fermat’s little theorem)는 어떤 수가 소수일 간단한 필요조건에 대한 정리이다. 추상적으로, 소수 크기의 유한체 위의 프로베니우스 사상이 항등 함수임을 의미한다.
-위키백과-
페르마의 소정리는 페르마가 언급했지만 페르마가 아닌 라이프니츠가 증명하였습니다.
페르마의 소정리는
소수 p와 정수 a가 다음을 만족합을 의미합니다
이때 a와 p가 서로소이라면 양변을 약분하여 다음과 같이 나타낼 수 있습니다.
즉 a의 p승을 p로 나눈 나머지 값이 a를 p로 나눈 나머지 값과 같다는 것입니다.
예)
p가 3이고 a가 2일 때
a의 p승은 2의 3승인 8이고
8을 3으로 나눈 나머지 값은 2이고
2를 3으로 나눈 나머지는 2 이므로 같습니다.
또한 a와 p는 서로소 이므로
a의 p-1승은 2의 2승인 4이고
4를 3으로 나눈 나머지는 1입니다
pf)
증명 방법에는 여러 가지가 있지만 합동식을 이용한 방법을 사용하겠습니다.
페르마의 소정리를 증명하기 전 다음을 알아야 합니다.
소수 p와 정수 a가 서로소 일 때 a, 2a, 3a ,... , (p-1) a를 p로 나눈 나머지는 모두 다르다.
증명: 귀류법을 사용하여 증명합니다. 임의의 정수 i, j가 있을 때 ia와 ja를 p로 나눈 나머지가 같다고 합시다.(0 < i < j < p)
그럼 (j - i)a는 p의 배수여야 합니다. a는 p와 서로소 이므로 (j - i)가 p의 배수여야 합니다. 그러나 0 < (j - i) < p 이므로
(j - i)는 p의 배수가 아니므로 모순입니다. 따라서 위의 명제는 참입니다.
0 < i < p일때 ia는 p의 배수가 아니다
증명: i 는 p와 서로소이고 a 또한 p와 서로소 이기 때문에 ia는 p의 배수가 아니다.
a, 2a, 3a ,... , (p-1)a를 p로 나는 나머지는 모두 다릅니다.
또한 1,2,3... , (p-1) 역시 p로 나눈 나머지는 모두 다릅니다.
즉 1부터 p-1까지의 나머지가 모두 나옵니다.
그럼 a x 2a x 3a x ... x (p-1)a 를 p로 나눈 나머지는 1 x 2 x 3 x ... x (p-1)을 p로 나눈 나머지와 같습니다
즉
이고 양변을
로 나누면
페르마의 소정리가 유도됩니다.
참고.
페르마의 소정리 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 수론에서 페르마의 소정리(Fermat小定理, 영어: Fermat’s little theorem)는 어떤 수가 소수일 간단한 필요 조건에 대한 정리이다. 추상적으로, 소수 크기의 유한체 위
ko.wikipedia.org
오타나 오류는 알려주세요.
감사합니다.