[정수론](-)[카마이클 수의 성질]

주어진 정수 n이 카마이클 수이고, 소수 p는 n의 약수라 하자. p − 1이 n − 1을 나눈다는 사실을 증명하여라. 또한, p − 1이 사실은 더 작은 수인 n/p − 1을 나눔을 증명하여라.

 

p − 1이 n − 1을 나눈다는 사실을 증명

 

카마이클 수의 성질에 의해 gcd(a, n) = 1에 대해
a^(n-1) ≡ 1 (mod n)
=> a^(n-1) ≡ 1 (mod p) <- mod big -> mod small은 언제나 성립

p는 소수이므로, 원시근 g가 존재하고 a = g라고 두자.
g^(n-1) ≡ 1 (mod p)
g에서 위수 e = p-1이고,
위수의 나눔성질에 의해 e | n-1이다.
즉, p-1 | n-1이다.

 

p − 1이 n/p − 1을 나눔을 증명

 

n = pm이라고 하자.
n/p - 1 = m - 1이다.

위에서 p-1 | n-1은 보였다. 이걸 이용해보자.
n-1 = pm-1 = (p-1)m + m-1
따라서 (n-1)/(p-1) = m + (m-1)/(n-1) = 정수
m = 정수이므로, (m-1)/(n-1) 도 정수여야 한다.
따라서 p-1 | m-1 = n/p - 1