听说有人在催我写博客

1. x2+y2x^2+y^2形式的素数

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

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

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

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

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

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

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

素数 存在的某组解
22 (1,1)(1,1)
33 无解
55 (1,2)(1, 2)
77 无解
1111 无解
1313 (2,3)(2, 3)
1717 (1,4)(1, 4)
1919 无解

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

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

模数 可能的余数
33 00, 11
44 00, 11
55 00, 11, 44
⋯\cdots ⋯\cdots

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

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

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

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

p=2 或者 p≡1(mod4)p = 2 \text{ 或者 } p \equiv 1 \pmod{4}

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

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

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

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

z2=−1(modp)z^2=-1\pmod{p}

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

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

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

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

ap≡a(modp)a^{p}\equiv a \pmod{p}

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

zp−1≡1(modp)z^{p-1}\equiv 1\pmod{p}

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

(z2)p−12=zp−1≡1(modp)(z^2)^{\frac{p-1}{2}}=z^{p-1}\equiv 1\pmod{p}

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

(−1)p−12≡1(modp)(-1)^{\frac{p-1}{2}}\equiv 1\pmod{p}

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

p≡1(mod4)p\equiv 1\pmod{4}

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

  • ∃x∈Zp∗ s.t. x2≡t(modp)  ⟺  tp−12≡1(modp)\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}
  • ∄x∈Zp∗ s.t. x2≡t(modp)  ⟺  tp−12≡−1(modp)\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}

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

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

勒让德符号

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

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

欧拉判据

(tp)=tp−12(modp)\left( \dfrac{t}{p} \right) = t^{\frac{p-1}{2}}\pmod{p}

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

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

计算应用：

  • （利用整数标准分解计算勒让德符号） (tp)=(±1p)(2p)r(q1p)l1⋯(qsp)ls\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}

这时回到原问题 z2≡−1(modp)z^2\equiv -1\pmod{p} ，问题就很清楚了。

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