카마이클 수

카마이클 수는 1910년에 미국의 수학자 로버트 다니엘 카마이클(Robert Daniel Carmichael)에 의해 처음 연구된 특수한 합성수입니다. 카마이클 수는 모든 a와 gcd(a, n) = 1에 대해 다음 합동식을 만족하는 합성수 n입니다.

a^n-1 ≡ 1 (mod n)

여기서 gcd(a, n)은 a와 n의 최대공약수를 의미합니다. 페르마의 소정리에 따르면, p가 소수일 때 모든 a에 대해 a^p-1 ≡ 1 (mod p)이 성립합니다. 카마이클 수는 소수가 아님에도 불구하고, 특정 조건을 만족하는 모든 a에 대해 페르마의 소정리와 유사한 합동식을 만족한다는 점에서 "가짜 소수"로도 불립니다.

카마이클 수를 판별하는 데 사용되는 중요한 정리는 코르셀트 판별법(Korselt's criterion)입니다. 코르셀트 판별법에 따르면, n이 카마이클 수일 필요충분조건은 n이 제곱인수가 없고, n의 모든 소인수 p에 대해 (p - 1)이 (n - 1)을 나눈다는 것입니다.

가장 작은 카마이클 수는 561 = 3 × 11 × 17이며, 더 많은 카마이클 수가 존재함이 증명되었습니다. 특히, 1994년에 Alford, Granville, Pomerance는 무한히 많은 카마이클 수가 존재한다는 것을 증명했습니다. 카마이클 수는 소수 판별법의 함정을 보여주는 예시이며, 소수 판별 알고리즘 개발에 중요한 고려 사항으로 작용합니다.