欧拉定理(数论) 及其拓展 - Extended Euler Theorem

$\forall a<m,(a, m)=1$,均有$a^{\varphi(m)}\equiv1\pmod{m}$,于是就有欧拉定理: $$a^n\equiv a^{n \mod \varphi(m)} \pmod{m}$$ 对于$n$取值较大的情况(比如$10^{30000}\mod 13$),欧拉降幂的作用不可忽视,但局限的是必须满足$(a,m)=1$才能有上式恒成立。 由于上述形式流传甚广,读者大抵早已熟记于心,这里便不再赘述。本文的最终目的是介绍另一个适用范围更广的版本,即所谓拓展欧拉定理。 $$a^n\equiv a^{n \mod \varphi(m) + \varphi(m)} \pmod{m} \quad \textrm{if }n \geq \varphi(m)$$ ...

August 28, 2021 · 3 min · Kenshin2438