一、整除与最大公因数

定理 1：整除的线性组合性质

若

$$d\mid a,\qquad d\mid b,$$

则对任意整数 $x,y$，都有

$$\boxed{d\mid ax+by}.$$

证明：

由整除的定义，存在整数 $k_1,k_2$，使得

$$a=k_1d,\qquad b=k_2d.$$

因此

$$ax+by=(k_1x+k_2y)d.$$

由于 $k_1x+k_2y$ 仍为整数，所以

$$d\mid ax+by.$$

---

定理 2：辗转相除法的基本原理

对任意整数 $a,b,q$，其中 $a,b$ 不全为零，有

$$\boxed{\gcd(a,b)=\gcd(b,a-qb)}.$$

证明：

设 $d$ 为 $a,b$ 的公因数，则

$$d\mid a,\qquad d\mid b.$$

根据定理 1，

$$d\mid(a-qb).$$

故 $d$ 也是 $b,a-qb$ 的公因数。

反之，若

$$d\mid b,\qquad d\mid(a-qb),$$

则

$$d\mid[(a-qb)+qb],$$

即

$$d\mid a.$$

因此，两组整数具有完全相同的公因数，最大公因数也相同。

推论：辗转相除法

反复应用上述等式：

$$\begin{aligned} \gcd(a,b) &=\gcd(b,r_1)\\ &=\gcd(r_1,r_2)\\ &=\cdots\\ &=\gcd(r_{n-1},0)\\ &=r_{n-1}, \end{aligned}$$

其中最后一个非零余数取正值。

因此，最后一个非零余数就是最大公因数。

---

定理 3：裴蜀定理（Bézout's Identity）

对于不全为零的整数 $a,b$，存在整数 $x,y$，使得

$$\boxed{ax+by=\gcd(a,b)}.$$

证明：最小正线性组合方法

考虑集合

$$S=\{ax+by\mid x,y\in\mathbb Z,\ ax+by>0\}.$$

由于 $a,b$ 不全为零，所以 $S$ 非空。

根据正整数的良序性，$S$ 存在最小元素 $d$。

因此，存在整数 $x_0,y_0$，使得

$$d=ax_0+by_0.$$

下面证明

$$d=\gcd(a,b).$$

第一步：证明 $d$ 是 $a,b$ 的公因数。

对 $a$ 进行带余除法：

$$a=qd+r,\qquad 0\le r<d.$$

代入 $d=ax_0+by_0$，得到

$$\begin{aligned} r &=a-qd\\ &=a-q(ax_0+by_0)\\ &=a(1-qx_0)+b(-qy_0). \end{aligned}$$

因此，$r$ 也是 $a,b$ 的整数线性组合。

如果 $r>0$，那么 $r\in S$，但 $r<d$，与 $d$ 的最小性矛盾。

故

$$r=0,$$

即

$$d\mid a.$$

同理可证

$$d\mid b.$$

第二步：证明 $d$ 是最大的公因数。

设 $c$ 是 $a,b$ 的任意正公因数，则

$$c\mid a,\qquad c\mid b.$$

根据定理 1，

$$c\mid(ax_0+by_0),$$

即

$$c\mid d.$$

因此

$$c\le d.$$

由于 $d$ 本身也是公因数，所以

$$\boxed{d=\gcd(a,b)}.$$

证毕。

核心思想：

所有整数线性组合构成集合

$$L=\{ax+by\mid x,y\in\mathbb Z\}.$$

若取其中最小的正整数 $d$，则可证明

$$L=d\mathbb Z.$$

因此，最大公因数实际上就是整数线性组合中最小的正整数。

---

定理 4：互素条件下的整除消去律

若

$$\gcd(a,b)=1,\qquad a\mid bc,$$

则

$$\boxed{a\mid c}.$$

证明：

由裴蜀定理，存在整数 $x,y$，使得

$$ax+by=1.$$

两边同乘 $c$：

$$acx+bcy=c.$$

显然，

$$a\mid acx.$$

又因为 $a\mid bc$，所以

$$a\mid bcy.$$

根据定理 1，

$$a\mid(acx+bcy).$$

故

$$\boxed{a\mid c}.$$

---

二、素数与整除

以下素数均指正素数。

定理 5：素数与任意整数的最大公因数

设 $p$ 为素数，则对于任意整数 $a$，

$$\boxed{ p\nmid a \iff \gcd(p,a)=1 }.$$

等价地，

$$\boxed{ p\mid a \iff \gcd(p,a)=p }.$$

证明：

设

$$d=\gcd(p,a).$$

由于

$$d\mid p,$$

且 $p$ 为素数，所以

$$d=1\quad\text{或}\quad d=p.$$

若 $p\nmid a$，则 $d$ 不可能等于 $p$，故

$$d=1.$$

反之，若

$$\gcd(p,a)=1,$$

则 $p$ 不可能整除 $a$，否则最大公因数应为 $p$。

故结论成立。

---

定理 6：欧几里得引理

若 $p$ 为素数，且

$$p\mid ab,$$

则

$$\boxed{p\mid a\quad\text{或}\quad p\mid b}.$$

证明：

若 $p\mid a$，结论立即成立。

否则，

$$p\nmid a.$$

由定理 5，

$$\gcd(p,a)=1.$$

又因为

$$p\mid ab,$$

根据定理 4，

$$p\mid b.$$

证毕。

推论：

若素数 $p$ 整除有限个整数的乘积，

$$p\mid a_1a_2\cdots a_n,$$

则 $p$ 至少整除其中一个因子：

$$\exists i,\quad p\mid a_i.$$

这一结论可以通过对定理 6 反复应用得到。

---

三、同余与模运算

定理 7：同余的定义及运算性质

定义：

设 $m$ 为正整数，若

$$m\mid(a-b),$$

则称 $a,b$ 模 $m$ 同余，记作

$$\boxed{a\equiv b\pmod m}.$$

性质 1：同余可以相加、相减。

若

$$a\equiv b\pmod m,$$

且

$$c\equiv d\pmod m,$$

则

$$\boxed{a+c\equiv b+d\pmod m},$$

以及

$$\boxed{a-c\equiv b-d\pmod m}.$$

证明只需注意

$$(a\pm c)-(b\pm d) =(a-b)\pm(c-d).$$

右边两项均为 $m$ 的倍数。

性质 2：同余可以相乘。

若

$$a\equiv b\pmod m,$$

且

$$c\equiv d\pmod m,$$

则

$$\boxed{ac\equiv bd\pmod m}.$$

证明：

$$\begin{aligned} ac-bd &=c(a-b)+b(c-d). \end{aligned}$$

由于

$$m\mid(a-b),\qquad m\mid(c-d),$$

根据定理 1，

$$m\mid(ac-bd).$$

故结论成立。

推论：同余的幂运算

若

$$a\equiv b\pmod m,$$

则对任意正整数 $n$，

$$\boxed{a^n\equiv b^n\pmod m}.$$

---

定理 8：同余式的消去律

若

$$ac\equiv bc\pmod m,$$

且

$$\gcd(c,m)=1,$$

则

$$\boxed{a\equiv b\pmod m}.$$

证明：

由同余的定义，

$$m\mid(ac-bc).$$

即

$$m\mid c(a-b).$$

又因为

$$\gcd(m,c)=1,$$

根据定理 4，

$$m\mid(a-b).$$

所以

$$a\equiv b\pmod m.$$

注意：

同余式两边不能无条件地约去相同因子。

只有当这个因子与模数互素时，才能直接消去而保持模数不变。

---

定理 9：模逆元存在的充要条件

设 $m>1$，则

$$\boxed{ \exists x\in\mathbb Z,\quad ax\equiv1\pmod m \iff \gcd(a,m)=1 }.$$

满足上述同余式的 $x$ 称为 $a$ 模 $m$ 的乘法逆元。

证明：

必要性

若存在整数 $x$，使得

$$ax\equiv1\pmod m,$$

则

$$m\mid(ax-1).$$

因此存在整数 $k$，使得

$$ax-km=1.$$

设

$$d=\gcd(a,m).$$

由于

$$d\mid a,\qquad d\mid m,$$

所以

$$d\mid(ax-km).$$

即

$$d\mid1.$$

故

$$\gcd(a,m)=1.$$

充分性

若

$$\gcd(a,m)=1,$$

根据裴蜀定理，存在整数 $x,y$，使得

$$ax+my=1.$$

移项可得

$$ax-1=-my.$$

因此

$$m\mid(ax-1).$$

即

$$ax\equiv1\pmod m.$$

证毕。

重要应用：

在模 $m$ 的运算中，只有与 $m$ 互素的整数才具有乘法逆元。

---

四、费马小定理

定理 10：费马小定理

设 $p$ 为素数，且

$$p\nmid a.$$

则

$$\boxed{a^{p-1}\equiv1\pmod p}.$$

证明：利用非零剩余类的重排

考虑以下 $p-1$ 个整数：

$$1,2,\ldots,p-1.$$

将它们分别乘以 $a$，得到

$$a,2a,\ldots,(p-1)a.$$

下面证明：这 $p-1$ 个整数模 $p$ 的余数恰好是

$$1,2,\ldots,p-1$$

的一个排列。

第一步：证明余数两两不同。

任取

$$1\le i,j\le p-1.$$

假设

$$ai\equiv aj\pmod p.$$

则

$$p\mid a(i-j).$$

由于

$$p\nmid a,$$

由定理 5，

$$\gcd(a,p)=1.$$

应用定理 4，得到

$$p\mid(i-j).$$

即

$$i\equiv j\pmod p.$$

又因为

$$1\le i,j\le p-1,$$

所以

$$-(p-2)\le i-j\le p-2.$$

在这个范围内，$p$ 的倍数只有 $0$，因此

$$i=j.$$

所以当 $i\ne j$ 时，

$$ai\not\equiv aj\pmod p.$$

第二步：证明余数均不为零。

假设存在

$$1\le i\le p-1$$

使得

$$ai\equiv0\pmod p.$$

则

$$p\mid ai.$$

由于

$$p\nmid a,$$

根据欧几里得引理，

$$p\mid i.$$

但

$$1\le i\le p-1,$$

矛盾。

因此，这 $p-1$ 个余数全部非零。

第三步：利用排列关系。

模 $p$ 的非零余数只有

$$1,2,\ldots,p-1$$

这 $p-1$ 个。

前面已经证明

$$a,2a,\ldots,(p-1)a$$

模 $p$ 的余数两两不同且均非零。

所以它们恰好构成上述非零余数的一个排列。

于是两组整数的乘积同余：

$$a\cdot2a\cdot3a\cdots(p-1)a \equiv 1\cdot2\cdot3\cdots(p-1) \pmod p.$$

整理得

$$a^{p-1}(p-1)!\equiv(p-1)!\pmod p.$$

由于 $p$ 是素数，且

$$p\nmid(p-1)!,$$

所以

$$\gcd((p-1)!,p)=1.$$

根据定理 8，同余式两边可以消去 $(p-1)!$，得到

$$\boxed{a^{p-1}\equiv1\pmod p}.$$

证毕。

推论：费马小定理的另一种形式

对任意整数 $a$，均有

$$\boxed{a^p\equiv a\pmod p}.$$

证明分两种情况：

• 若 $p\mid a$，则两边模 $p$ 均为零。
• 若 $p\nmid a$，由费马小定理有

$$a^{p-1}\equiv1\pmod p.$$

两边同乘 $a$，即得

$$a^p\equiv a\pmod p.$$

---

五、定理之间的逻辑关系

整份笔记的主要证明链条为：

$$\begin{aligned} &\text{Linear combinations}\\ &\Downarrow\\ &\text{Bézout's identity}\\ &\Downarrow\\ &\text{Coprime cancellation}\\ &\Downarrow\\ &\text{Euclid's lemma} \end{aligned}$$

将上述结论用于同余运算：

$$\begin{aligned} &\text{Coprime cancellation}\\ &\Downarrow\\ &\text{Cancellation of congruences}\\ &\Downarrow\\ &\text{Modular inverses} \end{aligned}$$

最后，利用欧几里得引理证明非零余数的排列性质，再通过同余消去律，得到费马小定理。

整份笔记最关键的思想：

1. 整除关系在线性组合下封闭。
2. 最大公因数可以表示成整数线性组合。
3. 互素条件允许消去整除式或同余式中的因子。
4. 与素数互素的整数乘法会重排全部非零剩余类。

这四个思想构成了从整除理论到费马小定理的主要证明路线。