페르마의 소정리 알아보기

백준 알고리즘을 푸는데 페르마의 소정리 를 이용한 알고리즘을 이용한 문제가 나와서...

오늘은 페르마의 소정리에 대해 알아 볼까 합니다.

페르마의 소정리는 위키백과에 따르면 다음과 같습니다.

여기서  란 a가 p의 배수가 아니라는 의미 입니다.

a가 p의 배수일때는 p | a 라고 표기하고 그렇지 않은 경우 위와 같이 표기 합니다.

여기서 합동이란 기하의 도형에서 나오는 합동을 대수학으로 옮겨와서 쓴 식을 합동식이라고 합니다.

가령△ABC≡△DEF에서 △ABC와 △DEF는 합동이다라고 이야기하는데요.

일단 기하학에서는 합동의 대상이 도형이 되며 기하학에서는 두 도형의 위치와 방향을 불문하고 각과 변만 같으면 합동이라고 합니다.

그렇다면 대수학에서의 합동은 무엇을 의미할까요?

2 ≡ 2 와 같이 같은 수를 의미 하지는 않습니다.

대수학에서는 숫자의 실제 크기를 불문하고 어떤 수로 나누었을때 나머지가 같으면 합동이라고 합니다.

7 과 12 는 5로 나누었을때 나머지가 2 입니다.

이때 다음과 같이 합동이라고 정의 합니다.

7 ≡ 12(mod 5)

즉 a ≡ b (mod p) 이면 a를 p로 나눈 나머지와 b를 p로 나눈 나머지가 같다 라고 보는 것을 대수학의 합동이라고 합니다.

페르마의 소정리는 위키백과에 따르면

p 가 정수 a를 나눌 수 없는 소수라면

a의 p승 ≡ a(mod p)

a의 (p-1)승 ≡ 1(mod p)

이라고 정의를 합니다.

가령 a=3, p=5 라고 하면

3의 4승 ≡ 1(mod 5) 인지 확인을 해보면 

3 * 3 * 3 * 3 = 81 이 되며 이것을 5로 나누면 나머지가 1이 되는 것을 확인 할 수 있습니다.

이러한 페르마의 소정리를 이용하면 다음과 같은 문제를 쉽게 풀수도 있을것 같네요.^^

문제) 4의 15승을 5로 나눈 나머지는 얼마인가?

=> 4의 15승을 계산하는 것보다 (4의 3승)의 5승 으로 표현을 해 보면

=> (4의 3승) 5승 ≡ 4의 3승(mod 5) 로 표현할 수 있으므로

=> 4의 3승은 64 이므로 64를 5로 나눈 나머지는 4 라는 것을 빠르게 계산 할 수 있겠네요.

페르마의 소정리 의 증명

1. a와 서로소인 소수 p에 대해 a, 2a, 3a, ..., (p-1)a인 p-1개의 수를 살펴보자. 이 수들을 p로 나눴을 때 나오는 나머지는 모두 다르다.

   예) a가 3 p가 5 인 경우 a,2a,3a,4a 는 5로 나눈 나머지가 각각 3,1,4,2 가 되는 것을 확인 할 수 있습니다.

   이것을 증명하기 위해서는 귀류법을 사용하는데요.

   a, 2a, 3a, ..., (p-1)a 의 임의의 두수를 골랐을때 p와 합동이 되는 수가 존재 한다면 위의 증명은 틀리게 되는 것입니다.

 

   어떤 수 m과 n이 있다고 하면 (0<n<m<p인 정수)

   임의의 수 ma 와 na 가 합동이 되는지 확인을 하면 됩니다.

   ma = p * A + 나머지

   na = p *  B + 나머지

  (여기서 나머지 < p 입니다.)

  

  만약에 합동이 된다면 나머지가 같은 경우이므로

  두 식을 빼 주게 되면

  (m-n)a=p(A-B) 와 같은 식이 됩니다.

  따라서 (m-n)a 는 p의 배수입니다.

  하지만 문제에서 a와 p는 서로소이고 m-n<p 이기 때문에 m-n 역시 p의 배수가 아닙니다. 

  이는 모순이므로 나머지가 같은 두수 ma,na는 존재하지 않습니다. 

2. 또 0 < i < p인 i에 대해 ia 역시 p의 배수가 아니다 ( 이것도 동일한 방법에 의해 증명이 됩니다.)

3.   에서  

 을 확인해 보면

   A는 a,2a,3a...(p-1)a 의 원데이터 집합이며

   B는 p와 서로소인 수를 p로 나눌때 생기는 모든 집합 이다.

   A의 집합의 갯수와 B의 집합의 갯수가 같으면서 B의 집합의 갯수가 p-1개 이면서 각각 모두 다른 수가 되려면...

   1부터 p-1 까지의 전체 데이터와 동일합니다.

4. 따라서 

  의 양변을 (p-1)! 로 나누게 되면 

  

  이 되는 결론을 얻게 되네요.

이상은 위키백과를 보면서 제 생각을 정리하는 차원에서 다시한번 페르마의 소정리를 써 보았습니다.

직접 증명을 해 보는 것이 어떤 정리를 이해 하는데 많은 도움이 되므로...

페르마의 소정리를 알고 끝내는 것 보다는 한번쯤 증명을 해 보게 된다면 훨씬 더 많은 도움이 될것 같네요.