一个素数拆分成特定形式平方和的例子

听说有人在催我写博客

1. $x^2+y^2$形式的素数

考虑这样一个十分经典的问题：

对于不定方程 $x^2+y^2=p$，其中 $p$ 为正素数，那么该方程是否存在整数解？

OK，我们把问题简化一下：

对于不定方程 $x^2+y^2\equiv 0\pmod{p}$，其中 $p$ 为正素数，那么该方程是否存在非平凡整数解？

1.1 探索这样素数的必要条件（性质）

1.1.1 利用完全平方数的同余性质

先尝试几个小的素数，我们观察一下规律：

素数	存在的某组解
$2$	$(1,1)$
$3$	无解
$5$	$(1, 2)$
$7$	无解
$11$	无解
$13$	$(2, 3)$
$17$	$(1, 4)$
$19$	无解

相信这里大家已经发现一些规律了。让我们进一步进行探索。

对同余的性质比较熟悉的小伙伴会注意到，完全平方数在同余情况下会呈现一些规律，比如：

模数	可能的余数
$3$	$0$, $1$
$4$	$0$, $1$
$5$	$0$, $1$, $4$
$\cdots$	$\cdots$

是的，我们可以看到，上述列出的小素数中，除了特殊的素数 $2$ ，只要 $p\equiv 3\pmod{4}$ 我们就枚举不出解，而当然 $p\equiv 1\pmod{4}$ 的时候，我们总是找到了一组解。

为了方便讨论，之后的 $p$ 均考虑为正奇素数。

要想要排除掉 $p\equiv 3\pmod{4}$ 这个情况其实是很容易的。只需要在方程 $x^2 + y^2=p$ 两端同时模掉 $4$ ，根据前面的铺垫，可以知道 $x^2 + y^2 \pmod{4}$ 只会有三种取值，即 $0$, $1$, $2$，这说明对于正奇素数只可能有 $p\equiv 1\pmod{4}$ 。

此时我们获得了正素数 $p=x^2+y^2$ 有解的一个必要条件：

$p = 2 \text{ 或者 } p \equiv 1 \pmod{4}$

1.1.2 利用二次同余方程（二次剩余）

到这里有经验的伙伴就看出来，不妨设 $y\neq 0$ ，把变量挪到一边那么就有：

$\left(xy^{-1}\right)^2=-1\pmod{p}$

设 $z=xy^{-1}$ ，那么方程就转化为：

$z^2=-1\pmod{p}$

问题即变成了，$-1$ 是否能在 $\mathbb{Z}_p$ 中开根号，或说 $\mathbb{Z}_p$ 中是否有一个其平方为 $-1$ 的元素？

---

先停一停，让我们在这里插播一个同余理论中十分重要的定理：

费马小定理（Fermat’s little theorem）

对于一个素数 $p$ ，如果 整数 $a$ 与 $p$ 互素 ，那么 $a^{p-1}\equiv 1\pmod{p}$
同样地也可以将特殊情况囊括进去，即对 任意整数 $a$ 都有：

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

如果我们把这个定理应用于 $z$ ，那么就有：

$z^{p-1}\equiv 1\pmod{p}$

同时我们先前已经假设 $p$ 为奇素数，那么 $p-1$ 实际上就是偶数，也就有：

$(z^2)^{\frac{p-1}{2}}=z^{p-1}\equiv 1\pmod{p}$

---

好的我们回到刚刚的问题，注意到两个条件 $(z^2)^{\frac{p-1}{2}}=z^{p-1}\equiv 1\pmod{p}$ 以及 $z^2=-1\pmod{p}$ ，结合起来就是：

$(-1)^{\frac{p-1}{2}}\equiv 1\pmod{p}$

这个等式并不总是成立，我们注意到，只有当 $\frac{p-1}{2}$ 也是偶数的时候，才成立。殊途同归，我们了一个相同的必要条件：

$p\equiv 1\pmod{4}$

走到这里其实我们其实可以更进一步，将上述 $-1$ 考虑为更一般的整数 $t$ （不为 $p$ 的倍数），那么不难证明：

• $\exists x\in\mathbb{Z}_p^{*}\text{ s.t. } x^2\equiv t\pmod{p}\iff t^{\frac{p-1}{2}}\equiv 1\pmod{p}$
• $\not\exists x\in\mathbb{Z}_p^{*}\text{ s.t. } x^2\equiv t\pmod{p}\iff t^{\frac{p-1}{2}}\equiv -1\pmod{p}$

（注意到由费马小定理， $t^{p-1}-1 = \left(t^{\frac{p-1}{2}}-1\right)\left(t^{\frac{p-1}{2}} + 1\right)\equiv 0\pmod{p}$，且 $\mathbb{Z}_p$ 为整环）

这种判别 $\mathbb{Z}_p^*$ 上某个元素是否能开方的方法称为欧拉判据，而上述这样的元素开方问题称为二次剩余问题，如果在模素数 $p$ 的情况下，对 $t\in\mathbb{Z}_p^{*}$ 有 $\exists x\in\mathbb{Z}_p^{*}\text{ s.t. } x^2\equiv t\pmod{p}$，那么就称 $t$ 为 素数 $p$ 的二次剩余，否则称为二次非剩余。我们常常用勒让德符号（Legendre symbol） 来表示：

勒让德符号

$\left( \dfrac{t}{p} \right) = \begin{cases} 1 & t \text{ 是} p \text{ 的二次剩余} \\ -1 & t \text{ 是} p \text{ 的二次非剩余} \\ 0 & t \text{ 是} p \text{ 的倍数} \end{cases}$

将上述我们所讨论的内容总结成定理，就是下面欧拉判别式：

欧拉判据

$\left( \dfrac{t}{p} \right) = t^{\frac{p-1}{2}}\pmod{p}$

当然，二次剩余的理论十分深刻，我们这里暂时就不做深刻讨论，此处不加证明地给出几个有关奇素数 $p$ 勒让德符号的计算规律：

• （积性）若 $p \not| m\cdot n$ ，则有： $\left( \dfrac{m}{p} \right) \left( \dfrac{n}{p} \right) = \left( \dfrac{mn}{p} \right)$
• （平移不变性） $\forall k\in \mathbb{Z}$ ，总有 $\left( \dfrac{kp+t}{p} \right) = \left( \dfrac{t}{p} \right)$
• （单位元(unit)的勒让德符号） $\left( \dfrac{1}{p} \right) = 1$ ； $\left( \dfrac{-1}{p} \right) = (-1)^{\frac{p-1}{2}}$
• （偶素数的勒让德符号） $\left( \dfrac{2}{p} \right) = (-1)^{\frac{p^2-1}{8}}$
• （二次互反律）对两个不等的奇素数 $p, q$ 有： $\left( \dfrac{p}{q} \right)\left( \dfrac{q}{p} \right) = (-1) ^ {\frac{1}{2}(p - 1)(q - 1)}$

计算应用：

• （利用整数标准分解计算勒让德符号） $\left( \dfrac{t}{p} \right) = \left( \dfrac{\pm 1}{p} \right)\left( \dfrac{2}{p} \right) ^ r \left( \dfrac{q_ 1}{p} \right) ^ {l_ 1} \cdots \left( \dfrac{q_ s}{p} \right) ^ {l_ s}$

这时回到原问题 $z^2\equiv -1\pmod{p}$ ，问题就很清楚了。

---

注：勒让德符号能一定意义上推广为雅可比符号，利用雅克比符号及其相关性质，我们可以类似于辗转相除法求得各种形如 $x^2\equiv a\pmod{n}$ （其中这里不再要求 $n$ 为奇素数）解的存在性问题。

1.1.3 构造的方法

对于这个问题，其实我们有一个构造型的结果，说明 $p\equiv 1\pmod{4}$ 时 $x^2\equiv -1 \pmod{p}$ 总是有解的。

---

这里还是会涉及到一个重要数论/代数定理：

威尔逊定理（Wilson’s theorem）

对于一个正整数 $p$ ，有：

$p \text{ 为素数 } \iff (p-1)!\equiv -1\pmod{p}$

这个定理的含义可以如此理解：考虑域 $\mathbb{Z}_p$ 上的方程 $x^{p-1} - 1 \equiv 0\pmod{p}$ ，那么它的根就是 $\mathbb{Z}_p$ 的所有非零元素，于是根据韦达定理有：

$\begin{aligned} \prod_{i=1}^{p-1} x_i \equiv -1\pmod{p} &\iff \prod_{i=1}^{p-1} i \equiv -1\pmod{p} \\ &\iff (p-1)!\equiv -1\pmod{p} \end{aligned}$

到这里我又想多嘴一下，其实Wilson定理可以使用Sylow第三定理进行证明。

Sylow第三定理

设有限群 $|G|=p^{\alpha} m$ ，其中 $p\not| m$ ，那么 $G$ 的 $\text{Sylow-}p$ 子群（即 $G$ 的 $p^{\alpha}$ 阶子群） 的个数 $N_p$ 满足：

• $N_p = \left[ G:N_G(P) \right]$
• $N_p\equiv 1\pmod{p}$
• $N_p\mid m$

其中 $N_G(P)=\left\{ g\in G\mid gPg^{-1}=P \right\}$ 为 $P$ 在 $G$ 中的正规化子。

对整数 $p$ ，考虑置换群 $S_p$ 的 $\text{Sylow-}p$ 子群，注意到 $|S_p|=p!$。

若 $p$ 为素数，那么 $S_p$ 的 $\text{Sylow-}p$ 子群的阶恰好为 $p$，从而 $S_p$ 的 $\text{Sylow-}p$ 子群恰为各个不同 $p$-循环生成的循环子群，这样的子群全体记为 $\text{Syl}_p(S_p)$，容易知道 $S_p$ 的 $\text{Sylow-}p$ 子群个数 $N_p = |\text{Syl}_p(S_p)|=\dfrac{p!}{p \cdot (p-1)} = (p-2)!$ （除以的 $p$ 是注意到 $(i_1\ i_2\ \cdots\ i_p)$ 与 $(i_2\ i_3\ \cdots\ i_p\ i_1)$是等价的；除以的 $(p-1)$ 是因为循环群的阶数是 $(p-1)$）。

从而根据 Sylow第三定理：

$(p-2)!\equiv 1\pmod p$

即

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

若 $p$ 不是素数，那么 $|\text{Syl}_p(S_p)|\neq (p-2)!$，具体请读着自行计算。

---

现在回到我们的问题上，考虑 $p=4k+1$ 的情形。

注意到由Wilson定理：

$(4k)!\equiv -1\pmod{p}$

即：

$\begin{aligned} &(4k)!\equiv -1\pmod{4k+1}\\ \iff &(4k)\cdots(2k+1) \cdot (2k)! \equiv -1\pmod{4k+1}\\ \iff &(-1)\cdots(-2k) \cdot (2k)! \equiv -1\pmod{4k+1}\\ \iff &(-1)^{2k} \cdot \left((2k)!\right)^2 \equiv -1\pmod{4k+1}\\ \iff &\left((2k)!\right)^2 \equiv -1\pmod{4k+1} \end{aligned}$

即取 $x=2k!$ ，即可。

1.2 必要条件是否充分？

1.2.1 数论的方法

1.2.2 几何（格）的方法

1.3. 一个例子：$x^2 + xy + y^2$ 形式的素数