平方剰余の分布について

以下合同式の法は記載の無い限り$p$,
まず平方剰余は${\displaystyle \frac{p+1}{2}}$個存在する.
以下この事実の証明(わかる人は読み飛ばしてOK)
任意の$0<a<b<p$なる整数$a,b$が$a^2\equiv b^2$をみたすことと$a^2-b^2=(a-b)(a+b)$が$p$で割り切れることは同値であり,$0<a<b<p$から$a-b$は$p$で割り切れないのでこれは$a+b$が$p$で割り切れる,すなわち$a\equiv -b$と同値である.
よって$a=1,2,...{\displaystyle \frac{p-1}{2}}$に対して$a^2$を$p$で割ったあまりはそれぞれ相異なり,かつある$b=p-1,p-2,...{\displaystyle \frac{p+1}{2}}$が存在して$a^2\equiv b^2$となるので$0$でない平方剰余はちょうど${\displaystyle \frac{p-1}{2}}$個存在し,$0$を含めると${\displaystyle \frac{p+1}{2}}$個となる.

次に,$0\leqq n<p$なる整数$n$であって$n,n+1$がともに平方剰余であるようなものは$p$が$4$で割って$1$あまる時${\displaystyle \frac{p+3}{4}}$個,$3$余るとき${\displaystyle \frac{p+1}{4}}$個存在することを示す.
$n$がこの条件をみたすことはある整数$a,b$が存在して$a^2\equiv n$かつ$b^2\equiv n+1$をみたすことと同値.このような$a,b$は$b^2-a^2=(b-a)(b+a)\equiv 1$をみたすのである$m$を用いて$b-a\equiv m,b+a\equiv m^{-1}$とあらわせるので$a\equiv 2^{-1}(m^{-1}-m),b\equiv 2^{-1}(m^{-1}+m)$となる.よって$n\equiv 4^{-1}(m^{-2}+m^2-2)$となる.よって$p$が奇素数であることからこのような$n$の個数は$m^{-2}+m^2$が$\mathrm{mod}p$においてとりうる値の数と一致する.ある$m\not\equiv M$なる$0$より大きく$p-1$以下の整数$m,M$が存在して$m^{-2}+m^2\equiv M^{-2}+M^2$が成り立つことは適切な式変形により$m\equiv -M$または$m\equiv \pm M^{-1}$と同値である.$-M\equiv -M^{-1}$は$M^2\equiv 1$,$-M\equiv M^{-1}$は$M^2\equiv -1$と同値であることから,
・$p$を$4$で割ったあまりが$1$であるとき
平方剰余の第一補充則より$m\equiv \pm 1$であるとき$m^{-2}+m^2$は$2$に等しく, $m\equiv \pm (-1{)}^{{\displaystyle \frac{1}{2}}}$であるとき$m^{-2}+m^2$は$-2$に等しく,そうでないとき$m^{-2}+m^2$はこれらと合同でなく,かつこれがとりうる値それぞれに対して同一の値をとる$m$が$4$個存在するので,これがとりうる値は$2+{\displaystyle \frac{p-1-4}{4}}={\displaystyle \frac{p+3}{4}}$種類.
・$p$を$4$で割ったあまりが$3$であるとき
同様に,平方剰余の第一補充則より$m\equiv \pm 1$であるとき$m^{-2}+m^2$は1に等しく,そうでないとき$m^{-2}+m^2$はこれと合同でなく,かつこれがとりうる値それぞれに対して同一の値をとる$m$が$4$個存在するので,これがとりうる値は$1+{\displaystyle \frac{p-1-2}{4}}={\displaystyle \frac{p+1}{4}}$種類.

さて,各グループに対して,それに属する整数$a$であって$a$が平方剰余であり,かつ$a+1$が平方剰余でないようなものがちょうど$1$つ存在するので,このような$a$の個数はグループの個数に一致する.ところで,このような$a$の個数は平方剰余$a$であって,「$a,a+1$がともに平方剰余である」が成り立たないようなものの個数であるので,先ほどの結果から
・$p$を$4$で割ったあまりが$1$であるとき
${\displaystyle \frac{p+1}{2}}-{\displaystyle \frac{p+3}{4}}={\displaystyle \frac{p-1}{4}}$個
・$p$を$4$で割ったあまりが3であるとき
${\displaystyle \frac{p+1}{2}}-{\displaystyle \frac{p+1}{4}}={\displaystyle \frac{p+1}{4}}$個
であることがわかる.