[정수론](-)[카마이클 수 판별]

561이 카마이클 수인지 판별하시오

카마이클 수란, gcd(a, m) = 1일때, a^(m-1) ≡ 1 (mod m)를 만족하지만 소수가 아닌 m을 말한다.
따라서
m이 합성수이고
gcd(a, m) = 1인 모든 a에 대해 a^(m-1) ≡ 1 (mod m)
를 만족하는지 보이면 된다.

1.561이 합성수?
561 = 3 * 11 * 17이므로 합성수

2. gcd(a, 561) = 1인 모든 a에 대해 a^(560) ≡ 1 (mod 561)?
   gcd(a, 561) = 1 이고 561의 인수가 각각 서로소이고 소수이므로,
       gcd(a, 3) = 1
       gcd(a, 11) = 1
       gcd(a, 17) = 1 만족한다.
   따라서 3, 11, 17에 대해서 페르마의 소정리를 사용할 수 있다.
       a^2 ≡ 1 (mod 3)
       a^10 ≡ 1 (mod 11)
       a^16 ≡ 1 (mod 17)
   이걸 a^(560) ≡ 1 (mod 561)로 표현하면
       (a^2)^280 ≡ 1^280 ≡ 1 (mod 3)
       (a^10)^56 ≡ 1^56 ≡ 1 (mod 11)
       (a^16)^35 ≡ 1^35 ≡ 1 (mod 17)
   즉, a^560-1은 3, 11, 17로 나누어떨어진다. 그리고 gcd(3, 11, 17) = 1이므로,
    3*11*17 | a^560 - 1
   즉, 조건을 만족하는 모든 a에 대해 a^(560) ≡ 1 (mod 561)을 만족한다.