페르마 소수판별법 계산기
페르마의 소정리 a^(n-1) ≡ 1 (mod n)을 여러 밑에서 검사합니다. 카마이클 수 561이 이 판별법을 속이는 것을 직접 계산으로 보여줍니다.
2^(n-1) mod n1 (통과)
7^(n-1) mod n1 (통과)
10^(n-1) mod n1 (통과)
13^(n-1) mod n1 (통과)
판정모든 밑을 통과 — 아마도 소수
561=3×11×17(합성수)로 밑 2,7,10,13을 시험해 보세요 — 서로소인 밑 전부를 통과합니다. 이런 수를 카마이클 수라 부르며, 이 판별법이 확률적일 뿐 완벽하지 않은 이유입니다.
계산 방법
- 1판별할 수 n을 입력합니다.
- 2시험할 밑(들)을 쉼표로 입력합니다.
- 3각 밑에서의 결과와 최종 판정을 확인합니다.
자주 묻는 질문
n이 소수이고 a가 n과 서로소이면 a^(n-1)을 n으로 나눈 나머지가 항상 1이 된다는 페르마의 소정리를 이용합니다. 이 식이 어떤 밑에서 성립하지 않으면 n은 확실히 합성수입니다. 여러 밑에서 전부 성립하면 "아마도 소수"라고 판단합니다.
역이 항상 성립하지는 않기 때문입니다. 561=3×11×17처럼 합성수인데도 자신과 서로소인 모든 밑에서 이 식을 통과하는 수가 있습니다. 이런 예외를 카마이클 수라 부르며, 561이 가장 작은 예입니다.
됩니다. 밑 2, 7, 10, 13으로 시험해 보면 2^560, 7^560, 10^560, 13^560을 561로 나눈 나머지가 전부 1이 나옵니다. 561이 명백한 합성수(3×11×17)인데도 말이죠. 이 계산기로 직접 확인해 보세요.
카마이클 수까지 걸러낼 수 있는 더 강력한 밀러-라빈 판별법을 씁니다. 밀러-라빈은 페르마 판별법에 제곱근 검사를 추가해, 카마이클 수 대부분을 실제로 걸러냅니다.
알아두면 좋은 점
- 서로소가 아닌 밑을 넣으면 그 밑은 검사에서 제외됩니다(gcd(a,n)>1이면 n이 합성수임이 이미 자명하기 때문입니다).
함께 보면 좋은 도구
마지막 검증: 2026년 9월 2일 · 결과는 참고용 추정치입니다.