모듈로(modulo) 연산, 페르마의 소정리(FlT)
모듈로(modulo) 연산
한 숫자를 다른 숫자로 나눈 후 나눗셈의 나머지를 반환하는 연산이다.
두 개의 양수 a,n에 대해 모듈로 n(mod n)은 a를 n으로 나눈 나눗셈의 나머지이다.
- a : 피제수(dividend), 나눠지는 수
- n : 제수(divisor), 나누는 수
여담으로, 파이썬의 내장함수 중 pow(a,b) 함수는 기존의 **, 거듭제곱 연산을 최적화한 함수인데, pow(a,b,c)로도 사용가능하다.
이때의 c는 a의 b제곱에 대한 모듈로 연산의 제수로 사용된다.
모듈로 연산의 규칙
덧셈, 곱셈, 뺄셈에 대한 모듈로 연산에서는 일종의 분배법칙이 성립한다.
\[(a+b)\%p = ((a\%p)+(b\%p))\%p\] \[(a-b)\%p = ((a\%p)-(b\%p))\%p\] \[(a\times b)\%p = ((a\%p)\times (b\%p))\%p\]하지만 나눗셈에 대해서는 항상 성립하지 않는다.
\[(a\div b)\%p \neq ((a\%p)\div (b\%p))\%p\]이런 점이 문제가 되는 경우가 이항계수의 모듈러 연산에서 발생한다.
이항계수 $n \choose k$를 계산하기 위해서는 팩토리얼을 팩토리얼로 나눠주는 연산이 필요하다.
\[{n \choose k} =\, _{n}\mathrm{C}_k =\frac{n!}{k!(n-k)!}\]보통 팩토리얼의 값은 기하급수적으로 커치므로, 특정 소수로 나눈 모듈러 연산의 결과 값을 사용하는데,
이 경우 분모의 팩토리얼에 대한 모듈러 연산의 분배 법칙을 어떻게 정의할 수 있는지가 핵심이 된다.
이런 문제를 해결하기 위해 페르마의 소정리를 사용하게 된다.
페르마의 소정리(Fermat’s little Theorem, FlT)
p가 소수이고 a와 p가 서로소이면 $a^{p-1} \equiv 1 \pmod{p} $이다. 즉, $a^{p-1}$을 p로 나누면 나머지가 1이다.
$a^{p-1} \equiv 1 \pmod{p}$ 해당 식을 합동식이라고 하며, 다음과 같이 해석하면 된다.
- $a^{p-1}$을 p로 나눈 나머지와 1을 p로 나눈 나머지가 같다.
위 정리의 합동식에서 양 변을 a로 곱하고 나누면 다음과 같은 결과를 얻을 수 있다.
\[\begin{align} a^p \equiv a \pmod {p} \\ a^{p-1} \equiv a \pmod {p} \\ a^{p-2} \equiv \frac{1}{a} \pmod {p} \end{align}\]페르마의 소정리를 사용하면, 분수 형태에 대한 모듈러 연산을 곱셈 모듈러 연산으로 대체하는 방식을 알 수 있다.
\[\begin{align} FlT \Rightarrow a^p \% p &= a \% p \\ a^{p-1}\% p &= 1 \% p \\ a^{p-2}\% p &= \frac{1}{a}\% p \\ \therefore \frac{n!}{k!(n-k)!} \% p &= (n!\%p)\times((k!\times(n-k)!)^{p-2}\%p)\%p \end{align}\]