페르마의 소정리 편집하기

페르마의 소정리(Fermat's little theorem, 小定理)는 정수론에서 소수와 [[모듈러 산술]]의 관계를 설명하는 기본적인 정리로, 소수 p와 정수 a가 서로소일 때 a<sup>p−1</sup> ≡ 1 (mod p)라는 형태로 표현된다. 이 정리는 [[모듈러 연산]]에서의 지수 계산을 단순화하며, [[오일러 정리]]의 특수한 형태로 볼 수 있다.
==정리 내용==
정수 a가 소수 p와 서로소일 때 다음이 성립한다. a<sup>p−1</sup> ≡ 1 (mod p)

또한, 일반화된 형태로 다음과 같이 표현되기도 한다. a<sup>p</sup> ≡ a (mod p)  이 식은 a가 p로 나누어떨어지지 않더라도 항상 성립한다.

예:
*a = 2, p = 7인 경우: 2<sup>6</sup> = 64 ≡ 1 (mod 7)
*a = 10, p = 13인 경우: 10<sup>12</sup> = 1000000000000 ≡ 1 (mod 13)
==조건==
*p는 소수여야 하며
*a는 p와 서로소여야 한다 (즉, gcd(a, p) = 1)
단, 일반화된 형태 a<sup>p</sup> ≡ a (mod p)는 a가 p의 배수여도 성립한다.
==오일러 정리와의 관계==
페르마의 소정리는 오일러 정리의 특수한 경우이다.  오일러 정리는 다음과 같이 일반화되어 있다: a<sup>φ(n)</sup> ≡ 1 (mod n), 단 a와 n은 서로소

여기서 n = p (소수)이면 φ(p) = p − 1이므로,  a<sup>p−1</sup> ≡ 1 (mod p)가 되어 페르마의 소정리와 일치한다.
==증명 개요==
페르마의 소정리는 다음과 같은 방식으로 증명할 수 있다.
*정수 a가 p와 서로소일 때, a, 2a, 3a, ..., (p−1)a를 mod p로 나타낸 결과는 1, 2, ..., (p−1)의 순열이 된다.
*양변의 곱을 비교하면 a<sup>p−1</sup>(p−1)! ≡ (p−1)! (mod p)가 되며,
*p는 소수이므로 (p−1)!은 p와 서로소이며, 양변을 약분하면 a<sup>p−1</sup> ≡ 1 (mod p)가 된다.
==응용==
*RSA 암호 알고리즘의 이론적 배경으로 활용된다.
*소수 판별 알고리즘(예: 밀러-라빈 검사)의 기본 원리로 사용된다.
*모듈러 연산에서 거듭제곱 계산을 단순화하는 데 유용하다.
==같이 보기==
*[[오일러 정리]]
*[[오일러 피함수]]
*[[모듈러 연산]]
*[[소수]]
*[[RSA 암호화]]
==참고 문헌==
*G. H. Hardy and E. M. Wright, *An Introduction to the Theory of Numbers*, Oxford University Press, 2008.
*Kenneth H. Rosen, *Elementary Number Theory and Its Applications*, Pearson, 2010.
==각주==