[수학]페르마 소정리

페르마는.. 무려 변호사에 취미 삼아 수학을 했다고 한다. ㅎㄷㄷ

피에르 드 페르마 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

이번 포스트에서는 나머지연산의 순환 특성과 연관된 "페르마의 소정리"라는 것을 알아보고 왜 중요한지 고민해보는 시간을 가져보자.

 

나머지의 순환

 

나머지 연산

누구나 알듯이 나머지 연산은 아래와 같이 정의해 볼 수 있다.

n=ax+b에서 n%a = b (단 0 ≤ b < a)
즉 n을 a로 나눴을 때의 나머지는 b 이다.

 

나머지 연산의 순환

나머지 연산은 재미있는 특성이 있는데 위의 수식에서 x가 변화할 때 나머지 b는 0부터 a-1까지 순환된다. 예를 들어 x+2에 대한 %5의 상황을 살펴보자.

(1*1+2)%5 = 3

(1*2+2)%5 = 4

(1*3+2)%5 = 0

(1*4+2)%5 = 1

(1*5+2)%5 = 2

(1*6+2)%5 = 3

...

 

제곱 수에서의 나머지 순환과 페르마의 소정리

페르마는 제곱 수에 대한 나머지 연산에서도 순환이 발생함을 알아냈다. 

2^1 %5 = 2

2^2 %5 = 4

2^3 %5 = 3

2^4 %5 = 1

2^5 %5 = 2

...

 

위의 마지막 연산 결과인 2^5%5=2 를 일반화 해보면 다음과 같다.

a^p%p = a (단 p는 소수이고 a 는 정수)

위 식의 양 변을 a로 나눠보면 a^(p-1)%p = 1이다.!!

이를 좀 더 다듬어 보면 아래와 같이 써볼 수 있다.

p가 소수이고 a가 정수일 때 페르마 소정리에 의해 a^p ≡ a (mod p) 즉 mod p에서 a^p와 a는 서로 합동이다.

만약 a가 0이 아닐 때 양 변을 a로 나눠보면
a^(p-1) ≡ 1 (mod p)                             <----- 1번 특성
양 변을 또다시 a로 나눠보면
a^(p-2) ≡ 1/a (mod p)                          <----- 2번 특성

 

뭐가 그렇게 대단한가?

 

아주 큰 제곱수에 대한 나머지 계산

7^222%11을 구해보면 얼마일까? 

수학적으로 연산을 처리하려면 7^222은 너무 크기 때문에 범위 내에서 연산할 수가 없다. 이런 경우 페르마의 소정리가 사용된다.

페르마의 소정리에 1번 특성에 의하면 a^(p-1)%p = 1 이므로 7^10%11 = 1이다.  따라서 위의 연산은 아래와 같이 유도해볼 수 있다.

7^222 = ((7^10)^22) * 7^2 이므로 %분배 법칙과 앞서 구한 7^10%11=1인 속성을 이용하면

7^222 %11 =  (((7^10)^22) * 7^2)%11 = 7^2 %11 = 49%11 = 5를 얻을 수 있다.

 

나눗셈의 곱셈화

% 연산의 분배 법칙은 나눗셈에는 적용할 수 없다. 

예를 들어 nCr의 p에 대한 나눗셈의 나머지를 계산한다고 할때 아래와 같이 식을 전개할 수 있다.

nCr%p = (n! / ((n-r)! * r!))%p

이때 (n-r)! 이나 r!은 큰 값이기 때문에 나머지 연산을 위해 분배법칙을 사용하고 싶지만 나눗셈이기 때문에 바로 적용할 수가 없다.

이때 페르마 아저씨가 한번 더 등장한다. 페르마의 소정리 2번째 특징을 다시한번 살펴보면 우변 즉 분수 1/a 가 좌변의 정수로 표현되는 마법이 일어난 것을 알 수 있다. 따라서 위의 식은 아래와 같이 전개해볼 수 있다.

만약 7C5에 대한 %11을 계산한다면 다음과 같이 처리할 수 있다.

 

이제 곱샘의 형태로 식이 준비되었기 때문에 %의 분배 법칙을 적용할 수 있게 되었다.

참고로 대부분 이런 문제는 %하는 수로 1,000,000,007과 같이 큰 소수를 던져주기 때문에 무려 1,000,000,005승을 계산해야 하는데 당연히 그대로는 계산이 불가하다. 이때는 분할 정복을 이용한 빠른 제곱수 구하기 기술을 이용해서 처리한다.

 

관련 문제

https://www.acmicpc.net/problem/11401