平方剰余
この現象は、抽象代数の言葉でよく説明できる。法と互いに素な合同類は、環 Z/nZ の単元群と呼ばれる乗法に関する群であり、平方数はその部分群となる。異なる非剰余は異なる剰余類に属している可能性があり、それらの積がどの類に属するかを予測する単純なルールは存在しない。素数を法として、平方数の部分群と単一の剰余類が存在するのみである。
たとえば15を法とする非剰余3と5の積、または非剰余5と剰余9の積、または2つの剰余9と10の積がすべてゼロであるという事実は、完全な環 Z/nZ の中にあることから生じ、この環は合成数 n の 零因子を持つ。
このため、一部の著者は、平方剰余 a は平方数であるだけでなく、法 n と互いに素でなければならないという定義を追加している。(a が n と互いに素となるのは、a が n と互いに素である場合でかつその場合に限る。)
これで話は片付くが、本記事では剰余が法と互いに素であるという定義は用いない。
以下の式の証明は容易である。
| ∑ n = M + 1 M + N ( n q ) | < q log  q {\displaystyle \left|\textstyle \sum \limits _{n=M+1}^{M+N}\left({\dfrac {n}{q}}\right)\right|<{\sqrt {q}}\log q}
実際、
| ∑ n = M + 1 M + N ( n q ) | < 4 π 2 q log  q + 0.41 q + 0.61 {\displaystyle \left|\textstyle \sum \limits _{n=M+1}^{M+N}\left({\dfrac {n}{q}}\right)\right|<{\frac {4}{\pi ^{2}}}{\sqrt {q}}\log q+0.41{\sqrt {q}}+0.61}
となる。
モンゴメリー(英語版)(Montgomery)とヴォーン(英語版)(Vaughan)は1977年にこれを改良し、一般化されたリーマン予想が真である場合、以下の式が成り立つことを示した。
p を奇素数とする。二次超過 (Quadratic excess) E(p) は、範囲 (0, p/2) の平方剰余の数から 範囲 (p/2, p) の平方剰余の数を引いたものである(オンライン整数列大辞典の数列 A178153)。p ≡ 1 mod 4 となる p では、−1 が平方剰余であり、剰余は r ↔ p - r に対して対称であるので過剰はゼロである。p ≡ 3 mod 4 となる p では、超過 E は常に正である。