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

Question

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

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

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

Answer 1

因為mod有可乘性

設 a=mq+r, b=nq+s. 則

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

手機碼字有些混亂