平方剰余
オイラーの規準は、p が素数であるルジャンドル記号 (a|p) の公式である。p が合成数の場合、公式は (a|p) を正しく計算できる場合もできない場合もある。与えられた数 n が素数であるか合成数であるかについてのソロベイ-シュトラッセン素数判定法は、ランダムな a を選び、ユークリッドの互除法の修正とオイラーの基準を使用して (a|n) を計算する。結果が一致しない場合、n は合成数である。一致する場合、n は合成数または素数である。合成数 n に対して、2, 3, ..., n − 1 の範囲中、少なくとも半分の a では「n は合成数」と判定されるが、素数 n に対しては何も出力しない。多くの異なる a を試しても n が合成数と判定されなければ、n は確率的素数と呼ばれる。
ミラー–ラビン素数判定法も同じ原理に基づく。この判定法は決定論的なバージョンがあるが、これが正しく判定できるかの証明は一般化されたリーマン仮説 (GRH) 依存する。この判定法の出力は、「n は完全に合成数」または「n は素数かGRHは偽である」のいずれかである。合成数 n に対して出力が後者の場合、GRHは偽になり、数学の多くの分野に影響を及ぼす可能性がある。
n = 1, 2, 3, ... に対する n を法とする平方剰余の数のリストは、以下の通りである。
1, 2, 2, 2, 3, 4, 4, 3, 4, 6, 6, 4, 7, 8, 6, 4, 9, 8, 10, 6, 8, 12, 12, 6, 11, 14, 11, 8, 15, 12, 16, 7, 12, 18, 12, 8, 19, 20, 14, 9, 21, 16, 22, 12, 12, 24, 24, 8, 22, 22, ...(オンライン整数列大辞典の数列 A000224)
n を法とする平方数の数を数える式は、スタングル (Stangl) によって与えられる。
こうした規則性の研究は、二進二次形式の類数の公式に関する(1830年代の)ディリクレの研究に由来する。q を素数、s を複素変数とし、ディリクレのL関数を次のように定義する。
L ( s ) = ∑ n = 1 ∞ ( n q ) n − s {\displaystyle L(s)=\textstyle \sum \limits _{n=1}^{\infty }\left({\dfrac {n}{q}}\right)n^{-s}}
ディリクレは、q ≡ 3 (mod 3) のとき、
L ( 1 ) = − π q ∑ n = 1 q − 1 n q ( n q ) > 0 {\displaystyle L(1)=-{\frac {\pi }{\sqrt {q}}}\textstyle \sum \limits _{n=1}^{q-1}{\dfrac {n}{q}}\left({\dfrac {n}{q}}\right)>0}
となることを示した。したがってこの場合(素数 q ≡ 3 (mod 4))、平方剰余の和から 1, 2, ..., q − 1 の範囲における非剰余の和を引いたものは負の数になる。
たとえば、11を法とすると
1, 2, 3, 4, 5, 6, 7, 8, 9, 10(太字は剰余)
1 + 4 + 9 + 5 + = 22, 2 + 6 + 7 + 8 + 10 = 33、そして差は −11 である。