Fermats Small Theorem

{{|
p가 소수이고 a가 p로 나눠지지 않는 정수이면, a^{p-1} - 1은 항상 p로 나눠진다.
|}}

혹은

{{|
p가 소수이면, 임의의 정수 a에 대해 a^p - a는 항상 p로 나눠진다.
|}}

이 두 명제는 동치이다.

• 3^4 - 1은 5로 나누어진다: 3^4 - 1 = 80 = 5 * 16
  
• 5^16 - 1은 17로 나누어진다: 5^16 - 1 = 152587890624 = 17 * 8975758272
  
  

p=7, a=3인 경우를 생각하자. 다음의 여섯 정수

를 7로 나눈 나머지는 정확하게 1,2,3,4,5,6이 된다. 왜냐하면

1. 3*n(n=1,2,3,4,5,6)중에 7의 배수는 없다. 따라서 3*n(n=1,2,3,4,5,6)을 7로 나눈 나머지는 1,2,3,4,5,6중의 하나이다.
   
2. 3*n(n=1,2,3,4,5,6)을 7로 나눈 나머지 중에 같은 것은 없다. 왜냐하면, 만일 3*n과 3*m을 7로 나눈 나머지가 같다면, 3*n-3*m = 3*(n-m)이 7의 배수이고, 이 때 3이 7로 나누어 떨어지지 않기 때문에 n-m이 7의 배수이어야 하는데, n과 m은 1,2,3,4,5,6중의 하나이기 때문에 유일하게 가능한 경우가 n=m일 때 뿐이기 때문이다.
   
   

따라서 1,2,3,4,5,6을 모두 곱한 값과 3*1,3*2,3*3,3*4,3*5,3*6을 모두 곱한 값은 7로 나눈 나머지가 같다. 즉,

가 7로 나누어 떨어진다. 1*2*3*4*5*6이 7로 나누어 떨어지지 않으므로 이것은

이 7로 나누어 떨어진다는 것을 의미한다.

a가 p로 나누어 떨어지지 않으면, a + pZ는 Z/pZ의 unit이 된다. 그런데 Z/pZ의 unit들은 order가 p-1인 (multiplicative) group을 이루므로, Lagrange theorem에 의해 (a+pZ)^{p-1} = a^{p-1}+pZ = 1+pZ이다. 따라서 a^{p-1} - 1은 p로 나누어 떨어진다.

역시 p=7, a=3을 예로.

원판을 360/7 도로 칠등분한 영역에 3가지 종류의 색을 칠하는 방법의 수를 세어 보자.

각 영역에 3가지 색이 가능하므로, 일단 모든 경우의 수는 3^7이다.

그런데 이 가운데 한 가지 색으로만 칠이 된 3가지 경우를 제외한 나머지는 회전해서 같은 모양이 7개씩 나온다.

따라서, 원판을 구별할 수 있는 색칠 방법의 수는 (3^7 - 3) / 7 + 3 이다.

이 값은 명백히 자연수이므로, 3^7 - 3 은 7로 나누어 떨어진다.

수학분류