📂정수론

카마이클 수

정의 ¹

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

정리

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

설명

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

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

증명

$n$ 이 카마이클 수라고 하자.

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

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

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

■