페르마의 소정리란?
페르마의 소정리(Fermat's Little Theorem)는 초등 정수론의 근간을 이루는 기본 정리로, 소수를 법(modulus)으로 하는 정수의 거듭제곱을 효율적으로 계산하는 방법을 제공합니다. 이 정리는 오일러 정리(Euler's Theorem)의 특수한 경우에 해당하며, 소수 판별(primality testing)과 공개키 암호(public-key cryptography) 같은 실용적인 응용 분야에서 없어서는 안 될 핵심 도구입니다.
페르마의 소정리의 정의
페르마의 소정리는 다음과 같이 두 가지 형태로 표현할 수 있습니다.
첫 번째 형태: P가 소수이고, a가 P로 나누어 떨어지지 않는 양의 정수라면 다음이 성립합니다.
aP−1 ≡ 1 (mod P)
두 번째 형태: P가 소수이고 a가 임의의 정수라면 다음이 성립합니다.
aP ≡ a (mod P)
증명
Zp를 {0, 1, …, P−1}로 구성된 정수 집합이라고 하겠습니다. 이 집합의 각 원소에 a를 곱한 후 P로 나눈 나머지를 취하면, 그 결과는 순서만 다를 뿐 Zp의 모든 원소를 포함하게 됩니다. 또한 a × 0 ≡ 0 (mod P)이므로, (P−1)개의 수 {a mod P, 2a mod P, …, (P−1)a mod P}는 사실상 {1, 2, …, (P−1)}을 어떤 순서로 나열한 것과 같습니다.
양변의 수들을 모두 곱하고 결과를 P로 나눈 나머지를 구하면 다음과 같습니다.
a × 2a × … × (P−1)a = [(a mod P) × (2a mod P) × … × ((P−1)a mod P)] mod P
= [1 × 2 × … × (P−1)] mod P
= (P−1)! mod P
그런데 좌변은 다음과 같이 정리할 수 있습니다.
a × 2a × … × (P−1)a = (P−1)! · aP−1
따라서 다음 관계가 성립합니다.
(P−1)! · aP−1 ≡ (P−1)! (mod P)
(P−1)!은 P와 서로소이므로 양변에서 약분할 수 있고, 최종적으로 다음 결론을 얻습니다.
aP−1 ≡ 1 (mod P)
집합 X를 통한 직관적 이해
p보다 작은 양의 정수들의 집합 {1, 2, …, p−1}의 각 원소에 a를 곱하고 p로 나눈 나머지를 취하여 집합 X = {a mod p, 2a mod p, …, (p−1)a mod p}를 만들어 보겠습니다.
X의 어떤 원소도 0이 아닙니다. p가 a를 나누지 않기 때문입니다.
X의 원소들은 서로 다릅니다. 만약 ja ≡ ka (mod p) (단, 1 ≤ j < k ≤ p−1)라고 가정하면, a와 p가 서로소이므로 양변에서 a를 약분하여 j ≡ k (mod p)를 얻습니다. 그러나 j와 k는 모두 p보다 작은 서로 다른 양의 정수이므로 이는 모순입니다.
따라서 X의 (p−1)개 원소는 모두 양의 정수이면서 서로 겹치지 않으며, 결국 {1, 2, …, p−1}의 순열임을 알 수 있습니다.
수치 예시
페르마의 소정리에 따르면, p가 소수이고 a가 p로 나누어지지 않으면 ap−1 ≡ 1 (mod p)입니다.
예를 들어 p = 11, a = 3일 때 다음이 성립합니다.
310 ≡ 1 (mod 11)
이를 활용하면 아주 큰 지수의 거듭제곱도 손쉽게 계산할 수 있습니다.
3201 = (310)20 × 3 ≡ 120 × 3 ≡ 3 (mod 11)
활용 예제
페르마의 소정리는 특정 거듭제곱 연산의 답을 빠르게 찾아야 할 때 매우 유용합니다. 다음 예제들을 통해 개념을 확인해 보겠습니다.
예제 1: 610 mod 11 구하기
풀이: 여기서 p = 11이고, 밑인 6은 11로 나누어 떨어지지 않으므로 페르마의 소정리 첫 번째 형태에 의해 다음과 같습니다.
610 mod 11 = 1
예제 2: 312 mod 11 구하기
풀이: 지수(12)가 p−1 = 10과 일치하지 않지만, 식을 변형하면 페르마의 소정리를 적용할 수 있습니다.
312 mod 11 = (311 × 3) mod 11 = (311 mod 11) × (3 mod 11)
두 번째 형태(aP ≡ a mod P)에 의해 311 mod 11 = 3이므로,
= (3 × 3) mod 11 = 9
맺음말
페르마의 소정리는 단순해 보이지만 RSA 암호화를 비롯한 현대 정보 보안 기술의 이론적 토대가 되는 강력한 도구입니다. 소수 모듈로 연산의 성질을 이해하면 큰 수의 거듭제곱 계산을 획기적으로 단순화할 수 있으며, 이는 암호학뿐 아니라 소수 판별 알고리즘에서도 폭넓게 활용됩니다.