p를 소수라고 하자.

그러면, 모든 정수 a에 대해, a^p-a 는 언제나 p의 배수이다.                         

정수론에서 정말 중요한 정리입니다. 

참고로, 역은 성립하지 않습니다.  (사실 p를 1이라고 하면, 반례임. 근데, 이런 trivial case 말고...)

모든 정수 a에 대해, a^m-a가 언제나 m의 배수가 되는 합성수 m이 존재합니다. 이런 합성수 m을 카마이클 수라고 합니다. 

심지어 이런 카마이클 수는 무한하다는 것이 증명되었습니다. 

따라서 페르마의 소정리를 만족한다고 소수로 판별하는 것은 위험합니다. 

(페르마의 소정리를 만족하지 않을 경우 합성수라는 결론을 내는 것은 가능합니다.)

페르마의 소정리에 대한 증명은 exercise로 남겨 두죠. 

(속마음 : 이러면 누군가 증명을 적어주겠지?)