페르마의 소정리[Fermat's little theorem]

정의

소수인 p와 정수인 a가 서로 서로소일 때 아래의 식을 만족한다.

 

증명

①  a, 2a, 3a, ..., (p-1)a 인 p-1 개의 수들이 p로 나눈 나머지가 모두 다르다.

→ (귀류법으로 참임을 증명)

  ①번 명제가 거짓이라면 서로 같은 나머지를 가진 두 수 i*a, j*a (0<i<j<a)의 차를 p로 나누었을 때 나누어 떨어지는 경우의 수가 있어야 한다.

  하지만 두 수의 차는 (j-i)*a 이며 a는 p와 서로소이고 1 < j-i < p 이므로 위와 같은 경우의 수는 없다. 따라서 ①번 명제는 참이다.

 

② 집합 A = { x | x = i*a, i ∈ { 1, 2, ..., p-1} }는 ①에 따라 나머지가 모두 다르다. 따라서 A는 집합 B = {1, 2, ..., p-1} 와 원소의 수 및 값이 같으니 다음을 증명한다.

따라서 위 정의는 a와 p가 서로소일 때 참이다.

 

③ 모든 정수 a에 대해선 아래 식을 만족한다. (②에서 a와 p가 서로소일 때 증명하였고, a가 p의 배수일 때 a ≡ 0 (mod p) 이므로)

 

응용

페르마의 소정리를 응용하면 아래의 식을 만들 수 있다. 이를 이용하면 mod p에서 모든 정수형 나눗셈을 정수형 곱셈으로 치환 가능하다.

 

 

예를들어 nCr (mod p) 를 구할 때 모두 자연수의 곱셈으로 표현이 가능하다. (백준 이항계수2, https://www.acmicpc.net/problem/11051)

 

마치며

처음으로 포스팅하며 학생때 관심을 많이 가졌던 정수론 부터 정리하고 있습니다. 사실 nCr (mod p)을 빠르게 구하려면 뤼카의 정리를 이용합니다.

다음시간에는 오일러의 정리와 이어서 이 둘로 증명과정을 거쳐 만들어진 RSA 알고리즘에 대해 포스팅 할까 합니다.