이항계수를 구하는 알고리즘 고급편 - 페르마의 소정리-

1. 페르마의 소정리 p가 소수이면 모든 정수 a에 대하여 $a^p$와 a를 p로 나눈 나머지는 서로 같다. 만약 a가 p의 배수가 아닌 서로소라면 $a^{(p-1)}$와 1을 p로 나눈 나머지는 서로 같다 역은 성립하지 않는다. 즉 모든 정수 a에 대하여 $a^p \equiv a (mod p)$임에도 불구하고 p가 합성수일 수 있다 2. 응용 - 이항계수를 빠르게 구하는 방법 n과 r이 10만에서 100만정도 되는 매우 큰 수에 대하여 어떻게 하면 빠르게 구할 수 있을까 파스칼의 삼각형을 이용한 다이나믹 프로그래밍으로는 이제는 불가능하다 그래서 $nCr = n! / ((n-r)! * r!)$을 직접 구할 필요가 있는데 이 경우 n과 r이 매우 크면 직접 나타내기 어려우므로 어떤 소수 p에 대해 나머지를..