【数论】费马小定理与欧拉定理及其证明

_GeorgeAAAADHD_ · 2024-06-05 12:58:14 · 个人记录

本篇博客将讲解费马小定理与欧拉定理的定义，证明与用途。

费马小定理部分：

Part 1. 定义

定义：若 p 为素数，且整数 a 满足 \gcd(a,p)=1，则有 a^{p-1}\equiv 1\pmod{p}。

Part 2. 证明

先来证明两个引理：

引理 1：设 a,b,c 为三个整数，p 为任意正整数，若 \gcd(c,p)=1，且 ac\equiv bc\pmod{p}，则有 a\equiv b\pmod{p}。

证明 1：

其中从第 2 步推到第 3 步是因为 \gcd(c,p)=1，所以 a-b\equiv 0\pmod{p}。

得证。

引理 2：若 \{a_1,a_2,\cdots,a_p\} 是模 p 的一个完全剩余系，且有整数 b 满足 \gcd(b,p)=1，则 \{b\times a_1,b\times a_2,\cdots,b\times a_p\} 也是模 p 的一个完全剩余系。

这里给出完全剩余系的定义：

若有 p 个整数 a_1,a_2,\cdots,a_p 满足对于任意整数 x 有且仅有一个 a_i 使得 x 与 a_i 模 p 同余，则称这 p 个整数 a_1,a_2,\cdots,a_p 是模 p 的一个完全剩余系。

证明 2：使用反证法，如果不满足则一定有 b\times a_i\equiv b\times a_j\pmod{p}。然而因为 \gcd(b,p)=1，所以 a_i\equiv a_j\pmod{p}，显然不满足定义，因此原命题成立。

接下来开始对费马小定理的证明：

设 p 为任意素数，a 为满足 \gcd(a,p)=1 的整数，构造模 p 的一个完全剩余系 S=\{0,1,2,\cdots,p-2,p-1\}，则由引理 2 可得 S'=\{0,a,2a,\cdots,a(p-2),a(p-1)\} 也是模 p 的一个完全剩余系。

则把对 p 取模后为 0 的项去掉后可得 1\times2\times\cdots \times(p-1)\equiv a\times2a\times\cdots\times a(p-1)\pmod{p}，即 (p-1)!\equiv a^{p-1}\times (p-1)!\pmod{p}.

显然 \gcd((p-1)!,p)=1，则由引理 1 得 a^{p-1}\equiv 1\pmod{p}.

得证。

Part 3. 应用

显然最广泛的应用就是求乘法逆元。

乘法逆元的定义：如果一个线性同余方程 ax \equiv 1 \pmod b，则 x 称为 a \bmod b 的逆元，记作 a^{-1}。

当 b 为素数时，有 a^{b-1}\equiv 1\pmod{b}，即 ax\equiv a^{b-1}\pmod{b}，可得 x\equiv a^{b-2}\pmod{b}。

欧拉定理部分：

Part 1. 定义

若 \gcd(a,m)=1，则 a^{\varphi(m)}\equiv 1\pmod{m}。

Part 2. 证明

实际上证明过程与费马小定理的证明基本相同。

既约剩余系：若有 \varphi(p) 个整数 a_1,a_2,\cdots,a_{\varphi(p)} 满足对于任意与 p 互质的整数 x 有且仅有一个 a_i 使得 x 与 a_i 模 p 同余，则称这 \varphi(p) 个整数 a_1,a_2,\cdots,a_{\varphi(p)} 是模 p 的一个既约剩余系。

可以发现既约剩余系仍满足上文的引理 1,2，则对数 p 构造它的一个既约剩余系 S，并对每个数乘上 a 得到其另一个既约剩余系 S'，则有 r_1r_2 \cdots r_{\varphi(p)} \equiv ar_1 \cdot ar_2 \cdots ar_{\varphi(p)} \equiv a^{\varphi(p)}r_1r_2 \cdots r_{\varphi(p)} \pmod{p}，约掉 r_1r_2 \cdots r_{\varphi(p)} 后可得 a^{\varphi(p)}\equiv 1\pmod p。

当 p 为质数时，\varphi(p)=p-1，此时代入欧拉定理可直接得到费马小定理。

Part 3. 应用

暂时未知。