斐波那契数列百科全书

Jacken · 2026-02-05 23:32:45 · 算法·理论

本篇文章使用 f 来表示斐波那契数列，用 l 来表示卢卡斯数列，用艾弗森括号 [x] 来表示命题 x 是否成立，若无特殊情况，用 \left(\frac{a}{p}\right) 表示 a 是否是 p 的二次剩余（如果遇到右括号带有指数，那么就是特殊情况，这表示的并不是二次剩余，而是普通分数），本文中的 i 并非虚数。

前言

别看本文似乎短小精悍，其实是因为用了很多伸缩框，如果全部展开是相当之长的，本文涵盖许多关于斐波那契数列的定理、性质、恒等式，以及一些有关的算法，同时如果在证明时用到与斐波那契数列关系不大的东西在这篇文章中也都会进行阐述及证明，对新人非常的友好。这篇文章不仅适合信息学奥林匹克竞赛选手，还适合纯数学爱好者。

而本蒟蒻作为一个 \LaTeX 超级萌新，在极长的文章不中不乏有展示效果没那么好看的公式，但恕本人无能，不知道怎么样才能更好看，所以只能这样了，请大家见谅。

最后，本蒟蒻思考加写文章总共耗费 20 天时间，边写边想，而且这篇文章的大部分证明都是用本蒟蒻的猪脑想出来的，看我那么辛苦，麻烦给一个小小的赞吧……

本文章的皮萨诺周期部分还有最后一个证明没有写，因为太难了，本蒟蒻目前还不会，但由于本蒟蒻已经红温，先这样提交审核了，等后面缓过来了再更新。

::::

定义

斐波那契数列初始为 f_0 = 0,f_1 = 1，然后对于 \forall n \ge 2,\ f_n = f_{n-1}+f_{n-2}。

通项公式

::::success[证明] 考虑寻找满足 \forall n \in \mathbb{N},\ f_n = r^n 的指数解 r。

我们将 r 代入 f_n = f_{n-1}+f_{n-2} 可得 r_n = r_{n-1}+r_{n-2}，于是 r^n-r^{n-1}-r^{n-2} = 0，我们考虑提公因式 r^{n-2}，可得：

然后对于 f_n，令 \alpha = \frac{1+\sqrt{5}}{2},\beta = \frac{1-\sqrt{5}}{2} 可得通解 f_n = A \alpha+B \beta。

考虑对于 n = 0 时，f_n = 0 = A+B，所以 A = -B。

当 n = 1 时，f_n = A \alpha+B \beta = 1，因为 A = -B 并且 \alpha-\beta = \sqrt{5}，所以 A \alpha+B \beta = A\sqrt{5} = 1，即：

所以：

::::

加法恒等式

前 n 项和：

::::success[证明] 使用数学归纳法，在基础 0 的情况下：

成立，再考虑此时我们已知：

我们需要证明：

考虑到将 f_{m+3} 展开为 f_{m+1}+f_{m+2}，可得只需要证明：

显然 f_{m+1}-1 = \sum_{i = 0}^{m-1} f_i，所以只需要证明：

显然 f_{m+2} = f_{m+1}+f_m，所以只需要证明：

因为 \sum_{i = 0}^{m-1} f_i+f_{m+1}+f_m = \sum_{i = 0}^{m+1} f_i，所以只需要证明：

这显然成立。

至此，证毕。 :::: 平方和：

::::success[证明] 依旧使用数学归纳法，对于基础 0：

成立，考虑我们此时已知：

如何证明：

因为我们知道对于 m 这个命题是成立的，所以可以两个等式相减，得出我们只需要证明：

而我们将 f_{m+2} 展开成 f_{m+1}+f_m，于是变为：

这显然成立。

至此，证毕。 :::: 下标奇偶性求和：

::::success[证明] 先考虑第一个式子，依旧使用数学归纳法，对于基础 0：

成立，考虑我们此时已知：

如何证明：

依旧将 m 的等式和 m+1 的等式相减，得出我们只需要证明：

考虑将 f_{2m+3} 拆成 f_{2m+1}+f_{2m+2}，于是变成：

这显然成立。

对于第二个式子也是基本一样的方法，就不多说了。 :::: 项与项的关系：

::::success[证明] 我们固定 n，然后对 m 进行归纳。

对于基础 0 和 1，分别为 f_n = f_1f_n+f_0f_{n-1} = f_n 以及 f_{n+1} = f_2f_n+f_1f_{n-1} = f_n+f_{n-1}，均成立。

考虑此时我们已知：

我们要证明 m = k+2 时此命题是否成立，我们已知 f_{k+2+n} = f_{k+1+n}+f_{k+n}，于是根据已知条件进行推导：

这就是 m = k+2 时的恒等式形式。

至此，证毕。 :::: 倍增法前置恒等式：

::::success[证明] 先证明第一个式子。

利用我们之前已经证明的项与项的关系：

令 m = n = k，即可得到：

此时我们再进行化简：

我们再对 f_k(2f_{k+1}-f_k) 进行化简：

于是我们有 f_{2k} = f_k(2f_{k+1}-f_k)，至此，第一个式子证毕。

再证明第二个式子。

考虑使用数学归纳法，对于基础 0，f_1 = f_1+f_0 = 1+0 = 1，成立。

考虑我们已知：

怎么证明 f_{2(k+1)+1} = f_{k+1}^2+f_{k+2}^2 呢？

显然 f_{2(k+1)+1} = f_{2k+3}，并且我们根据斐波那契数列的递推式有 f_{2k+3} = f_{2k+2}+f_{2k+1}，而 f_{2k+2} 可以转化成 f_{2(k+1)}，然后通过第一个式子进行展开，并且 f_{2k+1} 也是已知的，考虑进行展开：

显然我们把 f_{k+1}^2 提出来与要证明的式子中的 f_{k+1}^2 进行对应，于是我们只需要证明：

进行一波推导：

这显然成立，至此，证毕。 ::::

卡塔兰恒等式

该恒等式还有一个常用的弱化恒等式，它有自己的名字，卡西尼恒等式。

它通常写作：

这显然是卡塔兰恒等式在 r = 1 时的情况。

不过有时，卡西尼恒等式也会写成：

这与上面的式子显然等价。 ::::success[证明] 我们利用通项公式，令：

然后将 f_n^2,f_{n-r}f_{n+r} 分别列出（设 A = \alpha^n,B = \beta^n，通过手磨很容易知道 \alpha\beta = -1,\beta = -\alpha^{-1}）：

此时我们考虑 (-1)^r[\alpha^{2r}+\beta^{2r}-2(-1)^r] 和 (-1)^r(\alpha^{2r}+\alpha^{-2r})-2 的关系，很显然是相等的，化简一下就能证明了，并且这两个东西是等于 (-1)^r \times 5f_r^2于是，我们就可以把 \frac{(-1)^{n}[(-1)^r(\alpha^{2r}+\alpha^{-2r})-2]}{5} 转化为 \frac{(-1)^n(-1)^r \times 5f_r^2}{5}，化简一下得到 (-1)^{n+r}f_r^2，因为 (-1)^{n+r} = (-1)^{n-r}，所以可以变成 (-1)^{n-r}f_r^2，与该恒等式相同。

至此，证毕。 ::::

组合意义

• \forall n \in \mathbb{N}^+,\ f_n = \frac{l_{n-1}+l_{n+1}}{5}
• \forall n \in \mathbb{N},\ f_{2n} = f_n \times l_n

我们先证明第一个关系。

显然将 f_{n+1} 转化成 f_n+f_{n-1} 之后很容易得出 f_{n-1}+f_{n+1} = f_n+2 \times f_{n-1}。

也就是我们只需要证明 l_n = f_{n-1}+f_{n+1} 即可。

考虑使用数学归纳法。

对于基础 1，我们有 l_1 = f_0+f_2 = 1，成立。

再考虑我们已知：

如何证明 l_{m+1} = f_m+f_{m+2}？

因为我们已知 l_m = f_{m-1}+f_{m+1}，而我们要证明的是 l_{m+1} = f_m+f_{m+2}，直接用两式相减法，左边很容易得到 l_{m-1}，但是右边比较困难（其实也很简单），我们来一步一步推导：

很显然，因为对于 i \in [1,m] 的 l_i 我们是已知的，所以 l_{m-1} = f_{m-2}+f_m，这正好和我们上面要证明的式子相等。

至此，第一个关系证毕。

依旧使用数学归纳法。

对于基础 1，我们有 f_1 = \frac{l_0+l_2}{5} = \frac{5}{5} = 1。

考虑我们已知：

那么如何证明 f_{m+1} = \frac{l_m+l_{m+2}}{5}？

根据已知的 f_m = \frac{l_{m-1}+l_{m+1}}{5}，我们依旧使用两式相减法。

很显然，左边是 f_{m-1}，那右边呢？我们来推一下：

而根据已知条件，我们有 f_{m-1} = \frac{l_{m-2}+l_m}{5}，这与我们推的式子相同。

至此，第二个关系证毕。

最后证明第三个关系。

其实很简单，根据斐波那契数列和卢卡斯数列的通项公式，我们有：

于是我们直接相乘：

至此，第三个关系证毕。 ::::

更相减损术的核心及证明

更相减损术是一种算法，但它的核心是一个数论性质：

::::success[证明] 令 d = \gcd(m,n),d' = \gcd(m-n,n)，显然：

我们先证明 d \mid d'，也就是 d 是 m-n 和 n 的公因数。

这个其实超级简单，因为 d \mid m 并且 d \mid n，所以根据数论基本原则我们可以得到 d \mid m-n，如果实在要证明这个基本原则，我们可以令 m = qd,n = q'd，因为 m \ge n，所以 q \ge q'，即 m-n = (q-q')d，显然是 d 的倍数。

至此，d \mid d' 证毕。

接着再证明 d' \mid d，也就是 d' 是 m 和 n 的公因数。

因为 d' \mid m-n 并且 d' \mid n。所以 d' \mid m-n+n，化简一下得到 d' \mid m，由于原本就有 d' \mid n，所以命题得证。

一个数论基本定理的证明

::::success[证明] 我们令 d = \gcd(a,b)，那么存在整数 m,n 使得：

我们已知 a \mid x 并且 b \mid x，我们将 a,b 进行替换后，很容易得到：

我们容易能想到将两式合并，得到 dmk = dnt，两边同时除以 d，可得 mk = nt，根据简单性质我们有 m \mid nt，而又因为 m,n 互质，所以 m \mid t，这里我们设 t = mq，则代入 mk = nmq 得到 k = nq，于是我们就有了：

而：

因为 x = (dmn) \times q，所以：

至此，该定理证毕。 ::::

上一个定理的扩展

::::success[证明] 我们先改写一波：

很容易发现，这不就是上一个定理的基本变形吗？

至此，该定理证毕。 ::::

数论性质

该命题也有一个常用的变形弱化命题：\forall m \in \mathbb{N}^+,n \in \mathbb{N},\ [m \mid n] \Leftrightarrow [f_m \mid f_n]，只要证明了上面那个原命题成立，这个变形弱化命题也一定成立。 ::::success[证明] 根据之前我们得出的：

先交换一下 m 和 n，得出：

我们令 A = f_{m+n},B = f_n，那么：

根据 \gcd 的定义，我们有：

我们取 x = f_mf_{n+1},k = f_{m-1}，则：

所以：

因为 \gcd(f_{n+1},f_n) = 1，所以：

接下来一步便是魔法，我们知道这对于 \forall m,n \in \mathbb{N},m+n \ne 0 都是成立的，也就是我们可以对 m 和 n 进行任意更改，我们为了方便，如果 n>m，交换 n 和 m，也就是我们需要保持 m \ge n，接着我们令更改后的 m,n 为 m',n'，则 m' = m-n,n' = n，此时我们就可以得出：

此时回到我们的原命题：

考虑使用数学归纳法，对于基础：

• 当 m = n 时 \gcd(f_m,f_n) = f_m,f_{\gcd(m,n)} = f_m 成立。
• 当 m>0,n = 0 时 \gcd(f_m,f_n) = \gcd(f_m,f_0) = f_m,f_{\gcd(m,n)} = f_m，成立。
• 当 m = 0,n>0 时与上同。

考虑对于一组 m,n \in \mathbb{N}^+，比它的 m+n 小的 m,n 已经全部成立，我们要证明这组 m,n 也成立。

根据我们刚刚推出的式子：

我们很容易发现 m-n+n = m，而 m<m+n，所以 \gcd(f_{m-n},f_n) = f_{\gcd(m-n,n)} 已经成立了，于是我们便得出：

根据更相减损术，可得：

所以：

至此，证毕。 ::::

• 我们如果定义 P(x) 表示 x 是否是素数，则 \forall 4 \ne n \in \mathbb{N},\ P(f_n) \Rightarrow P(n)。 ::::success[证明] 我们很显然可以将该命题转化为：我们如果定义 C(x) 表示 x 是否是合数，则 \forall n \in \mathbb{N},\ C(n) \Rightarrow C(f_n)。

对于那些既不是合数也不是素数的非负整数下标，我们一一验证之后就可以发现，没有一个对应的斐波那契数是素数，所以此次命题转化完全正确。

运用第一个性质的变形弱化命题：

那么当 n 为合数时，一定存在 a,b>1，使得 ab = n，并且根据那个变形弱化命题，我们知道 f_a \mid f_n 并且 f_b \mid f_n。

接下来我们可以使用反证法。

我们要使 n 为合数时，f_n 可能是素数，所以 f_a 可以等于 1 或 n，但尽管 f_a 可以等于 1 或 n，不过如果 f_a = n 我们就可以通过魔法交换重新让 f_a 等于 1，所以我们只需要考虑 f_a = 1 的情况。

而只有在 a = 1 或 a = 2 时 f_a = 1，但是之前规定 a>1，所以 a 只能取 2。

当 a = 2 时，n = 2b，我们根据斐波那契数列与卢卡斯数列的关系恒等式：

而在 b>2 时，f_b \ge 2,l_b \ge 4，所以 f_{2b} 即 f_n 一定为合数。

不过 b = 2 时是一个特例，因为此时 f_b = 1，而此时 n = 4，这也刚好对应该命题的 n \ne 4 的要求。 ::::

齐肯多夫定理

对于任意一个非负整数，它可被唯一表示为若干个（也可以是一个）不同且不相邻的斐波那契数列之和，这个表示被称为齐肯多夫表示。

为了证明它，先给出一个前置定理：

对于所有 n \in \mathbb{N}，用不超过 f_n（并且严格不相邻）的斐波那契数能表示的最大整数是 f_{n+1}-1。 ::::success[前置证明] 考虑使用数学归纳法，对于基础 0，最大也只能取 f_0 = 0，而 f_{1}-1 = 0，成立。

考虑我们已知：对于所有 i \in [0,m-1]，此命题成立。

如何证明对于 m，此命题成立呢？

考虑我们是否选择 f_n，分类讨论：

• 当我们选择了 f_n 时，我们就不能选择 f_{n-1}，最多只能选择 f_{n-2}，而根据已知的条件，用不超过 f_{n-2}（并且严格不相邻）的斐波那契数能表示的最大整数是 f_{n-1}-1，再加上 f_n，就是 f_{n+1}-1。
• 当我们没有选择 f_n 时，可用的最大数是 f_{n-1}，而根据已知的条件，用不超过 f_{n-1}（并且严格不相邻）的斐波那契数能表示的最大整数是 f_n-1。

将两者答案取 \max，可得值为 f_{n+1}-1。 :::: ::::success[证明] 先证明其存在性。

考虑使用数学归纳法，对于基础 0，显然可以取 f_0 = 0，成立。

这里定义 Q(x) 为 x 有齐肯多夫表示这个命题是否成立。

考虑我们已知：

那么如何证明 Q(n) 成立？

我们设 f_k 为不超过 n 的最大斐波那契数，则 f_k \le n<f_{k+1}，考虑 n-f_k：

• 当 n-f_k = 0，那么 f_k 就是 n 的齐肯多夫表示，命题成立。
• 当 n-f_k>0，则 n-f_k<f_{k+1}-f_k，又因为 f_{k+1} = f_k+f_{k-1}，所以 n-f_k<f_{k-1}，也就是说 n-f_k 的齐肯多夫表示中最大的斐波那契数 x 一定满足 x \le f_{k-2}，而 n 的齐肯多夫表示不存在 f_{k-1}，也就是并不存在 n 的齐肯多夫表示中出现相邻的斐波那契数的情况，命题成立。

至此，存在性证毕。

接着证明其唯一性。

利用反证法，假设其表示方法并不唯一，则对于最小的有两种表示方法的数 n \in \mathbb{N}（分别用 a 和 b 表示）：

如果 a_1 = b_1，那 n-a_1 也是有两种表示方法的数，这与 n 是最小的有两种表示方法的数这个定义矛盾。

那么只剩下 a_1>b_1 和 a_1<b_1 了，显然 a_1<b_1 可以通过魔法交换变成 a_1>b_1，所以我们只需要考虑 a_1>b_1 的情况即可。

根据我们之前证明的一个性质：用不超过 f_k（并且严格不相邻）的斐波那契数能表示的最大整数是 f_{k+1}-1。

而又因为 b_1 是 b 中的最大值，根据那个性质，我们可以得出 n \le f_{b_1+1}-1，然后又因为 a_1>b_1 即 b_1<a_1，可推出 b_1+1 \le a_1，所以 f_{b_1+1}-1 \le f_{a_1}-1 即 n \le f_{a_1}-1，但是如果用第一种表示的角度来看的话，n \ge a_1，这两个不等式不可能同时成立，矛盾。

至此，唯一性证毕。 ::::

矩阵关联

::::success[矩阵乘法] 对于一个 n \times r 的矩阵 A 和一个 r \times m 的矩阵 B，它们的乘积定义为一个 n \times m 的矩阵 C，有：

:::: ::::success[k 阶常系数齐次线性递推关系] 通常指 F_i = \sum_{j = 1}^k \left(a_j \times F_{i-j}\right) 的齐次线性递推关系，因为有关 k 个常系数，所以得名。 :::: 假设我们要求 f_n，很显然，我们有：

所以：

初学者到这里可以尝试在图纸上进行笔画理解。因为本人初学时也觉得十分难理解。

那么有了这一步我们再次推广：

可得：

因为矩阵乘法满足结合律，所以可以使用快速幂在 O(\log n) 的时间内计算矩阵的幂。

这里说一下矩阵快速幂的计算变量 ans 的初始值。在普通的快速幂中，开始时 ans = 1，是因为 1 乘任何数都等于那个数本身，而在矩阵中，也有一个起到这种效果的矩阵，单位矩阵！这个矩阵的 3 \times 3 形式长这样：

是的，也就是正对角线是 1，其余是 0 了。

注意：矩阵乘法并不满足交换律。并且要特殊处理 n<2 的情况。

简单放一下代码（非完全体）： ::::success[矩阵乘法代码]

struct node
{
    int a[3][3] = {};
    node operator*(const node&b)const
    {
        node c;
        for(int i = 1;i<=2;++i)
        {
            for(int j = 1;j<=2;++j)
            {
                for(int k = 1;k<=2;++k)
                {
                    c.a[i][j]+=a[i][k]*b.a[k][j];
                }
            }
        }
        return c;
    }
}a,ans,s,c;

:::: ::::success[主函数代码]

if(n<=2)
{
    cout << 1;
}
else
{
    a.a[1][1] = a.a[1][2] = a.a[2][1] = ans.a[1][1] = ans.a[2][2] = s.a[1][1] = s.a[2][1] = 1;
    int y = n-2;
    while(y)
    {
        if(y&1)
        {
            ans = ans*a;
        }
        a = a*a;
        y>>=1;
    }
    for(int i = 1;i<=2;++i)
    {
        for(int j = 1;j<=1;++j)
        {
            for(int k = 1;k<=2;++k)
            {
                c.a[i][j]+=ans.a[i][k]*s.a[k][j];
            }
        }
    }
    cout << c.a[1][1];
}

:::: 其实还可以推广： ::::info[推广] 显然这种做法可以推广到 k 阶常系数齐次线性递推关系。

对于一个 k 阶常系数齐次线性递推关系：

我们要求 F_n，直接列式：

于是：

推广可得：

可用矩阵快速幂在 O(k^3 \log n) 的时间复杂度之内解决。

在 n<k 时需要特殊处理。 ::::

倍增法关联

根据之前的两个前置恒等式，很容易发现对于所有 k \in \mathbb{N}，2k 和 2k+1 已经完美覆盖了所有非负整数，所以我们可以直接递归处理。

这里也简单放一下代码（主函数内容过于简单就不放了，只放递归函数的代码）： ::::success[递归函数代码]

pair<int,int>f(int n)
{
    if (n == 0)
    {
        return {0,1};
    }
    auto x = f(n>>1);
    int a = x.first*(2*x.second-x.first);
    int b = x.first*x.first+x.second*x.second;
    if (n&1)
    {
        return {b,a+b};
    }
    else
    {
        return {a,b};
    }
}

:::: 当然也可以改成非递归形式并把 pair 换成结构体来加快速度，只不过会麻烦一点。

这个方法的优势在于它是真正的 O(\log n)，而之前的矩阵快速幂的做法还带一个 2^3 = 8 的常数。

皮萨诺周期

对于所有 2 \le n \in \mathbb{N}^+，将斐波那契数列统一对 n 取模后一定是一个纯周期的数列，且设该数列的最小周期长度为 \pi(n)，则 \pi(n) \le 6n，而且对 n 进行质因数分解之后 \pi(n) = \operatorname{lcm}_{i = 1}^k \pi(p_i^{a_i})。

若 n 是奇素数并且 n \ne 5，当 n \equiv \pm 1 \pmod 5，则 \pi(n) \mid n-1，当 n \equiv \pm 2 \pmod 5，则 \pi(n) \mid 2(n+1)。 ::::success[纯周期和质因数分解证明] 先证明纯周期。

我们知道斐波那契数列是一个二阶常系数齐次线性递推关系，于是我们有：

该递推由连续两项唯一确定后一项，定义状态：

于是状态空间为：

它显然是一个有限集合，且元素个数为 n^2。

定义状态转移函数 h:S \to S 的转移式为：

则：

初始状态：

定义一个状态转移函数 w:S \to S 可逆，则存在另一个状态转移函数 g:S \to S 使得：

很显然我们可以让 g 的转移式为：

从而使得 h 函数可逆。

对于一个可逆的状态转移函数，我们称它为双射。

对于一个有限集合到自身的双射，我们称它为该集合的置换。

对于从第一个元素就开始循环的集合，我们称它为纯周期。

鸽笼原理：如果把 n+1 个鸽子放进 n 个鸽笼，无论如何放置，至少存在一个鸽笼有两只鸽子。

对于不从第一个元素开始循环但是依旧存在循环的集合，我们称它为最终周期。

显然 h 函数是 S 的一个置换。

给出一个定理：一个有限集合的置换从某点出发的轨道是纯周期循环。

我们来证明一下，首先它是个最终周期是很显然的，根据鸽笼原理，我们的状态集合有限，在第 |S|+1 个状态是一定会出现和之前重复的状态的。

然后如何从最终周期变成纯周期呢？

设 i<j 是最小的使得 h^i(s_0) = h^j(s_0) 的指标对，我们采用反证法，设 i>0，由于 h 函数可逆，所以我们对等式两边求逆：

于是我们得到了更小的一对重复，与原先的定义矛盾。

所以只有在 i = 0 时，等式两边无法求逆，才能使得 i<j 是最小的使得 h^i(s_0) = h^j(s_0) 的指指标对。

至此，纯周期证毕。

接下来证明质因数分解的定理。

显然任意两个不同素数的次幂一定是互质的。

于是我们可以弱化这个定理，转化为两个互质数 m,n。

注意：此 n 并不是定理中的 n，请不要混淆。

我们令：

因为 z 是斐波那契数列模 mn 的周期，所以必有：

根据这个式子，我们又有：

于是显然 x \mid z 并且 y \mid z，我们便得到了 z 的最小取值 t = \operatorname{lcm}(x,y)，并且显然有 t \mid z，也就是说我们只需要再证明 z \mid t 即可证明 z = t。

显然 f_t 也一定满足模 m 和模 n 的同余式，但是如何证明 t 也是模 mn 的一个周期呢？

这里需要用到之前证明过的同余扩展的 \operatorname{lcm} 整除定理：

因为 m,n 互质，也就是 \gcd(m,n) = 1，显然我们就有了：

于是我们就证明了 t 也是模 mn 的一个周期，得到 z \mid t，于是就有了 z = t。

所以 \pi(mn) = \pi(m) \times \pi(n) = \operatorname{lcm}(\pi(m),\pi(n))。

而推广到多个两两互质数也是很容易的，因为我们对两个数 m,n 进行合并也就是取 \operatorname{lcm}(m,n) 之后其实所有数依旧是两两互质，就这样递归下去，最终化为两个质数的情况（不妨说是一直在进行这样的操作）。

至此，质因数分解定理证毕。 :::: 接下来证明整除定理之前让我给出一些前置（前置定理中的一切变量均与皮萨诺周期定理定义中的变量无关）： ::::success[乘法逆元] 定义：对于一个正整数 x，我们定义它在模 p 意义下的乘法逆元 x^{-1} 为最小的正整数 y 使得 xy \equiv 1 \pmod p 的 y。

可行性：我们要计算模 p 意义下的 \frac{a}{x}，即 a \times x^{-1}，说白了就是 a \times \frac{1}{x}，而在模 p 意义下 y = \frac{1}{x}，也就是说在模 p 意义下，\frac{a}{x} = a \times y。

存在性：对于 \gcd(a,p) = 1 的情况，a 在模 p 意义下存在逆元。这很显然可以用数论的整除性质来理解。

至此，乘法逆元的可行性证毕。 :::: ::::success[完全剩余系和既约剩余系] 完全剩余系：设 m 是一个正整数。从整数集 \mathbb{Z} 中取出任意 m 个数，若它们两两模 m 不同余，则这 m 个数模 m 的值组成的集合称为模 m 的一个完全剩余系。

既约剩余系：设 m 是一个正整数。在模 m 的一个完全剩余系中，取出所有与 m 互质的元素，由这些元素组成的集合称为模 m 的一个既约剩余系。 :::: ::::success[二次剩余] 二次剩余：对于一个非负整数 a 和奇素数 p，若：

则说 a 是 p 的二次剩余。

可用勒让德符号表示为：

如果是二次剩余，返回值就是 1，否则就是 -1，特别的，如果满足条件的 t 等于 0 也就是 p \mid a，返回值为 0。 :::: ::::success[威尔逊定理] 威尔逊定理：对于素数 p，满足 (p-1)! \equiv -1 \pmod p。

威尔逊定理证明：考虑集合 S = \{1,2,3,\dots,p-1\}，这是一个模 p 的既约剩余系，对于每一个元素 x，它在该集合中有唯一的乘法逆元 x^{-1}，而我们需要先找出 x = x^{-1} 的 x 的数量，显然就是找 x^2 \equiv 1 \pmod p 的解集大小，而我们将此同余式进行化简：

而因为 p 是素数，要么 p \mid x+1，要么 p \mid x-1。当 p \mid x+1 时，x \equiv -1 \pmod p，易得 x = p-1 是唯一解；当 p \mid x-1 时，x \equiv 1 \pmod p，易得 x = 1 是唯一解。

所以 x^2 \equiv 1 \pmod p 的解集为 \{1,p-1\}。

我们考虑计算 \prod_{x \in S} x，当 1 = p-1 也就是 p = 2 时我们先排掉（因为很影响我们对各种情况的统一处理，并且 p = 2 时该定理也成立），显然我们先处理 1,p-1 这两个特殊的数的乘积与何数在模 p 意义下同余，显然是 -1，而考虑剩余数的个数，显然是 p-3，而因为我们已经排掉了 p = 2 的情况所以 p 是奇数即 p-3 是偶数，于是由于除了 1,p-1 这两个特殊数其余数都可以进行乘法逆元两两配对，所以：

至此，证毕。 :::: ::::success[费马小定理] 费马小定理：对于一个正整数 a 和一个素数 p，若 \gcd(a,p) = 1 也就是 a,p 互质，那么有：

费马小定理证明：我们考虑构造一个既约剩余系，由于 p 是一个素数，所以我们构造的既约剩余系 S = \{1,2,3,\dots,p-1\}。

通过上帝的启发我们很容易想到拿 a 去乘这个剩余系的每一个元素，得到一个新的集合 S' = \{1 \times a,2 \times a,3 \times a,\dots,(p-1) \times a\}，显然将这个集合统一模 p 之后，集合元素两两不同，也就是 S' 是 S 的某种排列方式，即又是一个既约剩余系。

为什么？

采用反证法。我们假设有两个不同的 i,j \in [1,p-1]，使得：

即：

于是我们有 p \mid a(i-j)，而又因为 \gcd(p,a) = 1，所以 p \mid i-j，但是 |i-j|<p，那么只有在 i-j = 0 也就是 i = j 时 p \mid i-j 才成立，但是这与原本假设矛盾，命题成立。

知道了原因之后，我们继续证明，再一次根据仁慈上帝的启发我们很容易想到求两个集合的元素乘积：

我们知道 S' 只是 S 的一个排列，所以这两个乘积在模 p 意义下理应是相等的，于是我们可以写出同余式：

而我们显然可以两边交换后，将右边化为 0，得到：

而 (p-1)! = 1 \times 2 \times 3 \times \dots \times (p-1)，这些数中所有数都和 p 互质，也就是说 (p-1)! 和 p 也是互质的，那么我们就可以从原本的 p \mid (a^{p-1}-1)(p-1)! 得到 p \mid (a^{p-1}-1)，再次变形成同余式，得到：

至此，费马小定理证毕。

后话：然而费马小定理其实还有一种更朴素的形式：对于一个正整数 a 和一个素数 p，有：

在 \gcd(a,p) = 1 的时候我们很显然可以由刚刚证明的那个形式两边同时乘上 a 来得到，那 \gcd(a,p) \ne 1 的时候呢？

显然，若 \gcd(a,p) \ne 1，则因为 p 是素数，所以 p \mid a，而根据整除基本性质，\exists k \in \mathbb{N}^+,\ kp = a，那么我们有：

也就是 a^p \equiv 0 \pmod p，而本身我们就有 a \equiv 0 \pmod p，所以 a^p \equiv a \pmod p。

至此，证毕。 :::: ::::success[欧拉判别法] 欧拉判别法：对于奇素数 p 和满足 \gcd(a,p) = 1 的整数 a，我们有：

欧拉判别法证明：根据费马小定理 a^{p-1} \equiv 1 \pmod p 和平方差公式，我们有：

所以对于任意满足 \gcd(a,p) = 1 的 a 我们都有 a^{\frac{p-1}{2}} \equiv \pm 1 \pmod p。

我们考虑集合 S = \{1,2,3,\dots,p-1\}，对于每一个元素 x，它在集合中有唯一的乘法逆元 x^{-1}。

我们分情况考虑，先考虑 \left(\frac{a}{p}\right) = 1 时的情况。

显然此时存在 b 使得 b^2 \equiv a \pmod p，那么这个二次同余方程的解的数量肯定是 2，并且互为相反数，也可以说是 b 和 -b，而除了这两个特殊数其余数都可以两两配对（因为剩余数的数量是 p-3 为偶数，并且每一个元素 x 都可以和 a \times x^{-1} 进行配对），于是我们有：

于是我们就有了：

根据威尔逊定理，我们得到：

两边同时乘 -1 得到：

至此，\left(\frac{a}{p}\right) = 1 时的情况证毕。

再考虑 \left(\frac{a}{p}\right) = -1 时的情况。

此时不存在 b 使得 b^2 \equiv a \pmod p，也就是说没有不能配对的点，即：

根据威尔逊定理，我们得到：

至此，\left(\frac{a}{p}\right) = -1 时的情况证毕。 :::: ::::success[高斯引理] 高斯引理：对于奇素数 p，若 n \in \mathbb{N}^+,\gcd(n,p) = 1，则 \forall k \in [1,\frac{p-1}{2}],\ a_k = nk \bmod p，有两个集合 A = \{a_k:a_k \le \frac{p-1}{2}\},B = \{a_k:a_k>\frac{p-1}{2}\}，我们有：

高斯引理证明：设 \lambda = |A|,\mu = |B|，显然我们知道 a 数列不存在两个重复的数（即 \lambda+\mu = \frac{p-1}{2}），证明很简单，采用反证法，若有两个不同下标 i,j 使得：

即：

显然 n 在模 p 意义下是存在乘法逆元的（根据逆元的存在性），所以将式子化为：

显然由于 i,j \le \frac{p-1}{2}，所以 i = j，与原先假设矛盾，该命题成立。

既然我们证明了数列没有两个重复的数，所以：

这里我简单说明一下为什么可以由第二个式子推出第三个式子，因为根据乘法逆元的存在性性质，我们知道在这里 n 在模 p 意义下是有乘法逆元的，于是我们就可以同余号两边同时乘上 n 在模 p 意义下的乘法逆元，得到显然正确的同余式。

我们知道对于 B 中任意元素 b，有 \frac{p-1}{2}<b<p，所以 0<p-b \le \frac{p-1}{2}，而对于 B 中任意一个元素 b，我们有 p-b \not \in A，否则若 A,B 中分别存在元素 a,b 使得 a = p-b，则存在整数 1 \le k_1 \ne k_2 \le \frac{p-1}{2} 使得 a = nk_1,b = nk_2 且 p \mid nk_1+nk_2，由于 (n,p) = 1，则 p \mid k_1+k_2，注意到 1 \le k_1+k_2<p，所以产生矛盾。

而我们知道 b \equiv -(p-b) \pmod p，所以：

再次利用乘法逆元的存在性性质，得出：

运用欧拉判别法：

可得：

:::: ::::success[二次互反律] 二次互反律：对于两个二次剩余 \left(\frac{p}{q}\right),\left(\frac{q}{p}\right)，这里 p \ne q，我们有：

二次互反律证明：先给出一个推论，对于奇素数 p，我们有：

若奇数 n 满足 \gcd(n,p) = 1，则我们有：

考虑证明（这个推论的证明中 p 并不是二次互反律定义中的 p）。

对于高斯引理中的 n,k,a_k,A,B,\lambda,\mu，我们有 \exist p \in \mathbb{N}^+,\ nk = p \left\lfloor \frac{nk}{p} \right\rfloor+a_k，首先我们有：

证明很简单，我们来推导一下就行了：

证明完后我们继续进一步可以得到：

我们来证明一下为什么：

等式两边同时减去 p \sum_{k = 1}^{\frac{p-1}{2}} \left\lfloor \frac{nk}{p} \right\rfloor+\sum_{a \in A} a，得出我们只需要证明：

来推导一下：

证明完后我们继续：

我们很容易得到：

先证明这个推论的第一个部分，也就是 n = 2 的时候。

而为了证明 (-1)^{\frac{p^2-1}{8}} = (-1)^{\mu}，我们需要证明 \frac{p^2-1}{8} \equiv \mu \pmod 2。

因为 n = 2，所以上面的恒等式变为：

我们显然有 0<\frac{2k}{p} \le \frac{p-1}{p}<1，也就是 \forall k \in [1,\frac{p-1}{2}],\ \left\lfloor \frac{2k}{p} \right\rfloor = 0，所以可以转化为：

又因为 p 是奇数所以 p \equiv 1 \pmod 2，可转化为：