- 나머지 분배 법칙으로 푸는 유형이라고 할 수 있다.
\begin{align*}
(a\cdot b)~\%~c &=
(a~\%~c)~\cdot~(b~\%~c)
\\[10pt]
(a^2)~\%~c &=
(a\cdot a)~\%~c =
(a~\%~c)~\cdot~(a~\%~c)
\\[10pt]
(a^3)~\%~c &=
(a\cdot a^2)~\%~c =
(a~\%~c)~\cdot~(a^2~\%~c)
\end{align*}
다음과 같은 식이 있다고 가정하자.
a^n \mod b
- 만약 n = 1이라면, a mod b 와 똑같을 것이다.
- 만약 n = (짝수)라면
a^{10} \mod c =
(a^{5} \mod c) \cdot
(a^{5} \mod c)
- 만약 n = (홀수)라면
a^{11} \mod c =
(a^{5} \mod c) \cdot
(a^{5} \mod c) \cdot
(a \mod c)