[알고리즘] 모듈러 연산과 페르마의 소정리

알고리즘 문제를 풀다 보면

"답이 커질 수 있으니 $1,000,000,007$로 나눈 나머지를 출력하시오"

이런 문장이 많이 보인다.

오늘은 이런 나머지연산에 대한 이야기를 하고자 한다.

 

피보나치 수 7

15624번: 피보나치 수 7

이 문제를 한번 보자

단순히 문제에서 제시한대로 구현한다면 이런 코드가 나올것이다.

n = int(input())
a, b = 0, 1
for i in range(n):
    a,b = b, a+b
print(a%1000000007)

하지만 이렇게 제출하게 되면 시간초과 또는 틀렸습니다를 받는다.

그 이유는 계산 과정에서 a, b의 값이 매우 커지기 때문이다.

이를 해결하기 위해 우리는 코드를 다음과 같이 수정한다.

n = int(input())
a, b = 0, 1
for i in range(n):
    a,b = b, (a+b)%1000000007
print(a%1000000007)

이것이 가능한 이유는 다음과 같은 성질 때문이다.

1. $(A+B) \% M = ((A\%M)+(B\%M))\%M$

2. $(A-B) \% M = ((A\%M)-(B\%M))\%M$

3. $(AB) \% M = ((A\%M)(B\%M))\%M$

 

문제는 나눗셈이다.

$(A/B) \% M = ((A\%M)/(B\%M))\%M$ 는 성립하지 않는다.

 

만약 M이 소수라면 페르마의 소정리를 이용하여 아주 간단하게 해결할 수 있다.

 

페르마의 소정리

$a^{p-1} \equiv 1 \pmod{p}$, 단 $p$는 소수이고 $ p \not| \ a $

 

페르마의 소정리에서 양변을 $a^{-1}$을 곱해주면 $a^{p-2} \equiv a^{-1} \pmod{p}$이 된다.

$(A/B) \% M = (AB^{-1})\%M = ((A\%M)(B^{-1}\%M))\%M$

에서 페르마의 소정리를 이용하면

$ ((A\%M)(B^{-1}\%M))\%M = ((A\%M)(B^{M-2}\%M))\%M$

로 모듈러의 성질을 이용할 수 있다.

 

증명

페르마의 소정리를 증명하는 방법에는 여러가지가 있겠지만 그 중 내가 아는 방법을 소개하려고 한다.

소수 $p$에 대해서 순열 $\{1,2,3, \dots , p-1\}$이 있다고 하자.

이 순열에 $a$를 곱할건데 $a$는 $p$와 서로소여야 한다. (그렇지 않을경우 모든 요소가 $0$이 된다.)

그럼 순열 $\{a, 2a, 3a, \dots, (p-1)a \}$를 얻는다.

이를 모듈러 $p$를 취해주면 $a$에 상관없이 순열이 된다. ($p$가 소수이기 때문)

위의 두 순열은 같은 값을 가지고 순서가 다른 순열이므로(같을 수도 있음) 모든 요소를 곱하면 같은 값을 가진다.

즉 $1 \cdot 2 \cdot \cdots \cdot (p-1) \equiv a \cdot 2a \cdot \cdots \cdot (p-1)a \mod p$

정리하면 $ (p-1)! \equiv a^{p-1}(p-1)! \mod p$이고 $(p-1)!$의 역원을 양변에 곱하면 $a^{p-1} \equiv 1 \mod p$를 얻는다. $\Box$

 

이 성질은 M이 소수일 때만 가능한데 문제에서 많이 나오는

$10 \ 007, \ 10 \ 009, \ 998 \ 244 \ 353, \ 1 \ 000 \ 000 \ 007, \ 1 \ 000 \ 000 \ 009$ 들은 소수이다.