另一道数论题

习题6.2 14

Problem:

设\(p\)是奇素数。

1. 试求集合 \(\{1,2,\cdots ,p-2\}\) 中使得\(n\)与\(n+1\)均是\(p\)的二次剩余的元素\(n\)的个数。
2. 证明：当 \(p \geq 7\) 时，必有两个相邻的整数皆为模\(p\)的二次剩余。

Remark:

第一题由Legendre Symbol 可以显然用式子

\[N=\dfrac{1}{4}\sum_{k=1}^{p-2}(1+(\dfrac{k}{p}))(1+(\dfrac{k+1}{p}))\]

表示出来。

第二题也非常容易。注意到 \(1\) 和 \(4\) 均为二次剩余。

用反证法，若不存在相邻的整数皆为 \(p\) 的二次剩余，由于 小于 \(p\) 的整数中，二次剩余和非二次剩余的个数相等，那么二次剩余和非二次剩余必然两两间隔。(用高斯的结论)

那么问题就很显然了，若\(2,3\)中都不为二次剩余，那么在之后的部分必然会出现相邻的两个数都为二次剩余。而\(2,3\)中一旦出现二次剩余，问题也就解决了。

Proof:

考虑式子

\[N=\dfrac{1}{4}\sum_{k=1}^{p-2}(1+(\dfrac{k}{p}))(1+(\dfrac{k+1}{p}))\]

由0,1是二次剩余，式子可以改写为

\[N=\dfrac{1}{4}\sum_{k=0}^{p-1}(1+(\dfrac{k}{p}))(1+(\dfrac{k+1}{p}))-\dfrac{1}{2}-\dfrac{1+(\dfrac{-1}{p})}{4}\\ =\dfrac{1}{4}\sum_{k=0}^{p-1}(1+(\dfrac{k}{p}))(1+(\dfrac{k+1}{p}))-\dfrac{3+(\dfrac{-1}{p}))}{4}\\ \]

考虑式子的左半部分，注意到

\[\sum_{k=0}^{p-1}(\dfrac{k}{p})=\sum_{k=0}^{p-1}(\dfrac{k+1}{p})=0\]

于是

\[ N =\dfrac{1}{4}p +\dfrac{1}{4}\sum_{k=0}^{p-1}(\dfrac{k(k+1)}{p})-\dfrac{3}{4}-(\dfrac{-1}{p})/4 \]

由于Legendre Symbol的可积性，对于\(k \neq 0\) , \((\frac{k}{p})=(\frac{k^{-1}}{p})\)

其中\(k^{-1}\)是\(k\)在模\(p\)下的逆,于是

\[\sum_{k=1}^{p-1}(\dfrac{k(k+1)}{p})=\sum_{k=1}^{p-1}(\dfrac{1+k^{-1}}{p})=\sum_{k=2}^{p}(\dfrac{k}{p})=-1 \]

因此原式化为

\[N=\dfrac{1}{4}p -1-(\dfrac{-1}{p})/4\]

若\(p \equiv 1 \pmod 4\) 则\(N=\dfrac{1}{4}p-\dfrac{5}{4}\)

若\(p \equiv 3 \pmod 4\) 则\(N=\dfrac{1}{4}p-\dfrac{3}{4}\)

于是题目1证毕，同时命题2也显然成立。