[정수론](13)[소수 판정과 카미이클 수]

 

소수의 판정법

1. root(n)보다 작거나 같은 소수로 나누기
2. 페르마의 소정리
   -> 카마이클 수라는 반례가 있음!

 

카마이클 수

합성수지만 페르마의 소정리를 만족하는 수
gcd(a, m) = 1일때
a^n ≡ a (mod n) 인 합성수 n

 

코어젤트의 카마이클 수 판정법

n이 합성수라 가정할 때
    n = 홀수
    n을 나누는 모든 소수 p에 대해
        p^2 ∤ n
        p-1 | n-1
    이라면 n은 카마이클 수이다.

 

증명

• 모든 카마이클 수는 홀수이다
  모든 a에 대해 a^n ≡ a (mod n)을 만족해야 한다.
  a = n-1이라 가정할 때 n-1 ≡ -1 (mod n) 이므로,
  따라서 (n-1)^n ≡ (-1)^n ≡ 1 (mod p)
  따라서 n = 홀수
• 모든 카마이클 수는 서로 다른 소수의 곱이다
  소수 p는 p|n이고 p^(e+1)|n인 가장 큰 거듭제곱이라 두자.
  (즉, p^(e+1)|n 이고 p^(e+2)∤n이다.)
  a = p^e 라고 가정한다면
  카마이클 수의 정의에 의해 p^en ≡ p^e (mod n)이므로
      n | p^en - p^e
      p^(e+1) | n 
  따라서 p^(e+1) | p^en - p^e
  => (p^en - p^e)/(p^(e+1)) = ( p^e(n-1) - 1)/p = 정수
  e = 0일 경우에밖에 성립 안함.
  따라서 소수의 제곱수 이상은 인수로 가지지 않으므로 서로 다른 소수의 곱이다
• 모든 카마이클 수의 인수 p에 대해 p-1 | n-1
  p-1|n-1 일때 모든 a에 대해 카마이클 수의 성질을 만족해야 한다.
  • p | a 라면, a ≡ 0 (mod p)
    따라서 a^n ≡ a (mod p)
  • p ∤ a 라면, a^(p-1) ≡ 1 (mod p)
    a^n = a^(1+k(p-1)) ≡ a* a^(p-1)k (mod p)
    p는 소수이고, gcd(a, p) = 1 이므로, 페르마의 소정리에 의해 1 ≡ a^(p-1) (mod p)
    따라서 a^n ≡ a (mod p)

    따라서 모든 n의 인수 p에 대해 모든 a에서
    a^n ≡ a (mod p) 가 성립하고 p는 서로 다른 소수이므로,
    a^n ≡ a (mod p1p2p3...) => a^n ≡ a (mod n)이다.