平方剰余
連続値 a に対する ( a p ) {\displaystyle ({\tfrac {a}{p}})} の値はコイントスのような確率変数で擬似的に表現できる。具体的には、ポリアとヴィノグラドフ(英語版) (Vinogradov)が、1918年に(独立して)q をとする非主(non-principal)ディリクレ指標 χ(n) と任意の整数 M, N に対して、ランダウの記号を用いて以下のように表現できることを証明した。
| ∑ n = M + 1 M + N χ ( n ) | = O ( q log  q ) {\displaystyle \left|\textstyle \sum \limits _{n=M+1}^{M+N}\chi (n)\right|=O\left({\sqrt {q}}\log q\right)}
ここで
χ ( n ) = ( n q ) {\displaystyle \chi (n)=\left({\frac {n}{q}}\right)}
とすると、長さ N の任意の区間における q を法とする平方剰余の数が以下のように表せる。
1 2 N + O ( q log  q ) {\displaystyle {\frac {1}{2}}N+O({\sqrt {q}}\log q)}
| ∑ n = M + 1 M + N χ ( n ) | = O ( q log  log  q ) {\displaystyle \left|\textstyle \sum \limits _{n=M+1}^{M+N}\chi (n)\right|=O\left({\sqrt {q}}\log \log q\right)}
この結果から本質的に改良されたわけではないが、シューアは1918年に
max N | ∑ n = 1 N ( n q ) | > 1 2 π q {\displaystyle \max _{N}\left|\textstyle \sum \limits _{n=1}^{N}\left({\dfrac {n}{q}}\right)\right|>{\dfrac {1}{2\pi }}{\sqrt {q}}}
を示し、ペイリー(英語版)(Paley)は1932年に
max N | ∑ n = 1 N ( d n ) | > 1 7 d log  log  d {\displaystyle \max _{N}\left|\textstyle \sum \limits _{n=1}^{N}\left({\dfrac {d}{n}}\right)\right|>{\dfrac {1}{7}}{\sqrt {d}}\log \log d}
を満たす d > 0 が無限に存在することを示した。
法が p の場合、
pa は 剰余である(k ≥ n の場合) 非剰余である(k < n が奇数の場合) 剰余である(k < n が偶数で a が剰余の場合) 非剰余である(k < n が偶数で a が非剰余の場合)
ただし、2のべき乗と奇素数のべき乗では、ルールが異なることに注意せよ。
奇素数のべき乗 n = p を法として、p と互いに素な剰余と非剰余の積は、p を法としたときと同じルールに従う。p は非剰余であり、一般に全ての剰余と非剰余に対して、その積の中の p のべき乗が n 以上ならば積がゼロとなることを除けば、同じルールに従う。
例えば 8 を法とすると、非剰余 3 と 5 の積は非剰余 7 であり、3, 5, 7 を互いに入れ替えた場合も同様である。実際、非剰余と1の乗法群はクラインの四元群を成す。