페르마의 소정리 :
p를 소수, a를 정수라고 하자. 그러면 a^p≡a (mod p) 가 성립한다. (a^p을 p로 나눈 나머지와 a를 p로 나눈 나머지가 같다는 뜻이다.)
(예시 : p를 7, a를 2라고 하자. 그러면, 2^7=128이고, 128을 7로 나눈 나머지는 2이다.)
pf)구슬 숫자 p개로 이루어진 목걸이를 생각해 보자. 이제 이 목걸이의 구슬을 색칠할 것인데 칠할 수 있는 색 종류는 a개이다. 원순열 같은 것은 생각하지 않고 구슬을 위치마다 구분한다고 하면, 색칠 가능한 경우의 수 a^p개이다(색 a개에 구슬 p개).
그런데 실제 목걸이는 원형이기 때문에 같은 목걸이를 회전시켜서 얻을 수 있는 경우가 p가지 있고 위에서 단순 셈한 것은 이 목걸이를 다 다른 것으로 계산한 것이 된다. 예를 들어 3개 구슬로 이루어진 목걸이를 흰검빨로 칠하는 경우를 생각해보면 '흰검빨, 검빨흰, 빨흰검'은 회전시켜 보면 모두 같은 목걸이이다. 단, 모든 구슬이 완전히 같은 색깔로 칠해진 경우는 위에서 단순히 셈한 것이나 실제 목걸이나 한 가지로 계산되는데 이 방법은 색깔의 종류인 a가지이다.
따라서 a^p 개(순열)에서 a개(모든 구슬을 같은 색깔로 칠해서 얻을 수 있는 목걸이 숫자)를 빼면 이는 p의 배수가 되어야 한다.
모두 같은 색으로 칠해진 목걸이 a개를 제외한 실제 목걸이 1개에 대해 회전시켜서 얻을 수 있는 p가지를 단순셈에서는 모두 다른 목걸이로 계산했기 때문에 전체 단순셈 목걸이 수에서 깡그리 같은 색인 목걸이 수를 빼면 p의 배수가 되어야 한다. 즉, a^p과 a는 mod p에 대해 합동이다.
p가 소수라는 성질이 어디에 쓰였나요?
