二次剩余：若 \((m,n)=1,m>1\) ，满足 \(\exists x\in Z,x^2\equiv n\:(mod~m)\) ，则称 \(n\) 为一个关于 \(m\) 的二次剩余。反之，若不存在 \(x\) ，则称 \(n\) 为一个关于 \(m\) 的二次非剩余
定义勒让德符号（通常约定 \(p\) 是素数）：
\((\frac ap)=\begin{cases} 1 &\text{if } a是p的二次剩余 \\ -1 &\text{if } a是p的非二次剩余\\ 0 &\text{if } p\mid a \end{cases}\)
定理 \(1\) ：由于 \(x^2\equiv y^2\:(mod~p)\iff x\equiv \pm y\:(mod~p)\) ，所以模 \(p\) 的二次剩余实际上恰好是 \(1^2,2^2,...,(\frac {p-1}2)^2\) 。从而模 \(p\) 的缩系恰有 \(\frac{p-1}2\) 个二次剩余与二次非剩余
定理 \(2\) ：方程 \(x^2\equiv a\:(mod~p)\) 恰有 \(1+(\frac ap)\) 个解
定理 \(3\) ：（欧拉准则） \((\frac ap)\equiv a^{\frac{p-1}2}\:(mod~p)\)
证明：根据拉格朗日定理，因为 \(x^{\frac{p-1}2}\equiv 1\:(mod~p)\) 至多有 \(\frac{p-1}2\) 个根，而 \(1^2,2^2,...,(\frac{p-1}2)^2\) 都是它的根，从而全体二次剩余就是它的全部根。
对非二次剩余， \(a^{p-1}-1=(a^{\frac{p-1}2}-1)(a^{\frac{p-1}2}+1)\equiv 0\:(mod~p)\) ，但它又不能是 \(a^{\frac{p-1}2}-1\equiv 0\:(mod~p)\) 的根，只能是 \(a^{\frac{p-1}2}+1\equiv 0\:(mod~p)\) 的根
欧拉准则有两个较重要的推论。
定理 \(4\) ： \((\frac {ab}p)=(\frac ap)(\frac bp)\) ，换而言之，勒让德符号是积性的。
定理 \(5\) ： \(\large(\frac{\frac 1a}p)=(\frac ap)\) ，因为 \(x^2\equiv a\:(mod~p)\iff (\frac 1ax)^2\equiv \frac 1a\:(mod~p)\)
定理 \(6\) ： \((\frac {-1}p)=(-1)^{\frac{p-1}2}\) ，换而言之，当 \(p\equiv 1\:(mod~4)\) ， \(-1\) 是它的二次剩余，当 \(p\equiv 3\:(mod~4)\) ， \(-1\) 是它的二次非剩余。
结合积性 \((\frac{-x}p)=(\frac xp)(\frac{-1}p)\)，可以直接知道 \(p\equiv 1\:(mod~4)\) 的二次剩余可以正负两两配对，而 \(p\equiv 3\:(mod~4)\) 满足 \(x,-x\) 中恰有一个二次剩余。
定理 \(7\) ：（二次互反律）对奇素数 \(p\ne q\) 有 \((\frac pq)(\frac qp)=(-1)^{\frac{p-1}2\cdot \frac{q-1}2}\)
证明：回忆 \(x_1^2+x_2^2+...+x_q^2\equiv 1\:(mod~p)\) 的解数 \(N=p^{q-1}+((-1)^{\frac{p-1}2}p)^{\frac{q-1}2}\equiv 1+(-1)^{\frac{p-1}2\cdot \frac{q-1}2}(\frac pq)\:(mod~q)\)
我们可以证明 \(N\equiv 1+(\frac qp)\:(mod~q)\) ，因为 \((x_1,x_2,...,x_q)=X\) 是一组解的话， \(TX=(x_2,x_3,...,x_q,x_1)\) 也是一组解， \(T^2X,T^3X,..,T^{q-1}X\) 配在一起就有 \(q\) 个，从而 \(N\) 在模 \(q\) 意义下只剩下 \(x_1=x_2=...=x_q\) 的解，即 \(qx^2\equiv 1\:(mod~p)\) 的解数，即 \((qx)^2\equiv q\:(mod~p)\) 的解数
定理 \(8\) ：\((\frac 2p)=(-1)^{\frac{p^2-1}8}\) ，即 \(2\) 是模 \(p\) 的二次剩余当且仅当 \(p\equiv \pm1\:(mod~8)\)
证明：
\( \begin{aligned} (\frac{p-1}2)!&\equiv \prod\limits_{i=1}^{[\frac {p-1}4]}2i\cdot \prod\limits_{i=1}^{[\frac {p+1}4]}(2i+1)\\ &\equiv 2^{[\frac{p-1}4]}\cdot ([\frac{p-1}4])!\cdot \prod\limits_{i=1}^{[\frac {p+1}4]}(2i+1-p)\\ &\equiv 2^{[\frac{p-1}4]+[\frac {p+1}4]}\cdot(-1)^{[\frac {p+1}4]}([\frac{p-1}4])!\cdot\prod\limits_{i=1}^{[\frac {p+1}4]}(\frac{p-1}2-i)\\ &\equiv 2^{\frac{p-1}2}\cdot(-1)^{[\frac {p+1}4]}(\frac{p-1}2)! \end{aligned} \)
用到了 \(Hermit\) 恒等式。从而 \(2^{\frac{p-1}2}\equiv (-1)^{[\frac {p+1}4]-1}\:(mod~p)\) ，分类讨论给出结果
这就是二次剩余 \(Gauss\) 引理证明的特例。
定理 \(9\) ： \(x^2-y^2\equiv a\:(mod~p)\) 当 \(p\nmid a\) 时有 \(p-1\) 个解，当 \(p\mid a\) 时有 \(2p-1\) 个解
证明： \((x-y)(x+y)\equiv a\:(mod~p)\) ，建立 \((x-y,x+y)\rightarrow (x,y)\:(mod~p)\) 的双射即可。
定理 \(10\) ：\(a,b,c\in Z\) 满足 \(p\nmid a\) ，则
\( \sum\limits_{k=0}^{p-1}(\frac{ak^2+bk+c}{p})= \begin{cases} (p-1)(\frac ap) &\text{if }p\mid b^2-4ac\\ -(\frac ap) &\text{if }p\nmid b^2-4ac \end{cases} \)
特别地，对 \(a\ne b\:(mod~p),\sum\limits_{k=0}^{p-1}(\frac{(k+a)(k+b)}{p})=-1\)
证明：考虑 \(\large (\frac ap)(\frac{k^2+\frac bak+\frac ca}p)=(\frac ap)(\frac{(k+\frac b{2a})^2+c-(\frac b{2a})^2}p)\) 换元为 \((\frac ap)(\frac{t^2+s}p)\)
当 \(p\mid b^2-4ac,s=0\) 时结论显然，否则考虑方程 \(x\equiv t^2+s\:(mod~p)\) ，这正是定理 \(9\) 的方程，配合定理 \(2\) 完成证明。
我们在之后会遇到很多 \(\sum(\frac{f(k)}p)\) 相关问题，我们将展示一些计算手法。在此之前先给出该定理的基本推论：
定理 \(11\) ： \(x^2+y^2\equiv a\:(mod~p)\) 当 \(a\mid p\) 时解数为 \(p+(p-1)(-1)^{\frac{p-1}2}\) ，否则为 \(p-(-1)^{\frac{p-1}2}\)
证明：直接套用定理 \(2\) 和 \(9\) ，或使用高斯和。
定理 \(12\) ：若 \(p\equiv 1\:(mod~4)\) ，则 \(| \{r^4\:(mod~p)\mid0\le r\le p-1\}|=\frac{p-1}4+1\) ，若 \(p\equiv 3\:(mod~4)\) ，则 \(\{r^4\:(mod~p)\mid0\le r\le p-1\}=\{r^2\:(mod~p)\mid0\le r\le p-1\}\)
我们将在这里留下一些比较容易的问题，可以作为基础概念的掌握：
-
给定非负整数 \(n\) 和素数 \(p\equiv 7\:(mod~8)\) ，证明： \(\sum\limits_{k=1}^{p-1}\{\frac{k^{2^n}}p+\frac 12\}=\frac{p-1}2\)
-
方程 \(x^8\equiv 16\:(mod~p)\) 至少有一个解
-
素数 \(p\equiv 3\:(mod~8)\) ， \(p\mid a\) ，求证 \(\{2^n+a\mid n=1,2,...\}\) 中只有有限个完全平方数
-
素数 \(p\mid n^4-n^3+2n^2+n+1,n>1\) ，求证 \(p\equiv 1,4\:(mod~ 15)\)
-
素数 \(p=a^2+b^2,2\nmid a\) ，证明 \((\frac{a}p)=1\)
例1
是否存在非常数整系数多项式 \(f\) 对所有 \(n>2\) ， \(f(0),f(1),f(2),...,f(n-1)\) 模 \(n\) 给出至多 \(0.499n\) 个不同的余数？
存在。
我们可以将 \((\frac 1p),(\frac 2p),...,(\frac{-1}p)\) 看作若干 \(-1,1\) 的连续段构成的序列，其中段落的交界处满足 \((\frac {n(n+1)}p)=-1\) （反之为 \(1\) ），由定理 \(10\) 给出 \(\sum\limits_{k=1}^{p-1}(\frac{k(k+1)}p)=-1\) ，可以计算得到交界处个数为 \(\frac{p-1}2\)
那么 \(f(x)=\prod_{p<100}p(x^2-1)^2\) 满足条件
因为 \(x^4-1\) 对 \(p\equiv 1\:(mod~4)\) 只有 \(\frac 14p\) 左右个取值，
而对 \(p\equiv 3\:(mod~4)\) ，由于每个段落末尾的平方剩余 （也就是交界处末尾的 \(1\) ，有一半的交界处是 \(1\) 的结尾）取不到，有 \(\frac 18p\) 左右的平方剩余取不到，那么 \((x^4-1)^2\) 就有 \(\frac 18p\) 左右的平方剩余取不到（可以验证： \(f(x)=x^2\) 是模 \(p\) 平方剩余系的双射）
注：
设 \(p\) 是奇素数，则满足 \(n\in \{1,2,...,p-2\},(\frac np)=(\frac{n+1}p)=1\) 的 \(n\) 共有 \(\frac{p-(-1)^{\frac{p-1}2}}4-1\)
证明： \(1\) 的段数共 \(\lceil\frac{x+1}2\rceil\) ，结合 \(1\) 共有 \(\frac {p-1}2\) 个，给出结论。
例2
已知素数 \(p\equiv 3\:(mod~4)\) ，对于一个由 \(\pm 1,\pm 2,...,\pm\frac{p-1}2\) 构成的长度不大于 \(\frac{p-1}2\) 的数列（可重复），若包含了正负项各一半，则称该数列是“平衡的”。求证：平衡数列的数量 \(M_p\) 不为完全平方数。
\( \begin{aligned} M_p&=\sum\limits_{k=1}^{\frac{p-1}2}C_{2k}^k\\ &\equiv \sum\limits_{k=1}^{\frac{p-1}2}\frac{(2k)!}{(2k)!!(2k)!!}\\ &\equiv \sum\limits_{k=1}^{\frac{p-1}2}\frac{(2k-1)!!}{(2k)!!}\\ &=\sum\limits_{k=1}^{\frac{p-1}2}(\frac{(2k+1)(2k-1)!!}{(2k)!!}-\frac{2k(2k-1)!!}{(2k)!!})\\ &\equiv \frac{p!!}{(p-1)!!}-1\equiv -1\:(mod~p) \end{aligned} \)
而 \((\frac{-1}p)=-1\) ，证毕
注：直接用 \(p\ge 2n+1\) 时有 \(C_{2n}^n\equiv (-4)^nC_{\frac{p-1}2}^n\:(mod~p)\) 也可做，这个同余式也是把分子分母处理一下就好了。
例3
对 \(p>2\) ，最小的模 \(p\) 正二次非剩余小于 \(\frac 12+\sqrt p\)
设最小正二次非剩余是 \(q\) ，并令 \(p=kq+r,r<q\) ，我们很显然希望 \(k\ge q\) （类似的结果） ，于是考虑 \(1=(\frac{q-r}p)=(\frac {k+1}p)(\frac qp)\) （因为 \(q\) 是最小的，肯定是要找一个比它更小的数利用这个性质）
于是 \((\frac{k+1}q)=1\) ，从而 \(k\ge q-1\) ，立即给出结果
下面的例子与二次互反律有关。比较重要的是：
\(p\equiv 1\:(mod~3)\iff (\frac{-3}p)=1\)
\(p\equiv \pm 1\:(mod~5)\iff (\frac{5}p)=1\)
例4
证明：不存在整数 \(x,y\) 使得 \(x^3-x+9=5y^2\)
\(x(x^2-1)\equiv 1\:(mod~5)\) ，枚举给出 \(x\equiv 2\:(mod~5)\) 是唯一的解，那么设 \(p\mid x(x^2-1)\) ，有 \((5y)^2\equiv 9\cdot 5\:(mod~p)\) ，从而 \((\frac 5p)=1\) ，那么 \(p\equiv \pm 1\:(mod~5)\) ，这与 \(x\equiv 2\:(mod~5)\) 矛盾。
一些其它的不定方程：
-
\(8xy=x+y+z^2\)
-
\(x^3+2x+1=2^n\) ，所有解是 \((x,n)=(0,0)(1,2)\)
这两个都可以寻求一个类因式分解来做。
例5
证明：若 \(\varphi(5^m-1)=5^n-1\) ，则 \((m,n)>1\)
假设 \((m,n)=1\) ，那么 \((5^m-1,5^n-1)=4\)
设 \(5^m-1=2^w\prod\limits_{i=1}^t p_i^{\alpha_i}\) ，由于 \((5^m-1,\varphi(5^m-1))=4\) ， \(\alpha_i=1\) ，显然 \(w\ge 2\) ，若 \(w=3\) ，则 \(t=0\) ，无解，只能 \(w=2\)
现在 \(5^m\equiv 1\:(mod~p_i)\) ，由于 \(w=2\) ，可知 \(m\) 必须是奇数，那么 \((\frac 5{p_i})=1\) ，给出 \(p_i\equiv \pm 1\:(mod~5)\)
\(p_i-1\mid \varphi(5^m-1)=5^n-1\) ，那么 \(5\nmid p_i-1\) ，只能是 \(p_i\equiv -1\:(mod~5)\)
接下来看 \(\prod(p_i-1)\equiv (-2)^t\:(mod~5)\) ，有 \(5^n-1\equiv 2\cdot(-2)^t\:(mod~5)\)
由于 \(5^m-1=4p_1p_2...p_t\equiv -1\:(mod~5)\) ，所以 \(2\mid t\)，然而前面给出 \(1\equiv 3^{t+1}\:(mod~5)\) ，矛盾。
例6
\(2^{m+1}+1\mid 3^{2^m}+1\iff 2^{m+1}+1\) 是素数
左推右： \(\delta_{2^{m+1}}(3)=2^{m+1}\)
右推左： \(3^{2^m}\equiv -1\:(mod~2^{m+1}+1)\iff(\frac{3}{2^{m+1}+1})=-1\) ，只要证这个，由二次互反律显然
例7
求所有正整数 \(a,b\) ，使得 \(6a+6b-1\mid 6ab-a-b\)
设 \(36ab-1=k(6a+6b-1)\) ，可以看到 \(k\equiv 1\:(mod~6)\)
类因式分解 \((6a-k)(6b-k)=k^2-k+1\) ，根据 \(6a-k\equiv -1\:(mod~6)\) ，那么存在 \(p\mid -1\:(mod~6),p\mid k^2-k+1\) ，于是 \((2k-1)^2\equiv -3\:(mod~p)\) ，这与 \(p\equiv 2\:(mod~3)\)
接下来的几个例子有一定难度。
例8
设函数 \(f,g:N\rightarrow N\) 满足 \(g\) 是满射，对任意 \(n\) 都有 \(2f^2(n)=n^2+g^2(n)\) ，并且 \(|f(n)-n|\le 2004\sqrt n\) 。求证： \(f\) 有无穷多不动点。
回忆 \(2c^2=a^2+b^2\iff c^4=(\frac{a^2-b^2}2)^2+(ab)^2\) ，给出 \(c^2=u^2+v^2,ab=2uv\) ，进一步地 \(ab=\pm2((m^2-n^2)^2-(2mn)^2)=\pm 2(m^2-2mn-n^2)(m^2+2mn-n^2)\)
我们说 \(p\mid (m\pm n)^2-2n^2\) 要求 \(p\equiv \pm 1\:(mod~8)\) ，因为 \((m\pm n)^2\equiv 2n^2\:(mod~p)\) 给出 \((\frac 2p)=1\)
现在取无穷素数序列 \(p_k,p_k\equiv 3\:(mod~8)\) （根据 \(Dirichlet\) 定理），并取 \(g(n)=p_k\) ，根据上述论证，必须有 \(p_k\mid (n,g(n))\) ，也就是 \(n=n_kp_k,f(n)=\sqrt{\frac{(1+n_k^2)}2}p_k\)
若 \(n_k\ne 1\) ，那么 \(\frac{f(n)}{n}=\sqrt\frac{1+n_k^2}{2n_k^2}\) ，根据 \(Pell\) 方程相关理论可以知道它至少是 \(\frac 75\) ，当 \(n\) 充分大时会违反 \(|f(n)-n|\le 2004\sqrt n\) ，从而 \(n_k=1\) 对充分大 \(n\) 成立。
例9
设方程 \(y^2\equiv x^3-ax\:(mod~p)\) 的解有 \(N(a)\) 个，定义 \(S(a)=\sum\limits_{x=0}^{p-1}(\frac{x^3-ax}p)\)
证明：当 \(p\equiv 3\:(mod~4)\) ，\(N(x)=p\) ，当 \(p=a^2+b^2,2\nmid a\) ，有 \(N(-1)=p+2a(-1)^{\frac{a+(p+1)/2}2}\)
这个问题很困难。对于 \(p\equiv 3\:(mod~4)\) ，可以用欧拉准则直接计算 \(\sum(x^3-ax)^{\frac{p-1}2}\) 得到结果，我们只讲 \(p\equiv 1\:(mod~4)\) 的情况
首先 \(S(ab^2)=S(a)(\frac bp)\) ，因为 \(\sum (\frac{x^3-ab^2x}p)=\sum(\frac{(bx)^3-ab^2\cdot bx}p)=(\frac bp)S(a)\)
然后 \(\sum\limits_{a=0}^{p-1}S^2(a)=2p(p-1)\) ，这是因为
\(\begin{aligned} \sum\limits_{a=0}^{p-1}S^2(a)&=\sum\limits_{k,l=0}^{p-1}(\frac kp)(\frac{k^2-a}p)(\frac lp)(\frac{l^2-a}p)\\ &=\sum\limits_{a=0}^{p-1}\sum\limits_{k,l=0}^{p-1}(\frac{(a-k^2)(a-l^2)}p)(\frac {kl}p)\\ &=-\sum\limits_{a=0}^{p-1}\sum\limits_{k,l=0}^{p-1} (\frac {kl}p)+p\sum\limits_{a=0}^{p-1}\sum\limits_{k,l=0,k^2\equiv l^2}^{p-1} (\frac {kl}p)\\ &=2p(p-1) \end{aligned}\)
用到了定理 \(10\)
接下来设 \(A=S(-1),B=S(x),(\frac xp)=-1\) ，根据 \(S(ab^2)=S(a)(\frac bp)\) 可知 \(S^2(ab^2)=S^2(a)\) ，然后 \(\sum\limits_{a=0}^{p-1}S^2(a)=\frac{p-1}2(A^2+B^2)\) ，从而 \(A^2+B^2=2p\)
我们将声称 \(A,B\) 均为偶数。有 \(A\equiv -(p+1)\:(mod~8)\)
这来自于 \(A=\sum\limits_{k=0}^{p-1}(\frac{k-1}p)(\frac{k}p)(\frac{k+1}p)\) ，然后考虑 \(\sum\limits_{k=0}^{p-1}(1+(\frac{k-1}p))(1+(\frac{k}p))(1+(\frac{k+1}p))\) 除了 \(k=0,-1,1\) 都是 \(8\) 的倍数，根据 \(p\) 模 \(8\) 讨论一下，然后把 \(\sum (\frac{k(k-1)}p),\sum(\frac kp)\) 这些减去就行
从而 \((\frac A2)^2+(\frac B2)^2=p\) ，考虑 \(\frac A2\) 模 \(4\) 的余数即可得到结论。
此外对照直接计算的方法可以给出（也就是所谓的算两次）：
对 \(p=a^2+b^2,2\nmid a\)
\(\large C_{\frac{p-1}2}^{\frac{p-1}4}\equiv 2a\cdot (-1)^{\frac{a+(p+1)/2}2}\:(mod~p)\)
例10
求所有素数 \(p\) 满足对正整数 \(a,b,c\) ，若有 \(p\mid a^2b^2+b^2c^2+c^2a^2+1\) ，就有 \(p\mid a^2b^2c^2(a^2+b^2+c^2+(abc)^2)\)
先假设 \(p\nmid abc\) ，然后假设不存在 \(a^2+b^2\equiv 0\:(mod~p)\) ，否则 \(p\mid a^2b^2+1,p\mid c^2(a^2b^2+1)+a^2+b^2\) ，也是成立的
将 \(a^2\equiv \frac{b^2c^2+1}{b^2+c^2}\:(mod~p)\) 代入我们要证的式子，我们会看到实则是要证明 \(a^2\equiv \pm 1\:(mod~p)\) ，当然轮换地也可以是另两个
我们将说明：除了很少的素数（ \(2,3,5,13,17\) ），都可以找到 \(p\) 的二次剩余 \(x,y,z\) 使得它们中没有 \(\pm 1\) 并且 \(xy+yz+zx\equiv -1\:(mod~p)\)
先令 \(x=z\) 看看，只要 \(x(x+2y)\equiv -1\:(mod~p)\) ，那么 \(y\equiv -\frac{x^2+1}{2x}\:(mod~p)\) ，\((\frac yp)=(\frac{x^2+1}p)(\frac {-2x}p)=(\frac{x^2+1}p)(\frac {-2}p)\)
我们还要求 \(y\ne \pm 1\:(mod~p)\) ，代入一看，发现就是 \(x\ne \pm 1,0\:(mod~p)\) ，很不错
我们惊喜地发现，对 \(p\equiv 3\:(mod~4)\) ， \(x,-x\) 总有一个是二次剩余，那么只要 \((\frac{x^2+1}p)(\frac {-2}p)=1\) ，选取 \(x,-x\) 中的二次剩余代入就可以了，也就是只要说 \((\frac{x^2+1}p)\) 不要全是 \(1,-1\) 就行， \(p>7\) 就行（回忆 \(\sum\limits_{i=2}^{p-2}(\frac{x^2+1}p)=-1-1-2(\frac 2p)\) ，全相等肯定不行）。
\(p\equiv 1\:(mod~4)\) 比较棘手，我们得找到 \((\frac{r^4+1}p)(\frac {-2}p)=1\) ，算一下 \(\sum\limits_{0\le r\le p-1}(\frac{r^4+1}p)\) ，它是
\(\begin{aligned} \sum\limits_{r=0}^{p-1}(\frac{r^4+1}p)&\equiv \sum\limits_{r=0}^{p-1}(r^4+1)^{\frac {p-1}2}\\ &=\sum\limits_{r=0}^{p-1}\sum\limits_{i=0}^{\frac{p-1}2}r^{4i}C_{\frac{p-1}2}^i\\ &=\sum\limits_{i=0}^{\frac{p-1}2}C_{\frac{p-1}2}^i\sum\limits_{r=0}^{p-1}r^{4i}\\ &\equiv -(C_{\frac{p-1}2}^{\frac{p-1}4}+C_{\frac{p-1}2}^{\frac{p-1}2})\:(mod~p) \end{aligned}\)
设 \(t\equiv (\frac{p-1}2)!\:(mod~p)\)
得考虑一下不合法的数 \(s^4\equiv -1\:(mod~p)\iff s^2\equiv\pm(\frac{p-1}2)!\:(mod~p)\) 有没有解得分类讨论，因为 \(1,2,...,\frac{p-1}2\) 中恰有 \(\frac{p-1}4\) 个二次非剩余
若 \(p\equiv 1\:(mod~8)\) ，就会存在这个 \(s\) ，不妨记四个解为 \(\pm s,\pm st\) ，以及 \(\pm t,\pm 1,0\) ，把这 \(9\) 个都去掉剩下的 \(\sum\limits(\frac{r^4+1}p)\equiv -(C_{\frac{p-1}2}^{\frac{p-1}4}+1)-1-4(\frac 2p)=-C_{\frac{p-1}2}^{\frac{p-1}4}-6\:(mod~p)\)
剩下 \(p-9\) 个数，希望存在 \((\frac {r^4+1}p)=1\)
如果全是 \(-1\) ，即 \(-C_{\frac{p-1}2}^{\frac{p-1}4}-6\equiv 9-p\:(mod~p)\) ，即 \(C_{\frac{p-1}2}^{\frac{p-1}4}\equiv -15\:(mod~p)\) ，那么 \(-15((\frac{p-1}4)!)^2\equiv (\frac{p-1}4)!\:(mod~p)\) ， \(-15\) 是平方剩余，但是因为 \(-16\) 是四次剩余， \((\frac{-16+1}p)=-1\) ，矛盾！
若 \(p\equiv 5\:(mod~8)\) ，对任意二次剩余 \(x\) ，都有 \(x,-x\) 中恰有一个四次剩余
不合法的是 \(0,\pm 1,\pm t\) ，剩下的 \(\sum\limits(\frac{r^4+1}p)\equiv -(C_{\frac{p-1}2}^{\frac{p-1}4}+1)-1-4(\frac 2p)=-C_{\frac{p-1}2}^{\frac{p-1}4}+2\:(mod~p)\) ，共 \(p-5\) 个数
希望有 \((\frac {r^4+1}p)=-1\)
考虑全是 \(1\)
如果把二次剩余分成连续的若干个段落，那么不存在长为 \(1\) 的段落，否则 \(x,-x\) 有一个是四次剩余，但 \(x+1,-(x-1)\) 都不是！
我们声称段落总数是 \(\frac{p-1}4\) ，这是因为 \(\sum\limits_{k=1}^{p-1}(\frac{k(k+1)}p)=-1\) ，在序列 \((\frac 1p),(\frac 2p),...,(\frac {p-1}p)\) 每个连续的 \(1\) 段落和 \(-1\) 段落末尾 \((\frac{k(k+1)}p)=-1\) ，其余为 \(1\) ，解个方程就能算出来
但是，总长是 \(\frac{p-1}2\) ，有 \(\frac{p-1}4\) 个段落，只能每个段落长为 \(2\) 了
那么 \(C_{\frac{p-1}2}^{\frac{p-1}4}\equiv -7\:(mod~p)\) ， \(-7\) 是二次剩余了， \(7\) 是二次剩余， \(9\) 也是， \(8\) 不是（ \(2\) 不是），然后 \(6,10\) 是，于是 \(3,5\) 不是， \(4\) 成为了单独的，矛盾！
当然前提是 \(p>17\) ，这个同余式 \(p=13\) 是满足的
不过例 \(9\) 中的同余式也有一定用处。当 \(p\) 足够大时， \(2a\) 是 \(2\sqrt p\) 级别的，而 \(-7,-15\) 作为奇数，要求 \(2a=p-7,p-15\) ，这是不可能的。
综上证明了命题。
另证：记 \(X_1(p)=\{(a,b,c)\mid p\mid a^2b^2+b^2c^2+c^2a^2+1\},X_2(p)=\{(a,b,c)\mid p\mid a^2b^2c^2+a^2+b^2+c^2\},0\le a,b,c\le p-1\)
对 \(p\equiv 1\:(mod~4)\) ，设 \(x^2\equiv -1\:(mod~p)\)
令 \(c=-a-b\) ，这样的三元组满足 \(a^2b^2+b^2c^2+c^2a^2+1\equiv (ab+bc+ca)^2+1\equiv (a^2+ab+b^2)^2+1\:(mod~p)\)
需要 \(Lemma\) ： \(a^2+ab+b^2\equiv x\:(mod~p)\) 至少有 \(p-1\) 个解，配个方就行。这些 \((a,b,-a-b)\) 全部在 \(X_1\) 中
我们声称满足 \(c=-a-b,a^2+ab+b^2\equiv x\:(mod~p)\) 的三元组在 \(X_2\) 中有限，当 \(a=0\) ，有 \(b^2\equiv x\:(mod~p)\) ，至多两个解，其它两个为 \(0\) 同理，有 \(6\) 个
接下来 \(a^2+b^2+c^2\equiv 2(a^2+ab+b^2)\equiv 2x\:(mod~p)\) ， \(a^2c^2\equiv (a(a+b))^2\equiv (x-b^2)^2\:(mod~p)\) （注意 \(x\) 是给定的）
关于 \(b\) 的六次多项式 \((x-b^2)^2b^2+2x\equiv 0\:(mod~p)\) 至多 \(6\) 个解，与 \(a\) 轮换，至多 \(12\) 个，总共至多 \(18\) 个，当 \(p\ge 29\) 时显然少于 \(p-1\) 个，证毕。
例11
设 \(k\) 是正整数，称质数 \(p\) 为好数，如果存在正整数 \(n\) 满足 \(p\mid n^{2^k}+k\) ，求所有的正整数 \(k\) ，使得存在无穷个好数
我们将在本例中强调二次互反律+ \(CRT\) + \(Dirichlet\) 定理的构造操作。
首先模 \(4\) 余 \(3\) 的素数满足 \(2^n\) 次剩余与 \(2\) 次剩余完全一致，所以只要寻找满足 \(p\mid n^2+k\) 的 \(n\) 即可
对完全平方数 \(k\) 显然不存在。我们将声称对于其余的 \(k\) 均存在无穷个 \(p\) ，不妨 \(k\) 无平方因子（否则并到 \(n^2\) 里去）
设 \(k=q_1q_2...q_m\)
我们的目标是找到 \(p\) 使得 \((\frac kp)=(\frac {q_1}p)(\frac {q_2}p)...(\frac{q_m}p)=-1\) ，就有 \((\frac{-k}p)=1\) ，那么只要令 \((\frac {q_1}p)=-1,(\frac{q_2}p)=...=(\frac{q_n}p)=1\) 即可
根据二次互反律只要 \((\frac p{q_1})=(-1)^{\frac{q_1+1}2}\) ，其余的 \((\frac p{q_i})=(-1)^{\frac{q_i-1}2}\) ，由 \(CRT\) 很容易做到
特别地当 \(p_1=2\) ，可以令 \(p\equiv 3\:(mod~8)\)
根据 \(Dirichlet\) 定理，这样的素数无穷，证毕
标签：剩余,frac,limits,二次,sum,mid,equiv,mod From： https://www.cnblogs.com/Rocking-Yoshi/p/18309123