페르마의 소정리란?
페르마의 소정리(Fermat's Little Theorem)는 정수론의 핵심 정리 중 하나입니다. 이 정리에 따르면 p가 소수이고 a가 p로 나누어떨어지지 않는 정수(즉 \(\gcd(a, p) = 1\))일 때, a를 (p − 1)제곱한 값을 p로 나누면 나머지가 항상 1이 됩니다. 기호로 표현하면 $$a^{\,p-1} \equiv 1 \pmod{p}$$입니다. 또한 모든 정수 a에 대해 성립하는 더 일반적인 형태도 있는데, 바로 $$a^{\,p} \equiv a \pmod{p}$$입니다.
계산기 사용법
밑 a 값과 p 값을 입력하세요. 계산기는 먼저 p가 소수인지 확인하고 \(\gcd(a, p)\)를 구한 다음, 빠른 모듈러 거듭제곱(modular exponentiation)을 이용해 \(a^{\,p-1} \bmod p\)와 \(a^{\,p} \bmod p\)를 모두 계산합니다. p가 소수이고 \(\gcd(a, p) = 1\)인 경우 첫 번째 결과는 항상 1이 되며, 이로써 정리가 성립함을 확인할 수 있습니다. 이 조건을 만족하지 않으면 정리가 결과값 1을 보장하지 않으므로 \(a^{\,p-1}\) 결과는 n/a로 표시됩니다.
공식 풀이
모듈러 거듭제곱은 밑을 반복해서 제곱하면서 그때마다 p로 나눈 나머지를 취하기 때문에, 지수가 아무리 커져도 계산이 감당할 수 있는 크기로 유지됩니다. 이 정리는 소수 판정법(페르마 소수 판정), RSA 암호의 키 계산, 그리고 모듈러 역원 계산의 기초가 됩니다. 소수 p에 대해 \(a^{\,p-2} \bmod p\)가 곧 a의 p에 대한 역원이 되기 때문이죠.
예제로 살펴보기
\(a = 2\), \(p = 7\)이라고 해봅시다. 7은 소수이고 \(\gcd(2, 7) = 1\)이므로, $$2^{6} \bmod 7 = 64 \bmod 7 = 1$$이 될 것으로 예상할 수 있습니다. ✔ 일반형으로 계산하면 $$2^{7} \bmod 7 = 128 \bmod 7 = 2$$이며, 이는 \(a \bmod 7 = 2\)와 같습니다. ✔
자주 묻는 질문
p가 소수가 아니면 어떻게 되나요? 정리가 성립하지 않을 수 있습니다. 이 경우 계산기는 p가 소수가 아님을 표시하며, 일반형 \(a^{\,p} \bmod p\) 값만 의미가 있을 뿐 반드시 a와 같지는 않습니다.
a가 p의 배수이면 어떻게 되나요? 그렇다면 \(\gcd(a, p) \neq 1\)이므로 \(a^{\,p-1} \bmod p\)는 1이 되지 않습니다(0이 됩니다). 다만 일반형 \(a^{\,p} \equiv a\)는 여전히 성립합니다.
모듈러 역원을 구하는 데 사용할 수 있나요? 네, 가능합니다. 소수 p에 대해 \(a^{\,p-2} \bmod p\)가 곧 a의 p에 대한 곱셈 역원입니다.
