a^p \equiv a\pmod x~~\text{일때, }~~
\\[10pt]
\text{a와 p가 서로소이면 }
a^{p-1} \equiv 1\pmod p
풀어 써보기
a^p \bmod x = a \bmod x
이때 식을 다음과 같이 바꿀 수 있다.
a^{p-1} \bmod p = a^{1-1} \bmod x
- 우선 나눠지는 수(x)를 지수에 있던 p로 바꿀 수 있다.
일반화하면 다음과 같다.
a^{p-n} \bmod p = a^{1-n} \bmod x
활용: 이항계수의 정리
-
주어지는 n과 r의 범위가 O(nr)의 시간복잡도로 충분히 수행 가능하다면,
파스칼의 삼각형으로 이차원 배열을 선언하여 미리 전처리해두면 된다.
\binom{n}{r} =
\binom{}{r} + \binom{}{r}
- 그러나 주어지는 n의 값이 너무 커지면 그냥 계산해야 한다.