카마이클 수 판정기

합성수인데도 자기와 서로소인 모든 밑에 대해 a^(n−1) ≡ 1 (mod n)을 만족하는 수입니다. 가장 작은 것이 561 = 3·11·17입니다. 페르마 소수판별은 이 식이 성립하면 소수라고 보는 방법이라, 카마이클 수는 밑을 아무리 많이 골라도 소수처럼 보입니다. 그래서 절대 유사소수라고도 부릅니다.

합성수 n이 카마이클 수일 필요충분조건은 첫째 n이 제곱인수를 갖지 않고, 둘째 n의 모든 소인수 p에 대해 (p−1)이 (n−1)을 나누는 것입니다. 1899년 코르셀트가 낸 이 조건 덕분에 밑을 하나도 훑지 않고 소인수분해만으로 판정할 수 있습니다. 561의 경우 560 = 2⁴·5·7이고 소인수는 3·11·17이라 2, 10, 16이 모두 560을 나눕니다.

n이 짝수면 n−1이 홀수인데, 소인수 p가 홀수 소수라면 p−1은 짝수라 홀수인 n−1을 나눌 수 없기 때문입니다. 같은 이유로 서로 다른 소인수가 반드시 세 개 이상이라는 것도 따라 나옵니다. 이 계산기는 그 성질을 판정 조건에 넣지 않고, 코르셀트의 두 조건만으로 실제로 그렇게 되는지 확인하도록 만들었습니다.

밑을 훑지 않고 L(n) = ∏ gcd(n−1, p−1)로 셉니다. 중국인의 나머지 정리로 소인수마다 갈라 보면 각 순환군에서 조건을 만족하는 원소가 gcd(n−1, p−1)개이기 때문입니다. 카마이클 수라면 모든 p에 대해 (p−1)이 (n−1)을 나누므로 이 값이 ∏(p−1) = φ(n)과 같아져 서로소인 밑이 전부 속습니다.

341 = 11·31은 밑 2에 대해서만 페르마 판별을 통과하는 유사소수입니다. 밑을 3으로 바꾸면 곧바로 걸립니다. 카마이클 수는 서로소인 밑을 전부 속인다는 점이 다르며, 그래서 밑을 여러 개 시도하는 대응이 통하지 않습니다.

n−1 = 2^s·d로 쪼갠 뒤 a^d를 제곱해 가며 1에 이르는 길을 봅니다. n이 소수라면 1 직전 값이 반드시 −1이어야 합니다 — 소수 modulo에서 1의 제곱근은 ±1뿐이기 때문입니다. 합성수에서는 1의 다른 제곱근이 존재하고, 그 값이 나오면 합성수임이 들통납니다. 카마이클 수도 이 검사는 피하지 못해 서로소인 밑의 최소 4분의 3이 증인이 됩니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.