소수 p에 대해 a !≡ 0(mod p) 을 만족하는 a의 배수 (mod p)는 1, 2, ..., p-1을 재배열한 것과 같다.증명a, 2a, ..., (p-1)a 는 p의 배수가 아니다.이때 ja, ka가 법 p에 대해 합동이라 가정한다. (1ja ≡ ka (mod p)이므로 p|(j-k)a이다. p∤a 이므로 소수의 가약성에 의해 p|(j-k)이다.그러나 (1따라서 j-k = 0 -> j = k이다p에 대해 합동인 수 ja = ka이므로 합동이면 전부 같은 숫자다.0이 아닌 p-1개의 합동이 아닌 수 목록은 1~p-1이므로 따라서 재배열이다.즉, a, 2a, ..., (p-1)a (mod p)와 1, 2, ..., p-1 (mod p)는 순서만 다르지 같은 배열이다. 페르마의 소정리p가 소수이고 a..

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이므로 합성수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) ..