홍라이프 계산기페르마의 소정리 계산기 쉽게 이해하기 — 개념과 원리
이 계산기는 밑 a와 법 p에 대해 페르마의 소정리를 확인합니다. a^(p−1) mod p와 a^p mod p를 정확히 계산하고, p가 소수인지 판정하며, 결과가 무엇을 뜻하는지 설명하고, p가 소수이면 a의 모듈러 역원도 알려 줍니다. 정수론 수업, 암호의 기초, 소수 판정에 쓸 수 있습니다.
계산 방법
페르마의 소정리: p가 소수이고 a의 약수가 아니면 a^(p−1) ≡ 1 (mod p), 모든 a에 대해 a^p ≡ a (mod p)
거듭제곱은 반복 제곱법으로 정확히 계산합니다.
p는 결정적 밀러-라빈 검사로 판정합니다.
p가 소수이면 a의 역원은 a^(p−2) mod p입니다.
원리
1, 2, …, p − 1에 각각 a를 곱해 p로 나눈 나머지를 구하면, p가 소수이고 a를 나누지 않을 때 같은 수들이 순서만 바뀌어 나옵니다. 양쪽을 모두 곱하면 a^(p−1) × (p − 1)! ≡ (p − 1)!이 되고, (p − 1)!을 지우면 a^(p−1) ≡ 1이 남습니다. 이 정리는 한쪽 방향으로만 쓸 수 있습니다. 결과가 1이 아니면 p가 합성수임이 증명되지만, 1이라고 소수임이 증명되지는 않습니다. 341 = 11 × 31(밑 2) 같은 유사소수와 561 같은 카마이클 수도 통과하기 때문입니다.
예제 풀이
기본값: a = 3, p = 101.
- a mod p = 3입니다.
- 3¹⁰⁰ mod 101 = 1이며, 반복 제곱법으로 계산합니다.
- 3¹⁰¹ mod 101 = 3으로 a^p ≡ a와 맞습니다.
- p는 소수이므로 예상대로 정리가 성립합니다.
- 101을 법으로 한 3의 역원 = 3⁹⁹ mod 101 = 34이며, 3 × 34 = 102 ≡ 1로 확인됩니다.
결과 해석
p가 소수이고 결과가 1이면 정리가 그대로 작동한 것입니다. 1이 아니면 p가 합성수라는 증명서이며, a를 페르마 증거라고 부릅니다. p가 합성수인데 1이 나오면 페르마 유사소수입니다. 34 같은 모듈러 역원은 RSA 같은 공개키 암호에서 쓰입니다.
흔한 실수
- a^(p−1) ≡ 1을 p가 소수라는 증명으로 보는 경우
- p가 a의 약수가 아니어야 한다는 조건을 잊는 경우
- 큰 p에서 a^(p−1)을 끝까지 계산한 뒤 나눠 수가 넘치는 경우
- a^(p−1) ≡ 1과 a^p ≡ a를 혼동하는 경우
자주 묻는 질문
페르마의 소정리란?
소수 p가 a를 나누지 않으면 a^(p−1)을 p로 나눈 나머지가 1이라는 정리입니다.
소수임을 증명할 수 있나요?
아닙니다. 합성수임은 증명할 수 있지만 일부 합성수도 통과합니다.
모듈러 역원은 어떻게 구하나요?
p가 소수이면 a의 역원은 a^(p−2) mod p입니다.
작은 예로 확인할 수 있나요?
네. p = 7, a = 2이면 2⁶ = 64이고, 64를 7로 나눈 나머지는 1입니다.
아주 큰 수도 계산되나요?
반복 제곱법은 지수를 절반씩 줄여 가므로 매우 큰 지수도 빠르게 계산합니다.
출처: E. W. Weisstein, "Fermat's Little Theorem", Wolfram MathWorld