📂정수론

코셀트 판정법

개요

카마이클 수임을 판정하는 방법으로써 필요충분조건이라는 점이 또 유용하게 쓰일 수 있는 정리다.

정리 ¹

홀수 $n$ 이 합성수라고 하자.

$n$ 은 카마이클 수 $\iff$ $p \mid n$ 을 만족하는 모든 소수 $p$ 에 대해 $p^2 \nmid n$ 이면서 $(p-1) \mid (n-1)$

증명

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

---

$( \implies )$

카마이클 수는 $2$ 를 제외한 서로 다른 소수 $p_{1} , \cdots , p_{m}$ 에 대해 $n = p_{1} \cdots p_{m}$ 로 나타낼 수 있고, 따라서 $p_{i}^2 \nmid n$ 이어야한다.

$n$ 은 카마이클 수이므로 $a^{n-1} \equiv 1 \pmod{n}$ 이고, 어떤 $k$ 에 대해 $$ a^{n-1} = n \cdot k + 1 = p_{i} \cdot \left( {{n} \over {p_{i}}} k \right) + 1 $$ 이므로 $a^{n-1} \equiv 1 \pmod{p_{i}}$ 이다.

위수의 성질: 소수 $p$ 에 대해 $\gcd (a,p)=1$ 이고 $a^{n} \equiv 1 \pmod{p}$ 면 $\text{ord}_{p} (a) \mid n$

위수의 성질에 따라 $\text{ord}_{p_{i} } (a) $ 는 $(n-1)$ 을 나누고, 원시근 정리에 의해 적어도 $1$ 개의 원시근을 가지므로 어떤 $a_{i}$ 에 대해 $$ \text{ord}_{p_{i} } (a_{i}) = p_{i} - 1 $$ 이다. 따라서 모든 $p_{1} , \cdots , p_{m}$ 에 대해 $(p_{i}-1) \mid (n-1)$ 이어야한다.

---

$( \impliedby )$

$n := p_{1} \cdots p_{m}$ 이라고 하자.

$n$ 을 나누는 모든 소수 $p_{1} , \cdots , p_{m}$ 에 대해서 $p^2 \nmid n$ 이므로, $p_{1} , \cdots , p_{m}$ 는 서로 다르다.

$(p-1) \mid (n-1)$ 이므로 어떤 정수 $k_{i}$ 에 대해 $$ (n-1 ) = ( p_{i} - 1) k_{i} $$ 이다. 이제 $1 \le a \le n$ 라 하고 $p_{i}$ 로 나눠지는 경우와 나눠지지 않는 경우를 생각해보자.

• Case 1. $p_{i} \mid a$
  당연히 $a^{n} \equiv 0 \equiv a \pmod{p_{i}}$ 이 성립한다.
• Case 2. $p_{i} \nmid a$
  페르마의 소정리에 의해 $$ \begin{align*} a^{n} =& a^{ ( p_{i} - 1) k_{i} +1 } \\ =& a^{ ( p_{i} - 1) k_{i} } \cdot a \\ \equiv& 1^{k_{i}} \cdot a \pmod{p_{i}} \\ \equiv& a \pmod{p_{i}} \end{align*} $$

따라서 어떤 경우든 $$ ( a^{n} - a ) \equiv 0 \pmod{ p_{i} } $$ 인데, 이는 곧 $( a^{n} - a )$ 이 $p_{1}, \cdots , p_{m}$ 으로 나누어 떨어진다는 것이다. 다시 말해 $( a^{n} - a )$ 은 $n= p_{1} \cdots p_{m}$ 으로 나누어 떨어지고, 정리하면 다음을 얻는다. $$ ( a^{n} - a ) \equiv 0 \pmod{ n } $$

■