카마이클 수
📂정수론카마이클 수
정의
자연수 n 이 모든 1≤a≤n 에 대해 an≡a(modn) 를 만족하면 카마이클 수라 한다.
정리
모든 카마이클 수는 2 를 제외한 서로 다른 소수의 곱으로만 나타난다.
설명
카마이클 수는 합성수임에도 불구하고 페르마 판정법을 통과하는, 말하자면 소수처럼 보이는 수다. 예로써 561=3⋅11⋅17 은 합성수지만 a561≡a(mod561) 이 항상 성립한다.
한편 이러한 카마이클 수를 잡아내기 위해 밀러-라빈 판정법이 있다.
증명
n 이 카마이클 수라고 하자.
Part 1.
a=n−1 라고 하면 n−1≡−1(modn) 이므로
(n−1)n≡(−1)n≡−1(modn)
위의 합동식을 만족하는 경우는 n 이 홀수일 때 뿐이다.
Part 2.
n 이 2 를 제외한 소수 p1,⋯,pm 에 대해 n=p1r1+1⋯pmrm+1 으로 나타난다고 하자. 여기서 r:=max{r1,⋯,rm} 이라고 두고 r=0 임을 보이면 증명은 끝난다. 이 r 에 대응되는 소수를 p 라 두자.
n 은 카마이클 수이므로 prn≡pr(modn) 이고, n 은 (prn−pr) 을 나누어야한다. 또한 n 의 약수 중엔 pr+1 도 있었으므로 pr+1 은 (prn−pr) 을 나누어야한다. 즉
pr+1prn−pr=pprn−r−1
은 정수라는 말인데, 이게 가능한 경우는 분자가 0 이 되도록 하는 r=0 뿐이다.
■