logo

카마이클 수 📂정수론

카마이클 수

정의 1

자연수 nn 이 모든 1an1 \le a \le n 에 대해 ana(modn)a^{n} \equiv a \pmod{n} 를 만족하면 카마이클 수라 한다.

정리

모든 카마이클 수는 22 를 제외한 서로 다른 소수의 곱으로만 나타난다.

설명

카마이클 수는 합성수임에도 불구하고 페르마 판정법을 통과하는, 말하자면 소수처럼 보이는 수다. 예로써 561=31117561=3 \cdot 11 \cdot 17 은 합성수지만 a561a(mod561)a^{561} \equiv a \pmod{561} 이 항상 성립한다.

한편 이러한 카마이클 수를 잡아내기 위해 밀러-라빈 판정법이 있다.

증명

nn 이 카마이클 수라고 하자.

Part 1. a=n1a = n-1 라고 하면 n11(modn)n-1 \equiv -1 \pmod{n} 이므로 (n1)n(1)n1(modn) (n-1)^{n} \equiv (-1)^{n} \equiv -1 \pmod{n} 위의 합동식을 만족하는 경우는 nn 이 홀수일 때 뿐이다.

Part 2. nn22 를 제외한 소수 p1,,pmp_{1}, \cdots , p_{m} 에 대해 n=p1r1+1pmrm+1n = p_{1}^{r_{1} + 1} \cdots p_{m}^{r_{m} + 1} 으로 나타난다고 하자. 여기서 r:=max{r1,,rm}\displaystyle r : = \max \left\{ r_{1}, \cdots , r_{m} \right\} 이라고 두고 r=0r=0 임을 보이면 증명은 끝난다. 이 rr 에 대응되는 소수를 pp 라 두자.

nn 은 카마이클 수이므로 prnpr(modn)p^{rn} \equiv p^{r} \pmod{n} 이고, nn(prnpr)\left( p^{rn} - p^{r} \right) 을 나누어야한다. 또한 nn약수 중엔 pr+1p^{r+1} 도 있었으므로 pr+1p^{r+1}(prnpr)\left( p^{rn} - p^{r} \right) 을 나누어야한다. 즉 prnprpr+1=prnr1p {{ p^{rn} - p^{r} } \over { p^{r+1} }} = {{ p^{rn - r} - 1 } \over { p }} 은 정수라는 말인데, 이게 가능한 경우는 분자가 00 이 되도록 하는 r=0r=0 뿐이다.


  1. Silverman. (2012). A Friendly Introduction to Number Theory (4th Edition): p133. ↩︎