平方分解与圆周率

概要

• 中文，英文；
• 初中数学；
• 集合，序列的定义；
• 复数的定义及加减乘；
• 模意义下运算，整数辗转相除法，Bezout 定理及其正确性证明；
• Wilson 定理；

• Fermat 平方和定理的证明；
• 二元二次方程 $x^2+y^2=a$ 的整数解计数以及零感性理解正确性证明，构造；
• 证明 $\frac\pi4=\frac11-\frac13+\frac15-\frac17+\dots$。

【前置知识】环论

各种环的定义

• 加法封闭性：$\forall x,y\in R:x+y\in R$；
• 加法结合律：$\forall x,y,z\in R:(x+y)+z=x+(y+z)$；
• 加法单位元（有时简称为「零元」）存在：$\exists 0\in R:\forall x\in R:0+x=x$；
• 加法逆元存在：$\forall x\in R:\exists{-x}\in R:x+(-x)=0$；
• 加法交换律：$\forall x,y\in R:x+y=y+x$；
• 乘法封闭性：$\forall x,y\in R:xy\in R$；
• 乘法结合律：$\forall x,y,z\in R:(xy)z=x(yz)$；
• 乘法对加法的分配律：$\forall x,y,z\in R:x(y+z)=xy+xz,(y+z)x=yx+zx$。

证：$ab-ac=0\Rightarrow a(b-c)=0$，是整环，$a$ 又不是 $0$，只能 $b-c=0\Rightarrow b=c$。

理想

证：

环的封闭性显然，因为 $x,y\in I,x,y\in J$ 必然有 $xy\in I,xy\in J$，从而 $xy\in I\cap J$，各种运算律也随之满足。至于为什么 $r(I\cap J),(I\cap J)r\subseteq(I\cap J)$

$$\forall x\in I\cap J,r\in R:x\in I,x\in J\\ \Rightarrow rx,xr\in I,J\\ \Rightarrow rx,xr\in I\cap J$$

$$I+J:=\{i+j\mid i\in I,j\in J\}\\ IJ:=\left\{\sum_{k=1}^ni_kj_k\mid n\in\N,i_k\in I,j_k\in J\right\}$$

证：对于加法，设

$$i_1,i_2\in I,j_1,j_2\in J,r\in R\\ a=i_1+j_1,b=i_2+j_2\in I+J$$

则有

$$a+b=(i_1+i_2)+(j_1+j_2)\in I+J\\ ra=ri_1+rj_1\in I+J$$

对于乘法，设

$$i_k,{i'}_k\in I,j_k,{j'}_k\in J,r\in R\\ a=\sum_{k=1}^ni_kj_k,b=\sum_{k=1}^m{i'}_k{j'}_k$$

则有

$$a+b=\sum_{k=1}^ni_kj_k+\sum_{k=1}^m{i'}_k{j'}_k\\ ra=\sum_{k=1}^n(ri_k)j_k\in IJ$$

存在性证明：首先，$R$ 肯定是一个包含 $A$ 的理想。然后，如果理想 $I,J\supseteq A$ 互不包含，那么 $I\cap J$ 一定包含 $A$ 且是理想。

商环

证：

$$\begin{aligned} (a+I)+(b+I)=&\{(a+b+i+j)\mid i,j\in I\}\\ =&(a+b)+I\\ (a+I)(b+I)=&\{\sum_{k=1}^ni_kj_k\mid i_k\in a+I,j_k\in b+I\}\\ =&\{\sum_{k=1}^n(a+i_k)(b+j_k)\mid i_k,j_k\in I\}\\ =&\{\sum_{k=1}^nab+ai_k+bj_k+i_kj+k\mid i_k,j_k\in I\}\\ \xlongequal{ai_k,bj_k,i_kj_k\in I}&(ab)I \end{aligned}$$

整除

$$\exists d:d\mid a,d\mid b\\ \forall d'\mid a,d'\mid b:d'\mid d$$

证：对于素元 $r$，考虑当 $r=ab$ 时证明 $a$ 或 $b$ 可逆。由 $r\mid ab$ 和素元的定义得 $r\mid a\lor r\mid b$，不妨设 $r\mid a$。令 $a=cr$，则 $r=ab=crb\Rightarrow cb=1$，故 $b$ 可逆。

Euclid 整环

证明与整数上的辗转相除法正确性和 Bezout 定理类似。

主理想整环

证：取理想 $I$ 上范数最小的非 $0$ 元素 $d$，那么所有 $a\in I$ 满足 $a=qd+r$，由 $N(r)<N(d)$ 得 $r=0$，故 $\forall a\in I:\exists q\in I:a=qd$，故 $a\in(d)\Rightarrow I\subseteq(d)$，根据生成理想的定义得 $I=(d)$。

引理 5 已经证了一半了，下证不可约元都是素元。

设不可约元 $p$ 满足 $p\mid ab$，需要证明 $p\mid a\lor p\mid b$。考虑理想：

$$I:=(p,a)=\{pi+aj\mid i,j\in R\}$$

因为是主理想整环，所以 $\exists d:(d)=I$。由 $p\in I$ 和 $\{xd\mid x\in R\}=(d)$ 得 $d\mid p$，此时要么 $d,p$ 相伴，要么 $d$ 是可逆元。

$d,p$ 相伴时，存在可逆元 $u$ 满足 $ud=p$，从而

$$I=(d)=(ud)=(p)\\ a\in(p)\\ p\mid a$$

$d$ 为可逆元的时候，

$$\exists u:ud=1\\ 1\in I\\ \exists i,j\in R:pi+aj=1\\ b=pib+ajb\\ p\mid ab\Rightarrow p\mid ajb\Rightarrow p\mid(pib+ajb)\Rightarrow p\mid b$$

证毕。

唯一分解整环

证：对于不可约元 $r$ 和 $r\mid ab$，将 $ab$ 进行分解，$r$ 必和其中一个因子相伴，不妨设他可能来自于 $a$（即他一定是 $a$ 的因子，可能是 $b$ 的因子），则 $r\mid a$，故 $r$ 是素元。

证：

$r$ 的分解存在性：

如果 $r$ 是不可约元，那么不必继续分解；否则对满足 $r=r_1r_2$ 的非可逆元 $r_1,r_2$ 继续分解。如果分解不停止，无限进行，那么存在一个序列 $\{r_\infty\}$ 满足 $r_0=r,r_{i+1}\mid r$，且序列中相邻的数两两不相伴。考虑他们生成的理想 $I_i:=(r_i)$，则 $I_i\subset I_{i+1},I_i\subseteq R$。令 $I:=\bigcup_{i=0}^\infty I_i$，则 $I$ 是理想（$\forall a,b\in I:\exists n\in\N:a,b\in I_n$），从而 $I$ 是主理想。令其生成元为 $d$，则 $\exists n\in\N:d\in I_n$，从而 $I\subseteq I_n$，矛盾。

$r$ 的分解唯一性：

如果 $r$ 有 $\prod_{i=1}^np_i=\prod_{i=1}^mq_i=r$，那么对于不可约元 $p_1$，一定存在 $p_1\mid q_i$，因为 $q_i$ 也是不可约元，所以他俩相伴，从两个序列里踢出去。以此类推，知道其中一个序列为空，另一个如果不为空，则里面的乘积为 $1$，因此都是可逆元，不符合定义；如果为空，就说明 $n=m$，恰恰证明了两个序列在重排和相伴的意义下唯一。

对于可逆元 $u_1,u_2$ 和唯一分解整环上的数 $r_1=u_1\prod_{i=1}^n{p_i}^{\alpha_i},r_2=u_2\prod_{i=1}^n{p_i}^{\beta_i}$，有 $\gcd(r_1,r_2)=\prod_{i=1}^n{p_i}^{\min(\alpha_i,\beta_i)}$ 在相伴意义下唯一且存在。

【前置知识】二次剩余

$$\left(\frac ap\right):= \begin{aligned}\begin{cases} 0,\quad&a\equiv0\\ 1,\quad&a\not\equiv0,a\text{ is a quadratic residue}\\ -1,\quad&\text{otherwise}. \end{cases}\end{aligned}$$

证明：

• 如果 $a\equiv 0$，那么两边都是 $0$；
• 否则，如果 $a$ 是二次剩余，那么 $a^{\frac{p-1}2}\equiv{\sqrt a}^{p-1}\equiv 1$；
• 否则，令 $r(i):=ai^{-1}$，那么

$$r(i)\neq i\\ r^{-1}=r\\ \begin{aligned} a^{\frac{p-1}2}\equiv&\prod_{i\in[1,p),i<r(i)}ir(i)\\ \equiv&(p-1)!\\ \overset{\text{Wilson's Theorem}}{\equiv}&{-1} \end{aligned}$$

证明：

试证 $\left\lvert\{(x^2\bmod p)\mid x\}\right\rvert=\frac{p-1}2$。考虑一个更强的结论：$\forall x:\exist!^*y:x^2\equiv y^2$。这相当于 $(x+y)(x-y)\equiv 0$，由于 $x\neq y$，所以 $x+y\equiv 0,y\equiv-x$。

*$\exist!$ 表示恰好存在一个。

$$\begin{aligned} (u+\sqrt t)^{p+1}=&(u+\sqrt t)\sum_{i=0}^p\binom piu^i\sqrt t^{p-i}\\ \equiv&(u+\sqrt t)\left(u^p+\sqrt t^p\right)\\ \equiv&(u+\sqrt t)\left(u+\sqrt t\left(\sqrt t^2\right)^{\frac{p-1}2}\right)\\ \equiv&(u+\sqrt t)\left(u+\sqrt t\cdot t^{\frac{p-1}2}\right)\\ \equiv&(u+\sqrt t)(u-\sqrt t)\\ \equiv&u^2-t\\ \equiv&a \end{aligned}$$

证明：

如果存在 $A,B$ 满足 $B\not\equiv0,(A+B\sqrt t)^2\equiv a$，那么 $A^2+tB^2+2AB\sqrt t\equiv a$，从而 $2AB\equiv0\Rightarrow A\equiv 0\Rightarrow B^2t\equiv a$。但是 $\left(\frac tp\right)\left(\frac{B^2}p\right)=-1\times1\neq1=\left(\frac ap\right)$，矛盾。故 $\Im\left((u+\sqrt t)^{\frac{p+1}2}\right)\equiv0$ 得证，结合引理 3 可得 $\Re\left((u+\sqrt t)^{\frac{p+1}2}\right)^2\equiv a$。

【前置知识】行列式

$$\{\text{sequence }a\mid\forall i\in T:i\in a,\forall i\in a:i\in T, |a|=|T|\}$$ $$\sigma=[\tau_1,\tau_2,\dots,\tau_{I-1},j,\tau_I,\dots,\tau_{n-1}]$$

原本的，$j$ 在 $j$ 位置，左边有多少个比 $j$ 大，右边就有多少个比 $j$ 小，$j$ 对逆序对奇偶性贡献为 $0$。$j$ 每移动一格，就会对逆序对造成一个 $\pm1$ 的贡献，移动 $\lvert I-j\rvert$ 格，奇偶性改变 $(I-j)\bmod 2$。

考虑每一对 $(i,j)$，其中 $i<j$。有 ${\sigma^{-1}}_{\sigma_i}=i,{\sigma^{-1}}_{\sigma_j}=j$。如果 $\sigma_i<\sigma_j$，那么 $(\sigma_i,\sigma_j)$ 在 $\sigma^{-1}$ 中不构成逆序对；$\sigma_i>\sigma_j$ 时构成。

$$A= \begin{bmatrix} a_{1,1}&&a_{1,2}&&\ldots&&a_{1,n}\\ a_{2,1}&&a_{2,2}&&\ldots&&a_{2,n}\\ \vdots&&\vdots&&\ddots&&\vdots\\ a_{n,1}&&a_{n,2}&&\cdots&&a_{n,n} \end{bmatrix}$$ $$A^T:= \begin{bmatrix} a_{1,1}&&a_{2,1}&&\ldots&&a_{n,1}\\ a_{1,2}&&a_{2,2}&&\ldots&&a_{n,2}\\ \vdots&&\vdots&&\ddots&&\vdots\\ a_{1,n}&&a_{2,n}&&\cdots&&a_{n,n} \end{bmatrix}$$ $$\begin{vmatrix} a_{1,1}&&a_{1,2}&&\ldots&&a_{1,n}\\ a_{2,1}&&a_{2,2}&&\ldots&&a_{2,n}\\ \vdots&&\vdots&&\ddots&&\vdots\\ a_{n,1}&&a_{n,2}&&\cdots&&a_{n,n} \end{vmatrix}$$

$$\begin{aligned} \det(A)=&\sum_{\sigma\in S_n}\mathrm{sgn}(\sigma)\prod_{i=1}^na_{i,\sigma_i}\\ =&\sum_{\sigma'\in S_n}\mathrm{sgn}(\sigma')\prod_{i=1}^na_{\sigma',i}\\ =&\det(A') \end{aligned}$$

第二个等于是因为可以考虑 $\sigma$ 和他的逆置换 $\sigma'$ 一一对应。结合引理 2。

$$A_{ij}:= \begin{bmatrix} a_{1,1}&&\cdots&&a_{1,j-1}&&a_{1,j+1}&&\cdots&&a_{1,n} \\ \vdots&&\ddots&&\vdots&&\vdots&&\ddots&&\vdots \\ a_{i-1,1}&&\cdots&&a_{i-1,j-1}&&a_{i-1,j+1}&&\cdots&&a_{i-1,n} \\ a_{i+1,1}&&\cdots&&a_{i+1,j-1}&&a_{i+1,j+1}&&\cdots&&a_{i+1,n} \\ \vdots&&\ddots&&\vdots&&\vdots&&\ddots&&\vdots \\ a_{n,1}&&\cdots&&a_{n,j-1}&&a_{n,j+1}&&\cdots&&a_{n,n} \end{bmatrix}$$ $$\forall I:\det(A)=\sum_{j=1}^na_{I,j}\cdot(-1)^{\lvert I-j\rvert}\cdot\det(A_{Ij})$$

证：

$$\begin{aligned} \det(A)=&\sum_{\sigma\in S_n}\mathrm{sgn}(\sigma)\prod_{i=1}^na_{i,\sigma_i}\\ =&\sum_{j=1}^na_{I,j}\sum_{\sigma\in S_n,\sigma_{I}=j}\mathrm{sgn}(\sigma)\prod_{k\in[1,n],k\neq I}a_{k,\sigma_k}\\ =&\sum_{j=1}^na_{I,j}\sum_{\tau\in\mathrm{Perm}([1,n]\setminus\{I\})}(-1)^{\lvert I-j\rvert}\mathrm{sgn}(\tau)\prod_{k\in[1,n]\setminus\{I\}}a_{k,\sigma_k}\\ =&\sum_{j=1}^na_{I,j}\cdot(-1)^{\lvert I-j\rvert}\cdot\det(A_{Ij}) \end{aligned}$$

$$\forall J:\det(A)=\sum_{i=1}^na_{i,J}\cdot(-1)^{\lvert i-J\rvert}\cdot\det(A_{iJ})$$

【前置知识】连分数

$$a_0+\frac1{a_1+\frac1{\ddots\frac1{a_n}}}$$ $$p_k=a_kp_{k-1}+p_{k-2}\\ q_k=a_kq_{k-1}+q_{k-2}$$ $$p_{-1}=1,q_{-1}=0\\ p_{-2}=0,q_{-2}=1$$

证：$p_k$ 可以看作关于 $a_0,a_1,\dots,a_k$ 的多项式 $P_k(a_0,\dots,a_k)$，同理 $q_k=:Q_k(a_0,\dots,a_k)$。此时 $Q_k(a_0,\dots,a_k)=P_{k-1}(a_1,\dots,a_k)$。OI Wiki 上只说了个不妨设，没搞明白。

分析 $Q_k(a_0,\dots,a_k)$：

$$\begin{aligned} &[a_0;a_1,\dots,a_k]\\ =&a_0+\frac1{[a_1;a_2,\dots,a_k]}\\ =&a_0+\frac1{a_1+\frac1{[a_2;a_3,\dots,a_k]}}\\ =&a_0+\frac1{a_1+\frac{Q_{k-2}(a_2,\dots,a_k)}{P_{k-2}(a_2,\dots,a_k)}}\\ =&a_0+\frac1{\frac{a_1P_{k-2}(a_2,\dots,a_k)+Q_{k-2}(a_2,\dots,a_k)}{P_{k-2}(a_2,\dots,a_k)}}\\ =&a_0+\frac{P_{k-2}(a_2,\dots,a_k)}{a_1P_{k-2}(a_2,\dots,a_k)+Q_{k-2}(a_2,\dots,a_k)}\\ &Q_k(a_0,\dots,a_k)\\ =&a_1P_{k-2}(a_2,\dots,a_k)+Q_{k-2}(a_2,\dots,a_k) \end{aligned}$$

再来分析 $P_{k-1}(a_1,\dots,a_k)$：

$$\begin{aligned} &[a_1;a_2,\dots,a_k]\\ =&a_1+\frac1{[a_2;a_3,\dots,a_k]}\\ =&a_1+\frac{Q_{k-2}(a_2,\dots,a_k)}{P_{k-2}(a_2,\dots,a_k)}\\ =&\frac{a_1P_{k-2}(a_2,\dots,a_k)+Q_{k-2}(a_2,\dots,a_k)}{P_{k-2}(a_2,\dots,a_k)}\\ &P_{k-1}(a_1,\dots,a_k)\\ =&a_1P_{k-2}(a_2,\dots,a_k)+Q_{k-2}(a_2,\dots,a_k) \end{aligned}$$

一方面：

$$x_k=\frac{p_k}{q_k}=\frac{P_k(a_0,\dots,a_k)}{Q_k(a_0,\dots,a_k)}$$

一方面：

$$\begin{aligned} x_k=&[a_0;a_1,\dots,a_k]\\ =&a_0+\frac1{[a_1;a_2,\dots,a_k]}\\ =&a_0+\frac1{\frac{P_{k-1}(a_1,\dots,a_k)}{Q_{k-1}(a_1,\dots,a_k)}}\\ =&\frac{a_0P_{k-1}(a_1,\dots,a_k)+Q_{k-1}(a_1,\dots,a_k)}{P_{k-1}(a_1,\dots,a_k)} \end{aligned}$$

所以

$$\begin{aligned} \frac{P_k(a_0,\dots,a_k)}{Q_k(a_0,\dots,a_k)}=&\frac{a_0P_{k-1} (a_1,\dots,a_k)+Q_{k-1}(a_1,\dots,a_k)}{P_{k-1}(a_1,\dots,a_k)}\\ P_k(a_0,\dots,a_k)=&a_0P_{k-1}(a_1,\dots,a_k)+Q_{k-1}(a_1,\dots,a_k)\\ =&a_0P_{k-1}(a_1,\dots,a_k)+P_{k-2}(a_2,\dots,a_k) \end{aligned}$$

考虑一个 $k+1$ 阶方阵：

$$M_k(a_0,\dots,a_k):= \begin{bmatrix} a_0&&1&&0&&\cdots&&0&&0&&0\\ -1&&a_1&&1&&\cdots&&0&&0&&0\\ 0&&-1&&a_2&&\cdots&&0&&0&&0\\ \vdots&&\vdots&&\vdots&&\ddots&&\vdots&&\vdots&&\vdots&&\\ 0&&0&&0&&\cdots&&a_{k-2}&&1&&0\\ 0&&0&&0&&\cdots&&-1&&a_{k-1}&&1\\ 0&&0&&0&&\cdots&&0&&-1&&a_k \end{bmatrix}$$

行列号为 $1$ 到 $k+1$。下证 $\det(M_k(a_0,\dots,a_k))=P_k(a_0,\dots,a_k)$。

$k=0$ 时，$\det(M_0(a_0))=a_0=P_0(a_0)$。

$k=1$ 时，$\det(M_1(a_0,a_1))=a_0a_1-1\times(-1)=a_0a_1+1=P_1(a_0,a_1)$。

$k\ge 2$ 时，考虑对 $M_k(a_0,\dots,a_k)$ 在第 $1$ 行做 Laplace 展开：

$$\begin{aligned} &\det(M_k(a_0,\dots,a_k))\\ =&\sum_{j=1}^{k+1}(M_k(a_0,\dots,a_k))_{1,j}\cdot(-1)^{j-1}\cdot\det((M_k(a_0,\dots,a_k))_{1j})\\ =&a_0\det((M_k(a_0,\dots,a_k))_{11})-\det((M_k(a_0,\dots,a_k))_{12}) \end{aligned}$$

对两个加数分别分析。

前者：

$$(M_k(a_0,\dots,a_k))_{11}= \begin{bmatrix} a_1&&1&&\cdots&&0&&0&&0\\ -1&&a_2&&\cdots&&0&&0&&0\\ \vdots&&\vdots&&\ddots&&\vdots&&\vdots&&\vdots&&\\ 0&&0&&\cdots&&a_{k-2}&&1&&0\\ 0&&0&&\cdots&&-1&&a_{k-1}&&1\\ 0&&0&&\cdots&&0&&-1&&a_k \end{bmatrix}\\ (M_k(a_0,\dots,a_k))_{11}=M_{k-1}(a_1,\dots,a_k)\\$$

后者：

$$(M_k(a_0,\dots,a_k))_{12}= \begin{bmatrix} -1&&1&&\cdots&&0&&0&&0\\ 0&&a_2&&\cdots&&0&&0&&0\\ \vdots&&\vdots&&\ddots&&\vdots&&\vdots&&\vdots&&\\ 0&&0&&\cdots&&a_{k-2}&&1&&0\\ 0&&0&&\cdots&&-1&&a_{k-1}&&1\\ 0&&0&&\cdots&&0&&-1&&a_k \end{bmatrix}$$

看到他的第一列只有一个非 $0$，考虑对他在第一列做 Laplace 展开：

$$\begin{aligned} &\det((M_k(a_0,\dots,a_k))_{12})\\ =&\sum_{i=1}^k((M_k(a_0,\dots,a_k))_{12})_{i,1}\cdot(-1)^{i-1}\cdot\det(((M_k(a_0,\dots,a_k))_{12})_{i1})\\ =&-\det(((M_k(a_0,\dots,a_k))_{12})_{11})\\ =&-\det(M_{k-2}(a_2,\dots,a_k)) \end{aligned}$$

将分析结果代入，得：

$$\begin{aligned} &\det(M_k(a_0,\dots,a_k))\\ =&a_0\det((M_k(a_0,\dots,a_k))_{11})-\det((M_k(a_0,\dots,a_k))_{12})\\ =&a_0\det(M_{k-1}(a_1,\dots,a_k))+\det(M_{k-2}(a_2,\dots,a_k)) \end{aligned}$$

对比 $\det(M_k(a_0,\dots,a_k))$ 和 $P_k(a_0,\dots,a_k)$，发现他们的初值一样，递推关系一样，所以二者完全相同：$\det(M_k(a_0,\dots,a_k))=P_k(a_0,\dots,a_k)$。

同理，从第 $k+1$ 列展开，得：

$$\det(M_k(a_0,\dots,a_k))=a_k\det(M_{k-1}(a_0,\dots,a_{k-1}))+\det(M_{k-2}(a_0,\dots,a_{k-2}))\\ P_k(a_0,\dots,a_k)=a_kP_{k-1}(a_0,\dots,a_{k-1})+P_{k-2}(a_0,\dots,a_{k-2})$$

回顾 $P$ 的定义，这其实就是：

$$p_k=a_kp_{k-1}+p_{k-2}$$

对于 $Q$，我们有：

$$P_{k-1}(a_1,\dots,a_k)=a_kP_{k-2}(a_1,\dots,a_{k-1})+P_{k-3}(a_1,\dots,a_{k-2})\\ Q_k(a_0,\dots,a_k)=a_kQ_{k-1}(a_0,\dots,a_{k-1})+P_{k-2}(a_0,\dots,a_{k-2})\\ q_k=a_kq_{k-1}+q_{k-2}$$

递推式证明完毕。将 $p_{-1}=1,q_{-1}=0,p_{-2}=0,q_{-2}=1$ 代入，得：

$$p_0=a_0p_{-1}+p_{-2}=a_0\\ q_0=a_0q_{-1}+q_{-2}=1\\ p_1=a_1p_0+p_{-1}=a_0a_1+1\\ q_1=a_1q_0+q_{-1}=a_0$$

符合。证毕。

证：

$$\begin{aligned} \begin{vmatrix}p_{k+1}&p_k\\q_{k+1}&q_k\end{vmatrix}=&\begin{vmatrix}a_kp_k+p_{k-1}&p_k\\a_kq_k+q_{k-1}&q_k\end{vmatrix}\\ =&\begin{vmatrix}p_{k-1}&p_k\\q_{k-1}&q_k\end{vmatrix}\\ =&-\begin{vmatrix}p_k&p_{k-1}\\q_k&q_{k-1}\end{vmatrix}\\ =&(-1)^{k+2}\begin{vmatrix}p_{-1}&p_{-2}\\q_{-1}&q_{-2}\end{vmatrix}\\ =&(-1)^k \end{aligned}$$

证：结合 $x=[a_0;a_1,\dots,a_k,r_{k+1}]$，引理 2 和引理 1。

证：$a_{k+1}=\lfloor r_{k+1}\rfloor\le r_{k+1}$，由引理 1 $q_{k+1}=a_{k+1}q_k+q_{k-1}$ 和引理 3 推得原命题。

【前置知识】其他

Dirichlet 卷积

离散介值定理（？）

证：$C=A$ 或 $C=B$ 时显然成立。否则，考虑集合 $S:=\{i\mid f(i)>C\}$，显然 $y\in S$，故 $S$ 非空。考虑 $p:=\min S$，显然 $p>x$，所以 $f(p-1)\le C$。那么 $z:=p-1$ 代入原命题显然成立。

Fermat 平方和定理

证明：

定义 $S:=\{(x,y,z)\mid x^2+4yz=p,(x,y,z)\in\N^3\}$，显然是有限的，且里面没有 $0$（$y=0\lor z=0\Rightarrow x^2=p,x=0\Rightarrow 4yz=p$），还一定有 $x\neq y-z$（$x=y-z\Rightarrow (y+z)^2=p$）和 $x\neq 2y$（$x=2y\Rightarrow 4y(y+z)=p$）。

考虑两个映射：

$$f(x,y,z)=(x,z,y)\\ g(x,y,z)= \begin{aligned}\begin{cases} (x+2z,z,y-x-z),\quad&x<y-z\\ (2y-x,y,x-y+z),\quad&y-z<x<2y\\ (x-2y,x-y+z,y),\quad&\text{otherwise.} \end{cases}\end{aligned}$$

由于

$$(x+2z)^2+4z(y-x-z)=x^2+4z^2+4xz-4xz+4yz-4z^2=x^2+4yz\\ (2y-x)^2+4y(x-y+z)=x^2+4y^2-4xy+4yx-4y^2+4yz=x^2+4yz\\ (x-2y)^2+4y(x-y+z)=x^2+4yz$$

所以 $f,g:S\to S$。

注意到 $g$ 是对合（自身是自身逆映射的映射）：

第一次所选分支	一次映射结果	第二次所选分支	二次映射结果
$x<y-z$	$(x+2z,z,y-x-z)$	$2y'<x'$	$(x+2z-2z,x+2z-z+y-x-z,z)$
$y-z<x<2y$	$(2y-x,y,x-y+z)$	$y'-z'<x'<2y'$	$(2y-2y+x,y,2y-x-y+x-y+z)$
$2y<x$	$(x-2y,x-y+z,y)$	$x'<y'-z'$	$(x-2y+2y,y,x-y+z-x+2y-y)$

再来考虑 $g$ 的不动点，$(x,y,z)$ 只有可能走 $y-z<x<2y$ 的分支（否则可以考虑映射后的 $x$，显然 $x+2z,x-2y\neq x$），因而 $2y-x=x$，推出 $x=y$，结合 $x^2+4yz=p$ 得到 $x(x+4z)=p$，所以 $x=1,y=1,z=\left\lfloor\frac{p-1}4\right\rfloor$。他是 $g$ 唯一的不动点。又因为 $g$ 是对合，可以将 $S\setminus{\left\{\left(1,1,\left\lfloor\frac{p-1}4\right\rfloor\right)\right\}}$ 中的元素两两配对，所以 $|S|$ 为奇。又 $f$ 是对合，所以至少存在一个不动点，此时 $y=z$，即 $x^2+y^2=p$，Fermat 平方和定理得证。

复数与 Gauss 整数

证：

$$\begin{aligned} \frac{a_1+b_1i}{a_2+b_2i}=&\frac{(a_1+b_1i)(a_2-b_2i)}{(a_2+b_2i)(a_2-b_2i)}\\ =&\frac{a_1b_1+a_2b_2+a_2b_1i-a_1b_2i}{{a_2}^2+{b_2}^2}\\ =&\frac{a_1b_1+a_2b_2}{{a_2}^2+{b_2}^2}+\frac{a_2b_1-a_1b_2}{{a_2}^2+{b_2}^2}\cdot i \end{aligned}$$

显然。

证：

令

$$\left(\frac ab\right)_\Complex=:x+yi\\ x':=\left\lfloor x+\frac12\right\rfloor\\ y':=\left\lfloor y+\frac12\right\rfloor\\ q:=x'+y'i$$

则

$$|x-x'|,|y-y'|\le\frac12\\ r=a-bq=b(x+yi-q)=b(x-x'+(y-y')i)$$

考虑其范数：

$$N(r)=N(b)((x-x')^2+(y-y')^2)\le\frac12N(b)<N(b)$$

平方分解

证：$x^2+y^2=a\Leftrightarrow(x-yi)(x+yi)=a$。

分解模 $4$ 余 $1$ 质数

证：

考虑其等价命题：如果 $\exists x,y,u,v\in\N^+,(x,y)\neq(u,v),(x,y)\neq(v,u):x^2+y^2=u^2+v^2=p$，则 $p$ 是合数。

$(x,y),(u,v)$ 两个数对，每个数对都恰有一奇一偶，不妨设 $x,u$ 偶，$y,v$ 奇，$x<u$。由于 $2\mid\gcd(u-x,y-v)$ 且他们都大于 $0$，可以设正整数

$$d:=\frac{\gcd(u-x,y-v)}2\\ a:=\frac{u-x}{2d}\\ b:=\frac{y-v}{2d}$$

则 $a\perp b$。那么

$$x^2+y^2=u^2+v^2\\ u^2-x^2=y^2-v^2\\ (u-x)(u+x)=(y-v)(y+v)\\ 2ad(2ad+2x)=2bd(2bd+2v)\\ a^2d+ax=b^2d+bv$$

等号所代表的数同时被 $a,b$ 整除，且 $a\perp b$，所以可以设正整数

$$c:=\frac{a^2d+ax}{ab}$$

从而

$$a^2d+ax=abc\\ x=\frac{abc-a^2d}a=bc-ad\\ y=2bd+v=ac+bd\\ p=x^2+y^2=(bc-ad)^2+(ac+bd)^2=(a^2+b^2)(c^2+d^2)$$

由 $a,b,c,d\in\N^+$ 推得 $p$ 为合数。

1. 找到 $c$ 使得 $c^2\equiv -1\pmod p, c<\frac p2$（由于 $\left(\frac{-1}{4k+1}\right)\equiv(-1)^{\frac{(4k+1)-1}2}=1$，所以 $a$ 一定存在）；
2. 找到一个 $\frac ab$，满足 $\exists k:\frac ab={\frac cp}_{k},\frac{a'}{b'}={\frac cp}_{k+1},b\le\sqrt p, b'>\sqrt p$（这一步可以用连分数渐进分数的递推式），此时 $(bc-pa)^2+b^2=p$。

正确性证明：

存在性是容易的：最后一个 $b$ 一定是 $p$，$a$ 一开始是 $0$，由离散介值定理部分的定理 1 知存在性。

根据连分数引理 4，

$$\exists\epsilon\le1:\frac cp=\frac ab+\frac\epsilon{bb'}\\ bc-pa=\frac{\epsilon p}{b'}<\epsilon\sqrt p\\ b^2<p\\ (bc-pa)^2+b^2<2p^2\\ (bc-pa)^2+b^2\equiv b^2c^2+b^2\equiv-b^2+b^2\equiv0\pmod p\\ p\mid(bc-pa)^2+b^2\\ (bc-pa)^2+b^2=p$$

一般整数分解与计数

• 对于每个 ${p_i}^{\alpha_i}$，他在 $\Z[i]$ 中能被分解成相伴意义下唯一的 $(z_i\overline{z_i})^{\alpha_i}$。这 $\alpha_i$ 个 $z_i$ 可以分配给左边 $j\in[0,\alpha_i]$ 个，相应地给右边 $\alpha_i-j$ 个，$\overline{z_i}$ 给左边 $\alpha_i-j$ 个，给右边 $j$ 个，他为方案数贡献 $\alpha_i+1$。注意这里交换重复不算重复。
• 对于每个 ${q_i}^{\beta_i}$，由 Fermat 平方和定理得他在 $\Z[i]$ 中不可分解，我们还要保证 $n$ 分解成一对共轭 Gauss 整数，由 Gauss 整数的唯一分解性得只能是左边右边各 $\frac{\beta_i}2$ 个 $q_i$。当 $\beta_i$ 为偶数时，他对方案数的贡献为 $1$，否则为 $0$。
• 对于 $\delta$ 个 $2=(1+i)(1-i)$，由于 $1+i=i(1-i)$，因此 $2$ 的所有分法在相伴意义下重复，为答案贡献 $1$。

圆周率

$\chi$

$$\chi(x):= \begin{aligned}\begin{cases} 1,\quad&x\equiv1\pmod4\\ 0,\quad&x\equiv0\pmod2\\ -1,\quad&\text{otherwise.} \end{cases}\end{aligned}$$

令

$$x=:\prod_{i=1}^k{r_i}^{\theta_i}$$

其中 $r_i$ 是互不相同的质数，那么小学奥数知识告诉我们：

$$(1\ast\chi)(x)=\prod_{i=1}^k\sum_{j=0}^{\theta_i}\chi({r_i}^j)$$

• 对于 $r_i\equiv1\pmod4$ 的项，他对 $\mathrm{ans}(x)$ 的贡献为 $\theta_i+1$，而 $\sum_{j=0}^{\theta_i}\chi({r_i}^{\theta_i})$ 正好为 $\theta_i+1$；
• 对于 $r_i\equiv3\pmod4$ 的项，当 $\theta_i$ 为偶数时他对答案贡献 $1$，否则贡献 $0$，刚好与 $\sum_{j=0}^{\theta_i}\chi({r_i}^{\theta_i})=1-1+1-1\dots$ 相等；
• 对于 $r_i=2$，他对答案贡献 $1$，与 $\sum_{j=0}^{\theta_i}\chi({r_i}^{\theta_i})=1+0+0+\dots$ 相等。

最后 $\mathrm{ans}$ 要乘上 $4$，所以 $\mathrm{ans}=4\cdot(1\ast\chi)$。

$\pi$

$$\begin{aligned} \pi R^2\sim&\sum_{i=1}^{R^2}\mathrm{ans}(i)\\ \frac\pi4\sim&\frac1{R^2}\sum_{i=1}^{R^2}\frac14\mathrm{ans}(i)\\ =&\frac1{R^2}\sum_{i=1}^{R^2}\sum_{d\mid i}\chi(d)\\ =&\frac1{R^2}\sum_{d=1}^{R^2}\left\lfloor\frac{R^2}d\right\rfloor\chi(d)\\ \sim&\sum_{d=1}^{R^2}\frac{\chi(d)}{d}\\ =&\frac11+\frac02-\frac13+\frac04+\frac15+\frac06-\frac17+\dots\\ =&\frac11-\frac13+\frac15-\frac17\ldots \end{aligned}$$

参考，致谢，以及写在后面

• 二次剩余与高斯整数 - 洛谷专栏 by C3H5ClO；
• 【官方双语】隐藏在素数规律中的π by bilibili@3Blue1Brown；
• 环论 - OI Wiki；
• 请问费马二平方和定理由Don Zagier在1990年给出的最简单的证明方法是什么？ - 知乎；
• 某校内模拟赛及其题解；
• Titu Andreescu, Gabriel Dospinescu, Oleg Mushkarov, Number Theory: Concepts and Problems；
• 某 MO 同学提供的上面那本书中模 $4$ 余 $1$ 质数平方分解唯一性的证明；
• Charles Hermite, Note de M. Hermite；
• 连分数 - OI Wiki；
• 行列式 - OI Wiki；
• 郝仲杰，李启超，离散介值定理及其应用。