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