欧拉定理 & 费马小定理

费马小定理¶

若 p 为素数，gcd(a,p)=1，则 ap−1≡1(modp)。

另一个形式：对于任意整数 a，有 ap≡a(modp)。

证明¶

设一个质数为 p，我们取一个不为 p 倍数的数 a。

构造一个序列：A={1,2,3…,p−1}，这个序列有着这样一个性质：

又因为每一个 Ai×a(modp) 都是独一无二的，且 Ai×a(modp)<p

得证（每一个 Ai×a 都对应了一个 Ai)

设 f=(p−1)!, 则 f≡a×A1×a×A2×a×A3⋯×Ap−1(modp)

也可用归纳法证明：

显然 1p≡1(modp)，假设 ap≡a(modp) 成立，那么通过二项式定理有

因为 (pk)=p(p−1)⋯(p−k+1)k! 对于 1≤k≤p−1 成立，在模 p 意义下 (p1)≡(p2)≡⋯≡(pp−1)≡0(modp)，那么 (a+1)p≡ap+1(modp)，将 ap≡a(modp) 带入得 (a+1)p≡a+1(modp) 得证。

欧拉定理¶

在了解欧拉定理（Euler's theorem）之前，请先了解 欧拉函数。定理内容如下：

若 gcd(a,m)=1，则 aφ(m)≡1(modm)。

证明¶

实际上这个证明过程跟上文费马小定理的证明过程是非常相似的：构造一个与 m 互质的数列，再进行操作。

设 r1,r2,⋯,rφ(m) 为模 m 意义下的一个简化剩余系，则 ar1,ar2,⋯,arφ(m) 也为模 m 意义下的一个简化剩余系。所以 r1r2⋯rφ(m)≡ar1⋅ar2⋯arφ(m)≡aφ(m)r1r2⋯rφ(m)(modm)，可约去 r1r2⋯rφ(m)，即得 aφ(m)≡1(modm)。

当 m 为素数时，由于 φ(m)=m−1，代入欧拉定理可立即得到费马小定理。

扩展欧拉定理¶

（读者可能对第二行是有疑问的。这一行表达的意思是：如果 b<φ(m) 的话，那么就不能降幂了。主要是题目中 m 不会太大，而如果 b<φ(m)，那么自然复杂度是可以接受的。而如果 b≥φ(m) 的话，那么复杂度可能超出预期了，这个时候我们才需要降幂来降低复杂度。）

证明¶

证明转载自 synapse7，并进行了一些整理。

1. 命题：a 的从 0 次，1 次到 b 次幂模 m 构成的序列中，存在 r 和 s，使得前 r 个数（即从 a0modm 到 ar−1modm) 互不相同，从第 r 个数开始，每 s 个数就循环一次。

   证明：

   • 由鸽巢定理易证。

     我们把 r 称为 a 幂次模 m 的循环起始点，s 称为循环长度。（注意：r 可以为 0）

     用公式表述为：∀i≥r,ai≡ai+s(modm)

2. 命题：a 为素数的情况，该式成立。

   证明：

   • 若模 m 不能被 a 整除，而因为 a 是一个素数，那么 gcd(a,m)=1 成立，根据欧拉定理，容易证明该式成立。

   • 若模 m 能被 a 整除，那么存在 r 和 m′ 使得 m=arm′，且 gcd(a,m′)=1 成立。所以根据欧拉定理有 aφ(m′)≡1(modm′)。

     又由于 gcd(ar,m′)=1，所以根据欧拉函数的求值规则，容易得到：φ(m)=φ(m′)×(a−1)ar−1，即我们有：φ(m′)∣φ(m)。

     所以 aφ(m′)≡1(modm′),φ(m′)∣φ(m)⇒aφ(m)≡1(modm′)，即 aφ(m)=km′+1，两边同时乘以 ar，得 ar+φ(m)=km+ar（因为 m=arm′）

     所以对于 m 中素因子 a 的次数 r 满足：ar≡ar+φ(m)(modm)。我们可以简单变换形式，得到 推论：

     b>r⟹ab≡ar+((b−r)modφ(m))(modm)

     又由于 m=arm′，所以 φ(m)=φ(ar)φ(m′)≥φ(ar)=ar−1(a−1)≥r（tips：a 是素数，最小是 2，而 r≥1）。

     所以因为 φ(m)≥r，故有：

     ar≡ar+φ(m)≡armodφ(m)+φ(m)(modm)
     ab≡ar+(b−r)modφ(m)≡armodφ(m)+φ(m)+(b−r)modφ(m)≡aφ(m)+bmodφ(m)(modm)

     即 ab≡abmodφ(m)+φ(m)(modm)。

3. 命题：a 为素数的幂的情况，该式成立。

   证明：

   • 不妨令 a=pk，是否依然有 ∀r,ar≡ar+φ(m)(modm)？

     答案是肯定的，由命题 1 可知存在 s 使得 as≡1(modm)，所以 plcm(s,k)≡1(modm)，所以令 s′=sgcd(s,k) 时，我们能有 ps′k≡1(modm)。

     此时有关系：s′∣s 且 s∣φ(m)，且 r′=⌈rk⌉≤r≤φ(m)，由 r′,s′ 与 φ(m) 的关系，依然可以得到 ab≡abmodφ(m)+φ(m)(modm)。

4. 合数：a 为合数的情况，该式成立。

   证明：

   • 只证 a 拆成两个素数的幂的情况，大于两个的用数学归纳法可证。

     设 a=a1a2，其中 ai=piki，而 ai 的循环长度为 si；

     则 s∣lcm(s1,s2)，由于 s1∣φ(m),s2∣φ(m)，那么 lcm(s1,s2)∣φ(m)，所以 s∣φ(m)，r=max(⌈riki⌉)≤max(ri)≤φ(m)；

     由 r,s 与 φ(m) 的关系，依然可以得到 ab≡abmodφ(m)+φ(m)(modm)。

习题¶