一个定理补了我五块数学短板

这两天看陶哲轩 15 岁写的数学学习心得，遇到了威尔逊定理，发现自己无法独立证明，在 AI 的帮助下，补了五块数学短板。

书中只是作为一个例子，一句话带过，没有展开。前几年自学数论概论的时候，有看到过。翻书仔细查看，发现是一道习题，没提威尔逊定理这个名字，我在旁边做了标注。大概当年也没做出来，上网查了，留下了标记。如今 36 岁，已经没有了年轻时的恐慌感与挫败感。

年轻时候，面对恐慌和挫败，只知道苦思冥想，跟自己较劲，来证明自己的智力良好。既不愿低下头去向别人请教，也不知道广泛阅读去寻找方法，还懒得做归纳和总结。

空闲时间用数学来做思维训练，发现短板，体验到数学的美感，是一种美好的人生体验。

威尔逊定理

$(n - 1)! + 1$ 是 $n$ 的倍数，当且仅当 $n$ 是素数。

短板一：缺乏模运算的训练

证明这个定理的关键洞察，是配对出一些乘积，论证余数为 1。

具体来说，当 $n$ 是素数时，$1$ 到 $n - 1$ 这 $n - 1$ 个数字，除了 $1$ 和 $n - 1$ 之外，其他数字两两配对相乘，除以 $n$ 余数为 1。

前些年，走马观花地了解了群的概念，知道模素数的余数构成了一个循环群，隐约需要这块的工具，但并没有真正理解余数，没有掌握模运算的法则，无法获得这个关键洞察。

走马观花是为了构建知识网络，建立知识结构和索引，为了估算，划定范围，进行定性分析。

深入钻研一个问题，把涉及的每个细枝末节都弄清楚，才能精算，才会推导，进行定量分析。

回到题目，把 $n$ 整除，说成是 $n$ 的倍数，也有一定迷惑性。容易写出 $n \cdot k$ 这样的东西，试图去寻找代数与分析的方法。

我看到 $(n - 1)! + 1$，尝试去做多项式展开，结果发现循环了， $1 = n - (n - 1)$。

接下来，就不知道怎么下手了。只好求助 AI，来补上知识和思维上的短板。

不理解余数，就是没有把这个概念的性质、特点、运算仔细考察过。

什么是余数呢？余数是除法运算中，整除不尽的剩余部分。理解余数，不要总想着实数域那一套，最终都归结到一个标量上，最好就是要建立起一个四元组的概念，也就是 $(被除数a, 除数d, 商q, 余数r)$。余数一定小于除数，余数的取值范围就是 $[0, d - 1]$。被除数一定大于等于余数。除数与商相乘可以看作一个线性组合项 $d \cdot q + r = a$。

理解概念的过程，就是逐个考察每个元素、考察元素之间的关系、考察元组整体的过程。

考察什么呢？考察大小、范围、排列次序、站在多个视角看一个关系和整体、用多种描述形式看一个关系和整体。

什么是掌握了运算法则呢？就是对加、减、乘、模的混合运算，形成了下意识的反应，而不需要临时推导，或者知道怎么做临时推导。

这个问题里的阶乘看着很唬人，说白了，是连续的乘法运算，最后还有个加一，也就是 $n - 2$ 次联乘，一次加法。

从加法的求模运算知道，$(n - 1)! + 1$ 要整除 $n$，后半部分余数显然是 $1$ 了，前半部分 $(n - 1)!$ 除以 $n$ 的余数必然要等于 $n - 1$。

加法模的运算法则，概括说就是，和的余数等于余数和的余数。更严谨地说，

设：
$$ a = q_1 m + r_1,\quad 0 \le r_1 < m $$
$$ b = q_2 m + r_2,\quad 0 \le r_2 < m $$
则两式相加得
$$ a + b = (q_1 + q_2)m + (r_1 + r_2) $$
因此 $a + b$ 除以 $m$ 的余数，就等于 $(r_1 + r_2)$ 除以 $m$ 的余数，即
$$ (a + b) \bmod m = (r_1 + r_2) \bmod m $$
也即
$$ \boxed{(a + b) \bmod m = \big((a \bmod m) + (b \bmod m)\big) \bmod m} $$

加法部分弄清楚了，接下来，就是乘法部分。

乘法模的运算法则，类似地，概括说就是，积的余数等于余数积的余数。严谨的式子就不写了。回到定义，简单的多项式展开，就能得出这个结论。

$$ \boxed{(a \cdot b) \bmod m = \big((a \bmod m) \cdot (b \bmod m)\big) \bmod m} $$

在 $(n - 1)!$ 中，首尾两个数，$1$ 和 $n - 1$，相乘除以 $n$ 余数为 $n - 1$，正是想要的，于是就想，剩下的 $n - 3$ 项相乘余数如果等于 $1$，那么就得证了。

全部求出来 $n - 3$ 项的乘积也不太可能，如果能两两配对找找规律，可能比较可行。

大于 $2$ 的素数，必然是奇数，$n - 3$必然是偶数，凑成对是可能的。

什么叫做两个数积的余数是 $1$ 呢？形式化表示就是 $(a \cdot x) ≡ 1 (\bmod n) $。

如果对最大公约数定理（裴蜀定理）和辗转相除法理解透彻，就会联想到 $(a \cdot x + n \cdot y) ≡ 1 (\bmod n) $。

短板二：没理解辗转相除法

在算法导论中，辗转相除法是递归算法的经典案例。要透彻理解，只做一步步的推导是不够的，合上书，又忘得一干二净，回头也想不起，这个推导到底要干什么，得出了什么结论。

数论的核心是素数，而素数定义的核心是因子，也叫因数。

辗转相除法，是为了找两个数的最大公约数，也就是两个数的最大的公共因数。

算法导论书上，偏重讲递归的思想，以及步数计算，也就是复杂度的计算，却没有交代一个重要事实，就是裴蜀定理描述的，最大公约数是这两个数的线性组合。

辗转相除法，每次相减，换被除数和除数，都能表示成最初两个数的线性组合。

要理解线性组合，需要些代数的知识，线性代数分支就是在讨论线性关系。

裴蜀定理一般放在应用上，也就是判定线性组合是否有整数解，以及整数解怎么求。

回到问题，$(a \cdot x + n \cdot y) ≡ 1 (\bmod n) $ 是裴蜀定理的一个特殊情况，也就是两个数互素的情况。

$ n $ 是素数时，小于 $ n $的每一个数 $a$ 都跟它互素。互素的两个数最大公约数就是 1，于是 $ x $ 必然有整数解，并且能用辗转相除法算出来。

这里虽然说 $ x $ 有整数解，可怎么说明整数解小于 $ n $，不同于 $ a $，且唯一呢？

根据乘法模运算的性质，知道整数解中一定存在小于 $ n $ 的数，而且可以发现，线性项上的元素 $ a $ 和 $ x $ 是对称的，元素在 $[1, n - 1]$ 的集合中封闭。

要论证 $a \cdot x ≡ 1 (\bmod n) $ 小于 $ n $ 的解中，$x = a$ 只有两个解，而 $x \ne a$ 的解具有唯一性，是另一个令我卡住，难以下手的地方。

短板三：恐惧唯一性的证明

心理上，我总是恐惧唯一性、只有几个的论证。这种问题，一经提醒，或者看了答案，发现没有一个知识点陌生，但自己独自面对，却茫然无措。非常打击人的信心。

这个根源，其实是一项重要的思维习惯没有建立好。

也就是，要有意识地建立起不同形式的可操作性。

比如 $a \cdot x ≡ 1 (\bmod n) $，意味着同余方程要找解，做裴蜀定理公式带入、辗转相除。

而它的变形 $a \cdot x - 1 ≡ 0 (\bmod n) $，也就是 $ n $ 整除 $a \cdot x - 1$ 意味着要找因数，做因数分解、算术定理。

看到一个形式，要想到它还会有其他变形，而不同的变形具有不同的可操作性。

没有形式的时候，要尝试形式化，写不出形式的时候，要分解可量化因素。

比如陶哲轩举的例子，要解决的问题是“在一个城市找一家旅馆过夜”，需要把条件约束都找出来，“在5公理范围内，找到一家有空闲的旅馆，并且住一晚的房费不能超过100美元”。

形式化是在定义问题，在建模，而解决问题，是在做形式变换，变换不同的形式，才有不同的工具可以用。分清楚是缺量化因素，还是缺可操作的形式，还是有了形式，不知道操作工具。

回到问题，把同余方程变成整除，就意味着对 $a \cdot x - 1$ 分情况讨论，做因式分解。

当 $x = a$ 时，也就是说，要论证 $ n $ 整除 $a ^ 2 - 1 = (a - 1)(a + 1)$ 的数只有两个。

首先，在 $ a < n $ 的范围内，$ a = 1 $ 和 $ a = n - 1 $是两个解。

接下来，要说明 $ 1 < a < n - 1 $ 的数中，没有解。因为 $n$ 是素数，若 $n$ 整除乘积，则 $n∣(a−1)$ 或 $n∣(a+1)$。但 $1<a<n−1$ 时，$0<a−1<n−2$ 且 $2<a+1<n$，两者都不可能被 $n$ 整除。矛盾。

当 $x \ne a$ 时，$a \cdot x ≡ 1 (\bmod n) $ 解存在，已经由裴蜀定理保证。现在要说明唯一性，就要用到反证法。

假设有两个数 $ x_1 \ne x_2 $ 都是方程的解，那必然有两个等式成立

$$ a \cdot x_1 ≡ 1 (\bmod n) $$

$$ a \cdot x_2 ≡ 1 (\bmod n) $$

两式相减得到

$$ a \cdot (x_1 - x_2) ≡ 0 (\bmod n) $$

也就是说$n$ 要整除 $a \cdot (x_1 - x_2)$，$a$ 跟 $n$ 互素，所以只能是 $n$ 整除 $x_1 - x_2$。由于两个数都小于 $n$，差也小于 $n$，因此只能 $x_1 - x_2 = 0$，这与 $ x_1 \ne x_2 $ 的假设矛盾。故解唯一。

至此，$n$ 是素数的充分性得证。

短板四：卡在逆否命题的提前

接下来，要证明必要性，也就是已知 $n$ 整除 $(n - 1)! + 1$，能推出 $n$ 是素数。

判断素数的方法，从定义上讲，需要做枚举、试除找因子，没有更简单的确定性的判定方法。

于是，来看逆否命题，也就是当 $n$ 不是素数时，$n$ 不能整除 $(n - 1)! + 1$。

如果逆否命题证明成立，那么原命题也成立。

这里又有一个坎，虽然我从前没觉得，但现在仔细思考，发现这当中，大有文章。

这里讲的原命题，其实是一个推理，是两个直言命题的复合。

用现代形式逻辑讲，是 p真 ⇒ q真，与逆否命题 非q真 ⇒ 非p真 等价。

远离校园考试，面对现实生活，会发现形式逻辑的一个前提，把它作为一个定义。你要从形式上接受 ⇒ 符号意味着左边是右边的充分条件，也就是没有其他的任何例外因素存在了。

这就是一种形式上的定义，跟现实中存不存在、是不是没关系。

举例来说，p表示天下雨，q表示地湿，当室外的一块没有遮挡的地，直接受天下雨的影响时，这个推理就是成立的。

在实际中应用时，理解的关键，在于一旦用了这个逻辑形式，那么就意味着天下雨，是地湿的充分条件，这时候，就不要再说，如果这块地在室内，或者在火星上、月球上之类的话了。

这其实反映出，数学思维、形式逻辑的本质，就是抽象，从现实的众多因素中剥离出关注的那个因素。这里的关键因素，就是充分性这个概念。在抽象的、封闭的环境中，容易看到这个充分性，但现实中，却没法讲什么条件就是充分的。

许多人的注意力放不到语言指出的那个抽象概念的时候，是极其绝望的，因为注意力放在一个抽象概念上，本质是一种主观体验，别人只能帮你创造理解的条件，但代替不了你自己体验到那个概念。

曾经在网上，看到一个小朋友一遍遍数苹果数到她妈崩溃。问她3个苹果加5个苹果等于几，她母亲越问她越怕，她的注意力放不在“加”上，也放不到“几“上，水汪汪的大眼睛只顾盯着愤怒的母亲的脸。她的脑神经，大概很长一段时间内，就要把数学作业、数苹果，跟内心那种畏惧的情绪给关联在一起了。

人的身体，不管是思维、口齿、手脚，都具有很强的可塑性。内在的正循环的建立，需要成就感，需要热爱，需要信心，也需要鼓励，需要耐心，才能扛得住外部的摩擦，与内在的混乱。

短板五：没抓住反证法的要点

逆否命题的结论让证明不能整除，这个形式没法操作，于是，就想到利用反证法，假设结论的否定成立，会推出矛盾，因此否定假设，肯定假设的反面。

反证法，其实做了三件事。第一，让形式可操作。第二，给证明多加了一个条件。第三，肯定矛盾律、排中律的必然性。

让形式可操作，在短板三那里讲过了。相比于“不能整除”，“整除”可以利用模运算，可以利用因数分解等等形式变化和可操作工具。

给证明多加一个条件，可以这样来理解：

逆否命题要证明 非q真 ⇒ 非p真，而反证法转换成了 非q真且 p真 ⇒ 矛盾，因为不能有矛盾，所以 p真不成立。显然，这里 非p真 从结论走到了条件上，相当于多了一个条件。

这种讲法是很多初高中老师的讲法，但这里其实有两个东西没说清。第一，什么是矛盾？第二，p真不成立，难道就意味着 非p真 成立吗？

第一步是在利用矛盾律，制造矛盾。矛盾律就是要承认 p 与非p 不能同时为真。

第二步是在利用排中律，做最后的判断。排中律要承认 p 或非p 必然有一个真。

综合来说，就是要么 p真，要么 非p真，没有其他情况。

把 非p真 拿到条件上，是在制造矛盾，但造出的矛盾是什么呢？

实际上，可以说是 非q真且 p真 ⇒ (非q 且 p)真，若发现 (非q 且 p)假，那么就跟 (非q 且 p)真 矛盾，p真也就不成立。

回到题目上，非q，是说 $n$ 不是素数，这个条件不好利用，转换一下，也就是 $n$ 是合数。

$n$ 是合数意味着可以被分解成至少两个非 $1$ 和非 $n$ 的因数，即 $n = a \cdot b$，其中$1 < a, b < n$。

p真，是说 $n$ 整除 $(n - 1)! + 1$ 成立。

可当 $n$ 分解成 $1 < a, b < n$，也就意味着，$n$ 能整除 $(n - 1)!$。既然 $n∣(n−1)!$，那么 $(n−1)!≡0(\bmod n)$。两边加 1，由加法模运算法则得 $(n−1)!+1≡1(\bmod n)$，即余数为 1。但这与“$n$ 整除 $(n−1)!+1$”矛盾。于是，p假，推出 (非q 且 p)假，与结论矛盾，因此假设 p真不成立，那么 非p真 成立。

至此，$n$ 是素数的必要性也得证。