平方剰余の分布について

以下合同式の法は記載の無い限り$p$,
まず平方剰余は$\dfrac{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,...\dfrac{p-1}{2}$に対して$a^2$を$p$で割ったあまりはそれぞれ相異なり,かつある$b=p-1,p-2,...\dfrac{p+1}{2}$が存在して$a^2\equiv b^2$となるので$0$でない平方剰余はちょうど$\dfrac{p-1}{2}$個存在し,$0$を含めると$\dfrac{p+1}{2}$個となる.

次に,$0≦n< p$なる整数$n$であって$n,n+1$がともに平方剰余であるようなものは$p$が$4$で割って$1$あまる時$\dfrac{p+3}{4}$個,$3$余るとき$\dfrac{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)\equiv1$をみたすのである$m$を用いて$b-a\equiv m,b+a\equiv m^{-1}$とあらわせるので$a\equiv2^{-1}(m^{-1}-m),b\equiv2^{-1}(m^{-1}+m)$となる.よって$n\equiv 4^{-1}(m^{-2}+m^2-2)$となる.よって$p$が奇素数であることからこのような$n$の個数は$m^{-2}+m^2$が$\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 ±M^{-1}$と同値である.$-M\equiv-M^{-1}$は$M^2\equiv1$,$-M\equiv M^{-1}$は$M^2\equiv -1$と同値であることから,
・$p$を$4$で割ったあまりが$1$であるとき
平方剰余の第一補充則より$m\equiv±1$であるとき$m^{-2}+m^2$は$2$に等しく, $m\equiv±(-1)^{\dfrac{1}{2}}$であるとき$m^{-2}+m^2$は$-2$に等しく,そうでないとき$m^{-2}+m^2$はこれらと合同でなく,かつこれがとりうる値それぞれに対して同一の値をとる$m$が$4$個存在するので,これがとりうる値は$2+\dfrac{p-1-4}{4}=\dfrac{p+3}{4}$種類.
・$p$を$4$で割ったあまりが$3$であるとき
同様に,平方剰余の第一補充則より$m\equiv±1$であるとき$m^{-2}+m^2$は1に等しく,そうでないとき$m^{-2}+m^2$はこれと合同でなく,かつこれがとりうる値それぞれに対して同一の値をとる$m$が$4$個存在するので,これがとりうる値は$1+\dfrac{p-1-2}{4}=\dfrac{p+1}{4}$種類.

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