オイラーの規準
実際には、ユークリッドの互除法の拡張した変形を使用してヤコビ記号 ( a n ) {\displaystyle \left({\frac {a}{n}}\right)} を計算する方が効率的である。 n {\displaystyle n} が奇素数である場合、これはルジャンドル記号と等しく、 a {\displaystyle a} が n {\displaystyle n} を法とする平方剰余であるかどうかを決定する。
一方で、ヤコビ記号と a n − 1 2 {\displaystyle a^{\frac {n-1}{2}}} の同等性は全ての奇素数に当てはまるが、必ずしも合成数には当てはまらないため、両方を計算してそれらを比較することで素数判定、特にソロベイ–シュトラッセン素数判定法として使用することができる。所与の a {\displaystyle a} に対して合同が成り立つ合成数は、底 a {\displaystyle a} に対するオイラー・ヤコビ擬素数(en:Euler–Jacobi pseudoprime)と呼ばれる。
この証明は素数を法とする剰余のクラスが体であることを使用する。詳細は素体の記事(en:Characteristic (algebra)#Case of fields)参照。
法が素数であるため、ラグランジュの定理(英語版)が適用される。次数 k の多項式は最大で k 個の根しか持つことができない。特に、x ≡ a (mod p) は各 a に対して最大2つの解を持つ。このことは0の他にpを法とする少なくともp − 1/2個の異なる平方剰余があることを即座に意味する。x の p − 1 個の可能な値の各々は、同じ剰余を与えるために互いに付随することしかできない。
実際に、 ( p − x ) 2 ≡ x 2 ( mod p ) {\displaystyle (p-x)^{2}\equiv x^{2}{\pmod {p}}} である。これは ( p − x ) 2 ≡ p 2 − 2 x p + x 2 ≡ x 2 ( mod p ) {\displaystyle (p-x)^{2}\equiv p^{2}-{2}{x}{p}+x^{2}\equiv x^{2}{\pmod {p}}} であるからである。 よって、 p − 1 2 {\displaystyle {\tfrac {p-1}{2}}} 個の別個の平方剰余は 1 2 , 2 2 , . . . , ( p − 1 2 ) 2 ( mod p ) {\displaystyle 1^{2},2^{2},...,({\tfrac {p-1}{2}})^{2}{\pmod {p}}} である。
a は p と互いに素であるため、フェルマーの小定理により