c++ - 为什么次幂取余可以写成先乘再取余？

Question

a的b次方对c取余可以写成下面的形式

int ans = 1;
while (b−−){
 ans = ( ans∗a)%c ;
}

数学不好，求大神解释一下

Answer 1

Because the mod is multiplier

Suppose a=mq+r, b=nq+s. Then

(a*b) mod q = (mnq^2+msq+nrq+rs) mod q = rs mod q = ((a mod q) * (b mod q)) mod q

The phone code is a bit confusing