欧拉定理以及推广

Asika391 · 2019-07-08 16:05:06 · 个人记录

欧拉定理

    如果a，m互质，则a^φ（m）≡1 （mod m);
证明：讲1-m中所有与m互质的数从小到大写出：x1,x2,x3，……，xφ（m）,同乘一个
a得到ax1，ax2，ax3，……，axφ（m）。若ax1≡ax2 （mod m）可得m∣（x1-x2）显
然不成立，于是乘上一个a后这些数各不相同(模m意义下)。且均与m互质,相当于下面
是上面那些数的一个排列，于是将两组数相乘得到∏xi≡a^φ（m）∏xi （mod m）化简
即得a^φ（m）≡1 （mod m)。

推论：费马小定理

当 p 是质数,a ̸= p 时，有 a^(p−1) ≡ 1 (mod p);

广义欧拉定理

若 a,m 互质，则 a^n≡a^(n mod φ(m)) (mod m)。
若 a,m 不互质，则：
a^n ≡ a^(n mod φ(m)) (n < φ(m))
a^n ≡ a^(n mod φ(m)+φ(m)) otherwise