费马小定理

定义

若 pp 是素数，且 gcd⁡(a,p)=1\gcd(a,p) = 1 ，则

ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}

另一种形式：若 pp 是素数，则

ap≡a(modp)a^p \equiv a \pmod{p}

证明

构造集合 A={1,2,…,p−1}A=\{1,2,\dots,p-1\} ，将集合中每一个数都乘以 aa 再模 pp ，即 rn=n×a mod pr_n=n\times a \bmod p ，得到新集合 B={r1,r2,r3,…,rp−1}B=\{r_1,r_2,r_3,\dots,r_{p-1}\} 。

则有 A=BA = B ，这是因为 ∀x,y∈A,  x≠y\forall x,y \in A, \; x \neq y ，有 ax−ay=a(x−y)≢0(modp)ax-ay=a(x-y)\not\equiv 0 \pmod{p}，即 ax≢ay(modp)ax \not\equiv ay \pmod{p} ，故 p−1p-1 个 rnr_n 互不相同。

于是就得到了 BB 其实也是 {1,2,…,p−1}\{1,2,\dots,p-1\}，和 AA 一样。

所以

1×2×⋯×(p−1)≡a×2a×⋯×(p−1)a(modp)1\times 2\times\dots\times(p-1) \equiv a\times 2a\times\dots\times(p-1)a \pmod{p}

即

(p−1)!≡(p−1)!×ap−1(modp)(p-1)! \equiv (p-1)!\times a^{p-1} \pmod{p}

因为 (p−1)!(p-1)! 与 pp 互质，可以两边都除以 (p−1)!(p-1)! 即得证。

欧拉函数

在学习欧拉定理之前，需要先了解欧拉函数（欧拉，怎么到处都是你？）

定义

欧拉函数 φ(n)\varphi(n) 表示所有小于 nn 的数中与 nn 互质的数的个数。

性质

对于质数 pp ，由定义立即有 φ(p)=p−1\varphi(p) = p-1

欧拉函数是积性函数，这意味着若 gcd⁡(a,b)=1\gcd(a,b)=1 有 φ(a×b)=φ(a)×φ(b)\varphi(a\times b) = \varphi(a)\times\varphi(b)

还有很多有趣的性质，感兴趣可以自行了解。

欧拉定理

定义

若 gcd⁡(a,m)=1\gcd(a,m)=1 ，则

aφ(m)≡1(modm)a^{\varphi(m)}\equiv1\pmod{m}

不难发现欧拉定理是费马小定理的推广，费马小定理是欧拉定理当 mm 为质数的特例。

证明

欧拉定理的证明也和费马小定理的证明很像，考虑所有小于 mm 与 mm 互质的数的集合 Φ={c1,c2,…,cφ(m)}\Phi=\{c_1,c_2,\dots,c_{\varphi(m)}\}

再记 aΦ={ac1,ac2,…,acφ(m)}a\Phi=\{ac_1,ac_2,\dots,ac_{\varphi(m)}\}

同上，不难验证 cnc_n 也是互异的，且 cnc_n 与 mm 互质， aΦa\Phi 也是所有小于 mm 与 mm 互质的数的集合。所以

aΦ=Φa\Phi=\Phi

接下来就顺理成章了

∏i=1φ(m)i≡∏i=1φ(m)ai(modm)\prod_{i=1}^{\varphi(m)}i\equiv\prod_{i=1}^{\varphi(m)}ai\pmod{m}

aφ(m)≡1(modm)a^{\varphi(m)}\equiv1\pmod{m}

拓展学习：群论中的拉格朗日定理

应用

由 aφ(m)≡1(modm)a^{\varphi(m)}\equiv1\pmod{m} 可以得到

an≡an mod φ(m)(modm)a^n\equiv a^{n\bmod\varphi(m)}\pmod{m}

  • 在实际应用中，可以使用欧拉定理对指数降幂

1913202(mod101)≡1913202 mod φ(101)≡1913202 mod 100≡192≡58\begin{align*} &19^{13202}\pmod{101} \\ \equiv& 19^{13202\bmod\varphi(101)}\\ \equiv& 19^{13202\bmod 100}\\ \equiv& 19^2\\ \equiv& 58 \end{align*}

  • 欧拉定理还可以应用到RSA加密算法中

拓展欧拉定理

刚刚的欧拉定理好是好，就是有一个条件 gcd⁡(a,m)=1\gcd(a,m)=1 假如不满足这个条件，可以吗？

定义

扩展欧拉定理：

an≡{an mod φ(m)gcd⁡(a,m)=1angcd⁡(a,m)≠1,n<φ(m)a(n mod φ(m))+φ(m)gcd⁡(a,m)≠1,n≥φ(m)(modm)a^n\equiv \begin{cases} a^{n\bmod\varphi(m)}&\gcd(a,m)=1\\ a^n&\gcd(a,m)\neq 1,n<\varphi(m)\\ a^{(n\bmod\varphi(m))+\varphi(m)}&\gcd(a,m)\neq 1,n\geq\varphi(m)\\ \end{cases} \pmod{m}

也就是说，假如 a,ma,m 不互质且 nn 不够大，那降幂。假如 a,ma,m 不互质且 nn 足够大，可以降幂，但是需要在指数上多加一个 φ(m)\varphi(m)

证明

扩展欧拉定理的证明相对就没有其他两个定理简单了，所以我咕咕咕了

参考链接

https://zh.wikipedia.org/zh-hans/%E8%B4%B9%E9%A9%AC%E5%B0%8F%E5%AE%9A%E7%90%86

https://zh.wikipedia.org/zh-hans/%E6%AC%A7%E6%8B%89%E5%AE%9A%E7%90%86_(%E6%95%B0%E8%AE%BA)

https://oi-wiki.org/math/number-theory/fermat/

https://oi-wiki.org/math/number-theory/euler-totient/