当前位置：网站首页>欧拉定理及费马小定理

欧拉定理及费马小定理

2022-08-05 21:18:00 【NOI RP++】

若正整数 $a, n$ 互质,则 $a^{φ(n)} \equiv 1 \mod(n)$

若 $p$ 是质数,则 $a^p \equiv a \mod(p)$

若正整数 $a, n$ 互质,对于任意正整数 $b$ 有
$a^b \equiv a^{b \mod \phi(n)} \mod(n)$

特别的,当 $a, n$ 不一定互质且 $b > φ (n)$ 时,有
$a^b \equiv a^{b \mod φ(n)+φ(n)} \mod(n)$

版权声明
本文为[NOI RP++]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_63271778/article/details/126071111