当前位置：首页 > news >正文

数论中

news 2025/10/9 12:20:34

数论中
- 前言
一些定理
- 欧几里得算法全家桶
- 中国剩余定理及其拓展（CRT）
- 威尔逊定理及逆定理
- 拉格朗日定理（没有用，不需要讲）

数论中

前言

叠甲：本文的许多定义并不是最官方严谨的，但是其实是本质相同的，不过更偏实用一点。有部分内容我并没有写代码验证过，可能有错，希望发现问题的大佬能及时指出。欢迎转载。但如果是全文转载，请附上原文链接。因为博客园与本地的渲染有细微差别，可能会导致有少量格式错误，但应该不会影响阅读，也欢迎大佬指出。

这不是给数论初学者写的博客！这是作者在整理各种数论知识的边边角角梳理出来的文章，不保证内容按照难度递增，而是按照逻辑顺序排列的，相关联的知识点会放在一起。文章分为前、中、后和配套题目与题解四个部分，分成四偏文章的原因是，放在一起会导致非常卡，猜测是因为文章太大了，每个部分之间有着藕断丝连的关系，前三部分是知识点，有着互相依赖的逻辑关系（但是保证不会有自己证明自己的情况出现），第四篇是具体的题目，对提分来说更加重要。建议配合食用。

本文很多内容是我之前写的博客复制过来，修缮了一下，个人感觉比之前写的更本质，更清晰一点，还有不少内容是我这次整理新学的知识。四篇文章总源码超过 100 KB，我认为整理的还是比较全面了，没有涉及到的内容，大概率在数论练习题里的后记里面提及。

合集链接：数论上，数论中，数论下，数论练习题。

一些定理

欧几里得算法全家桶

也称为辗转相除算法。

基础款

易得：$\gcd(a, b) = \gcd(a − b, b)$。

多减几次得：$\gcd(a, b) = \gcd(a \bmod b, b)$

对于边界 $a = 0$，此时的 $b$ 即是最大公约数。

这个复杂度基于取模运算的性质：进行取模运算，要么值不变，要么值至少减半。于是递归次数是 $O(\log n)$ 的。

可以直接使用 c++ 自带的 __gcd 函数。

inline int gcd(int a, int b) {return !b ? a : gcd(b, a%b);}

有一个非常神秘的小常数非递归版本，其实是等价的。

inline ll gcd(ll a, ll b) { while(b) b ^=a ^=b ^=a %=b; return a;}

裴蜀定理

这个是拓欧的前置知识。

内容：$\gcd(a,b)$ 是用 $a$ 和 $b$ 能线性组合出的最小的正整数。这里线性组合是指给 $a$ 和 $b$ 乘上一个系数后加起来。

~~很好感性理解吧~~。对于任意线性组合，一定可以提取出一个 $\gcd(a,b)$ 这个因子出来，这说明 $a$ 和 $b$ 的线性组合一定是 $\gcd(a,b)$ 的正整数倍。还可以思考一下 $a$ 和 $b$ 的最小线性组合还有什么性质。

设 $d$ 为 $a,b$ 的线性组合中最小的一个，设 $d = ma + nb$，$a = dq + r(0 \leq r < d)$

$\therefore r = a - dq = a - q(ma + nb) = (1 - qm)a - qnb$

$\therefore r$ 也是 $a, b$ 的线性组合。

$\because 0 \leq r < d$ 且 $d$ 为 $a, b$ 的线性组合中最小的一个。

$\therefore r = 0$

$\therefore d \mid a$，同理可得 $d \mid b$ 。这说明最小线性组合同时是 $a,b$ 的因子，而刚才我又说明了任何线性组合都是 $\gcd(a,b)$ 的倍数，所以 $a,b$ 的最小线性组合的值就是 $\gcd(a,b)$.

推论：对于方程 $ax+by=c$ ，当 $c$ 不是 $\gcd(a,b)$ 的倍数时，无 $x,y$ 整数解。（这个只用证明的前半段即可得到）

拓展版

此算法可用于解不定方程，用处广泛，可以求非质数意义下的逆元，合并同余方程（埋下伏笔）等。

不定方程：$ax + by = c$ ( $$a,b,c$$ 均为整数，求 $$x,y$$ 的合法整数解）

核心思路：在刚才求 $\gcd$ 的算法的末状态时，求出一组合法的 $x_末,y_末$，又因为有个天才脑洞大开发现可以顺着 $\gcd$ 递归回去，于是可以求出一组 $x,y$ 的特解，再找通解的表达。

具体做法：

当 $c$ 不是 $\gcd(a,b)$ 的倍数，时无 $x,y$ 整数解。（裴蜀定理）

否则：$ax + by = k \times gcd$，两边同时除 k，可先求出 $x/k，y/k$ 的值。

观察 $\gcd$ 的末状态：$a = \gcd,b = 0$。此时只要取 $x_末 = 1, y_末=任意数$ ，等式是成立的。

普通版 $\gcd$ 的转移方法是：$ax + by = \gcd = bx' + (a - {\lfloor a / b \rfloor} b) y'$; ( $\gcd$ 的递归转移)

整理一下：$y = x' - {\lfloor a / b \rfloor} * y', x = y'$

递归回去可得一组 $x/k,y/k$ 的整数解，再乘上 $k$ 就是一组 $x,y$ 的特解。

接下来就是求通解：

假设求出来的特解是 ${x2,y2}$ ，我们要通过这组特解求出另外一组解 ${x1,y1}$.

首先，不管是特解还是通解，肯定满足不定方程

\[\begin{aligned} ax_1 + by_1 &= c\\ ax_2 + by_2 &= c\\ \therefore a(x_1 - x_2) &= b(y_2 - y_1) \end{aligned} \]

两边同除 $\gcd(a,b)$，得 $a'(x_1 - x_2) = b'(y_2 - y_1)$，此时 $a'$ 与 $b'$ 互质

\[\therefore(x_1 - x_2) = k * b', (y_2 - y_1) = k * a' \]

整理一下：$x_1 = k * b' + x_2,y_1 = y_2 - k * a'$ ($k$ 为任意, $x_2,y_2$ 为特解，$x_1,y_1$ 为通解)

代码：

void exgcd(ll a, ll b){if(b == 0) {x = 1, y = 0, gcd = a;return ;}exgcd(b, a % b);tmp = x, x = y, y = tmp - (a/b) * y;
}

用 $exgcd$ 求逆元：$ax = 1 (\bmod p) => ax = 1 + pk => ax - pk = 1$，然后解不定方程。

练习 1 ：解 $n$ 元一次不定方程 $\sum a_ix_i = c$ 。

首先还是用裴蜀定理判掉无解。可以一个一个地做 exgcd ，然后合并。复杂度：不知道。

练习 2 ：还是线性组合 $ax + by = c$ ，保证 $\gcd(a,b)=1$ ，不过这次要求 $x,y$ 都大于等于 0，然后我们反其道而行之，求最大的不可以得到的 c （困难，可以跳过）

问题主要在于 $x,y$ 非负，考虑先手玩一下小数据。

手玩发现答案应该是 $ab-a-b$ 这个神秘的东西。

找一下可以被表示出来的 c 的必要条件。

$ax + by = c$ ，对于这个方程可以直接使用 exgcd 找到一个 x 和 y 的特解。

回忆一下，x，y 的通解分别是 $x=x_0+kb,y=y_0-ka$。

这说明我们可以找到一个 $x \in [0,b-1]$ 。改写不定方程有 $y = \frac{n - ax}b$ 。

$x \le b-1$ ，这时候 $y \ge \frac{n-ab+a}b$。刚才不是猜了个结论吗？试试带入 $n > ab - a- b$ ，可以得到 $y > -1$。

关键的来了，因为 y 是非负整数，所以 y 至少是 0。这里可能有同学会感到不解，考虑 x 不是每次都该取 b - 1，如果 n 比较小，x 也比较小。

先在相当于证明了 n 最大是 $ab -a -b+1$ ，只需要证明 $ab-a-b$ 不能被 $a,b$ 用非负数线性组合出来即可。

假设有 $ax+by=ab-a-b$

整理可得 $\dfrac{a(x+1)+b(y+1)}a=b$。

发现等式成立的一个必要条件是 $\frac {b(y+1)}a$ 是整数，由于 $\gcd(a,b) = 1$，可得 $a\mid (y+1)$。

同理可得 $b\mid (x + 1)$.

不妨设 $(y+1)=k_1a, (x+1)=k_2b$，带入最初的式子化简可得：$k_1+k_2=1$ ，但是由于 $x,y$ 非负，可得 $k_1\ge1,k_2\ge1$ ，假设不成立，故得证。

还有生成函数做法，这等价于计算使得 $[x^n]\dfrac 1{(1-x^a)(1-x^b)} = 0$ 成立的最大的 $n$ 是多少。

还有一个结论是，不可被表示出的 c 的数量是 $\frac{(a-1)(b-1)}2$ 。详见。

这玩意还有几何意义，甚至还可以使用类欧求解！详见

拓欧最大的缺点在于，解方程是通过特定的算法流程来实现的，不是一个显性的式子，不利于后续的推导。拓欧只是一个用于解方程的工具罢了。

类似版

这里指的是类欧。

给定 $n, a, b, c$ ，分别求

\[\sum_{i=0}^{n}\left\lfloor \frac{ai+b}{c} \right\rfloor\,,\ \sum_{i=0}^{n}{\left\lfloor \frac{ai+b}{c} \right\rfloor}^2\,,\ \sum_{i=0}^{n}i\left\lfloor \frac{ai+b}{c} \right\rfloor \]

先求第一个，后面两个的思路类似于第一个。为了方便，我们定义：

\[f(a,b,c,n)=\sum_{i=0}^{n}\left\lfloor \frac{ai+b}{c} \right\rfloor\ \]

整体思路：如果 $a>c$ 或 $b>c$，把 $f(a,b,c,n)$ 转换成 $f(a\bmod c,b\bmod c,c,n)$；否则转化成类似于 $f(c,c-b-1,a,m)$ 的形式。

具体做法：

对于 $a\ge c$ 或 $b\ge c$ 时：

\[\begin{aligned}f(a,b,c,n)&=\sum_{i=0}^n\left\lfloor \frac{ai+b}{c} \right\rfloor\\&=\sum_{i=0}^n\left\lfloor\frac{\left(\left\lfloor\frac{a}{c}\right\rfloor c+a\bmod c\right)i+\left(\left\lfloor\frac{b}{c}\right\rfloor c+b\bmod c\right)}{c}\right\rfloor\text{这一步是关键}\\&=\frac{n(n+1)}{2}\left\lfloor\frac{a}{c}\right\rfloor+(n+1)\left\lfloor\frac{b}{c}\right\rfloor+\sum_{i=0}^n\left\lfloor\frac{\left(a\bmod c\right)i+\left(b\bmod c\right)}{c}\right\rfloor\\&=\frac{n(n+1)}{2}\left\lfloor\frac{a}{c}\right\rfloor+(n+1)\left\lfloor\frac{b}{c}\right\rfloor+f(a\bmod c,b\bmod c,c,n)\end{aligned} \]

对于 $a,b < c$，

\[\begin{aligned} f(a,b,c,n) &= \sum^n_{i=0}\sum^{\left\lfloor \frac{ai+b}{c} \right\rfloor-1}_{j=0} 1\\ &=\sum^{\left\lfloor \frac{an+b}{c} \right\rfloor-1}_{j=0}\sum^n_{i=0}[j \le \left\lfloor \frac{ai+b}{c} \right\rfloor - 1] \end{aligned} \]

转化右边的式子：

\[\begin{aligned} j\le\left\lfloor \frac{ai+b}{c} \right\rfloor -1 &\iff j+1\leq \left\lfloor \frac{ai+b}{c} \right\rfloor \iff j+1\leq \frac{ai+b}{c}\\ &\iff jc+c\le ai+b \iff jc+c-b-1< ai\\ &\iff \left\lfloor\frac{jc+c-b-1}{a}\right\rfloor< i \end{aligned} \]

为了方便表示，令 $m=\left\lfloor \frac{an+b}{c} \right\rfloor$，则

\[\begin{aligned}f(a,b,c,n)&=\sum_{j=0}^{m-1}\sum_{i=0}^n\left[i>\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor \right]\\&=\sum_{j=0}^{m-1}(n-\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor)\\&=nm-f\left(c,c-b-1,a,m-1\right)\end{aligned} \]

递归即可。$O(n\log n)$

对于

\[g(a,b,c,n) = \sum_{i=0}^{n}i{\left\lfloor \frac{ai+b}{c} \right\rfloor}\\ h(a,b,c,n) = \sum_{i=0}^{n}{\left\lfloor \frac{ai+b}{c} \right\rfloor}^2 \]

同样的做法，可以得到：

对于 $ a\ge c$ 或 $b\ge c$

\[g(a,b,c,n)=g(a\bmod c,b\bmod c,c,n)+\left\lfloor\frac{a}{c}\right\rfloor\frac{n(n+1)(2n+1)}{6}+\left\lfloor\frac{b}{c}\right\rfloor\frac{n(n+1)}{2}\\ \]

\[\begin{aligned}h(a,b,c,n)&=\frac{n(n+1)(2n+1)}{6}\left\lfloor\dfrac{a}{c}\right\rfloor^2+(n+1)\left\lfloor\frac{b}{c}\right\rfloor^2+n(n+1)\left\lfloor\dfrac{a}{c}\right\rfloor\left\lfloor\frac{b}{c}\right\rfloor\\&\ \ \ \ +2\left\lfloor\dfrac{a}{c}\right\rfloor g(a\bmod c,b\bmod c,c,n)+2\left\lfloor\dfrac{b}{c}\right\rfloor f(a\bmod c,b\bmod c,c,n)\\&\ \ \ \ +h(a\bmod c,b\bmod c,c,n)\end{aligned} \]

否则：

\[g(a,b,c,n) = \frac{1}{2}[mn(n+1)-h(c,c-b-1,a,m-1)-f(c,c-b-1,a,m-1)]\\ h(a,b,c,n) = m(m+1)n-2f(c,c-b-1,a,m-1)-2g(c,c-b-1,a,m-1)-f(a,b,c,n) \]

其中 $m=\left\lfloor \frac{an+b}{c} \right\rfloor$.

与普通版的共同点在于都运用了取模运算的性质：进行取模运算，要么值不变，要么值至少减半。类欧主要不用用于处理一个有取整的求和式，但是又不能整除分块的式子。

吐槽一下：这玩意写起来是真史，要是不给我公式要我手推出来写代码，不知道得调到什么时候。

万能版

其实是类欧的拓展版。我简单了解了下，目前理解还不够深刻，而且没有写代码，只能简单口糊一下，见谅。

首先看一下类欧这个式子有什么实际含义。

假设有一条直线 $y=\dfrac{ax+b}{c}$。

那么第一象限中满足 $x\le n$ 的那段直线，下方的整点数为：

\[\sum_{i=0}^{n}\left\lfloor \frac{ai+b}{c} \right\rfloor \]

在坐标系中，如果这个直线遇到一条横线，就记录下一个 U ；如果遇到一个竖线，就记录下一个 R ，如果同时遇到横线和竖线（穿过一个整点），就先记录 U 再记录 R 。最后会形成一个由 U 和 R 构成的操作串。例如对于直线 $y=\dfrac{7x+2}3$，其操作序列是：UUURUURUURUUURU.

这里可以把 U 和 R 写成矩阵的形式，表示对答案的影响，然后用向量 $\begin{bmatrix} \sum y\\ y\\1\end{bmatrix}$ 一路扫过去，就可以得到答案。（注意，U 和 R 要有结合律才能使用万欧）

考虑要合并一些 U R 矩形来降低复杂度。

设原问题的答案为 $f(a,b,c,n,U,R)$，U 和 R 就是当前的操作矩阵是什么，因为在进行矩形合并以后，U 和 R 可能会变，所以要记录这两维。

$a\ge c$

则每个 R 前面都有 $a/c$ 个 U，可以直接合并掉，问题转化为 $f(a\bmod c,b,c,n,U,U^{a/c}R)$.

$a< c$

根据欧几里得算法的套路，是时候该交换 $a$ 和 $c$ ，然后就变成第一类问题了。

改写直线解析式，用 y 来表示 x，有 $x=\dfrac{cy-b}a$ 。

但是直接这样子会导致原本是 UR 的操作变成了 RU，于是发扬人类智慧，我们可以直接把直线向左平移一点点（只要平移的幅度小，就不会改变直线下点的数量），这样就变成了：

问题就变成了 $f(c,c-b-1,a,cnt_u,R,U)$，然后还会有一些多余的边界细节的矩形操作，我暂时没太想清楚。

贺来的代码：

Matrix solve (ll p, ll q, ll r, ll l, Matrix a, Matrix b) {if (!l) {return Matrix();}if (p>=q) {return solve(p % q, q, r, l, a, qpow(a, p / q) * b);}ll m = div(l, p, r, q);if (!m) {return qpow(b,l);}ll cnt = l - div(q, m, - r - 1, p);return qpow(b, (q - r - 1) / p) * a * solve(q, p, (q - r - 1) % p, m - 1, b, a) * qpow(b, cnt);
}

万欧的优势在于每次只用考虑如何计算合并矩形操作的贡献，不用重新推式子。代码里就是重载一下矩阵乘法的运算。

中国剩余定理及其拓展（CRT）

处理问题：同余方程，合并同余式

\[\begin{aligned} x &\equiv y_1\pmod {p_1}\\ x &\equiv y_2\pmod {p_2}\\ &…………\\ x &\equiv y_n\pmod {p_n}\\ \end{aligned} \]

使用条件：所有 $p$ 互质
核心思路：硬凑
算法流程

令 $M = \prod p,m_i = M / p_i,m^{-1}_i = m_i^{\varphi(p_i)-1}\bmod p_i$.

可以凑出来 $x = \sum_{i=1}^n y_i \times m_i \times m^{-1}_i + K\times M$ ( $K$ 是任意数，因为 $x$ 有无数个)

现在要证明这个凑出来的式子满足上面每一个同余方程。

对于任意 p ，最后一项都是 0。前面第 i 个式子，因为有所有 $p$ 互质这个条件，所以除了第 i 项，每一项里面的 $m_i$ 都含有 $p_i$ 这个因子，模一下就没了，只有和式里面的第 i 项可以幸存，而 $m_i^{-1}$ 其实就相当于逆元，与 $m_i$ 一乘就变成 1 了，于是诺大一个式子就只剩下 $x \equiv y_i\pmod {p_i}$ ，这就是我们想要的。

理解 CRT 要对逆元有深刻的理解。

一般来说，在 p 都是质数的时候，使用 CRT 比较方便。CRT 相比 exCRT 还有一个优势是，它直接给出了一个公式，可能可以在后续的推到中进一步化简。（？）

很多题目需要合并同余式，所以 CRT 会被大量运用。

拓展版（exCRT）

个人认为 exCRT 比 CRT 自然得多

对 p 没有任何限制。但是此时不一定有解。

例如：

\[\left\{\begin{matrix}x\equiv2 \bmod 4\\ x\equiv3 \bmod 6 \end{matrix}\right. \]

你要是算出一组解来 ~~我请你抽烟~~。exCRT 还具有检验方程是否有解的能力。

考虑只要能一个一个地去合并方程，就可以搞出答案。

考虑合并这两个方程：

\[\left\{\begin{matrix}x\equiv r_1 \bmod m_1\\ x\equiv r_2 \bmod m_2 \end{matrix}\right. \]

\[\left\{\begin{matrix}x = r_1 + k_1 * m_1\\x = r_2 + k_2 * m_2 \end{matrix}\right. \]

上下相减：

\[k_1 * m_1 - k_2 * m_2 = r_2 - r_1 \]

如果 $r_2 - r_1$ 不是 $\gcd(m_1,m_2)$ 的倍数，则无解（裴蜀定理），否则用 exgcd 解方程即可得到 $k_1,k_2$,可以搞出一个 $x_0$ ，通解是 $x = x_0 + k*lcm(m_1,m_2)$，所以合并出来的方程就是 $x\equiv x_0 \bmod lcm(m_1,m_2)$.

写代码小心爆 long long。

这启示我们，可以把一个同余式当成一个不定方程

模板：P4777 【模板】扩展中国剩余定理（EXCRT） - 洛谷。

例题：[P4621 COCI 2012/2013 #6] BAKTERIJE - 洛谷。这是个大粪题。

威尔逊定理及逆定理

用处不是很大？不过这个思想很有趣。

甚至只是七级考点，noip 可以考...

内容

如果 $p$ 是质数，一定有：

\[(p-1)! \equiv -1 \pmod p \]

或者说，把 $p$ 的完全剩余系里面，除了 0 的所有数乘起来等于 $-1$。

主要思想：发现很多数和它们的逆元一乘就没了，有用的数不多

首先发现，如果有 $p$ 是质数，可得 $(a^{p-2})^{p-2}\bmod p \equiv a^{(p-2)(p-2)\bmod p-1 }\equiv a^{-1\times -1}\equiv a$ 。这说明 $a$ 与 $a^{p-2}$ 形成一一对应的关系，又因为对于所有非零数都有 $a\times a^{p-2}\equiv1$，在计算阶乘的时候可以把 $a$ 和 $a^{p-2}$ 这两项扣掉。但是如果 $a\equiv a^{p-2}$，就不能把这两个数同时扣掉。这时候，我们只需要计算 $[1,p)$ 之间，到底是那些数满足 $a\equiv a^{p-2}$，然后只累乘这些数即可。

这些数肯定满足 $x^2\equiv 1\pmod p$ （怎么又是这个经典式子？），满足这个式子的只有 $1$ 和 $-1$ ，然后 $1\times -1 = -1$ ，所以 $(p-1)!\equiv -1\pmod p$。

注意，根据原根那一块的知识，一个数 $a$ 有 $\varphi(p)\over \delta(a)$ 个“逆元”，所以如果那那逆元去论证，而不用 $a^{p-2}$ 来论证，则不严谨

逆定理

对于 $n\ge2$，如果满足 $(n-1)!\equiv -1\pmod n$ ，则 $n$ 是质数。（这好像是我看到的唯一一个可以证明一个数是质数的非定义的定理，看来我还是太孤陋寡闻了）

假设 $n$ 是合数，那么有些数根本就没有逆元，$(n-1)! \equiv -1 \pmod n$ 就可能不成立。现在要证明它一定不成立。

可以换个思路。

考虑反证法，假设 $n$ 是一个合数，且 $(n - 1)! \equiv -1 \pmod n$。

因为 $n$ 是合数，找到 $n$ 的一个在 $(1,n)$ 之间的因子 $d$。

因为 $(n - 1)! \equiv -1 \pmod n$，然后同余式转整除式，有 $n\mid (n - 1)! + 1$。

又有 $d\mid n$ ，容易得到 $d\mid(n-1)!+1$ 。

但是，由于 $(n-1)!$ 里面肯定有一项是 $d$ ，所以 $d\mid (n-1)!$。

这表示 $d$ 是 $(n-1)!+1$ 和 $(n-1)!$ 的公因数，但是 $(n-1)!+1$ 和 $(n-1)!$ 的最大公因数显然是 $1$，于是 $d$ 只能是 $1$。

与假设矛盾，证完了。

例题1

给定一个正整数 $d$，满足 $d\le 2.5\times 10^5$，问是否存在一个正整数 $n$ ，满足 $n\le 2.5\times 10^5$ 且 $d$ 是 $n!+1$ 的次小约数，如果存在请给出任意一个合法的 $n$；否则报告无解。

先考虑打表如何求一个数的次小约数，这是问题突破的关键。

发现最小约数就是分解了质因数后，最小的质数。

所以如果 $d$ 是合数，就不可能是一个数的次小约数，就直接 G 了。

考虑 $d$ 是质数的时候怎么做。

根据威尔逊定理，有 $(d-1)!\equiv-1\pmod d$。

转整除式，有 $(d-1)!+1\mid d$，于是 $d-1$ 就是合法的 $n$，游戏结束。

加强版，但是打表基础练习题，很有趣，但是过于神秘，压表 Trick，认为没有必要讲，题解在这里。

拉格朗日定理（没有用，不需要讲）

没有用的新定理又增加了。

设 $p$ 为素数，对于模 $p$ 意义下的整系数多项式

\[f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0\;(p\nmid a_n) \]

的同余方程 $f(x)\equiv 0\pmod p$ 在模 $p$ 意义下至多有 $n$ 个不同解。

证明：对 $n$ 使用归纳法。当 $n=0$ 时，由于 $p\nmid a_0$，故 $f(x)\equiv 0\pmod p$ 无解，定理对 $n=0$ 的多项式 $f(x)$ 都成立。

若命题对于 $\deg f<n$ 的 $f$ 都成立，由反证法，假设存在一个满足题目条件的 $f$ 在模 $p$ 意义下有着至少 $n+1$ 个不同的解 $x_0,x_1,\cdots,x_{n}$。

可设 $f(x)-f(x_0)=(x-x_0)g(x)$，则 $g(x)$ 在模 $p$ 意义下是一个至多 $n-1$ 次的多项式。现在由 $x_0,x_1,\cdots,x_n$ 都是 $f(x)\equiv 0\pmod p$ 的解，知对 $1\leq i\leq n$，都有

\[(x_i-x_0)g(x_i)\equiv f(x_i)-f(x_0)\equiv 0\pmod p \]
而 $x_i \not\equiv x_0 \pmod p$，故 $g(x_i)\equiv 0\pmod p$，从而 $g(x)\equiv 0\pmod p$ 有至少 $n$ 个根，与归纳假设矛盾。

所以，命题对 $n$ 次多项式也成立，定理获证。