ルジャンドル記号
ルジャンドル記号には平方剰余の法則とともに効率的に計算するために使うことのできる便利な性質がいくつかある。
p ≡ 3 ( mod 4 ) {\displaystyle p\equiv 3({\text{mod }}4)} の場合、 p + 1 4 + p + 1 4 = ( p − 1 ) + 2 2 {\displaystyle {\frac {p+1}{4}}+{\frac {p+1}{4}}={\frac {(p-1)+2}{2}}} という事実は a = x ( p + 1 ) / 4 {\displaystyle a=x^{(p+1)/4}} が平方剰余 x {\displaystyle x} の平方根であることを提供する。
a ≡ b (mod p)の場合、ルジャンドル記号は1番目の(上の)引数において周期的である。 ( a p ) = ( b p ) . {\displaystyle \left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right).}
ルジャンドル記号は、上の引数の完全乗法的関数(en:completely multiplicative function)である。 ( a b p ) = ( a p ) ( b p ) . {\displaystyle \left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right).
ルジャンドルによる最初の定義は、次のように式を明示したものだった。
( a p ) ≡ a p − 1 2 ( mod p ) and ( a p ) ∈ { − 1 , 0 , 1 } . {\displaystyle \left({\frac {a}{p}}\right)\equiv a^{\frac {p-1}{2}}{\pmod {p}}\quad {\text{ and }}\quad \left({\frac {a}{p}}\right)\in \{-1,0,1\}.}
先に発見されルジャンドルにも知られていたオイラーの規準によると、これら2つの定義は同等である。よって、ルジャンルドルが貢献したのは、mod pでのaの平方剰余性を記録する便利な表記法を導入したことにあった。比較の目的で、ガウスはaがpを法とする剰余であるか非剰余であるかに応じて、aRpとaNpという表記を使用した。印刷の都合上、ルジャンドル記号は(a | p) または (a/p) と表記されることがある。a が0, 1, 2,...であるときの数列 (a | p) は周期pで周期的であり、ルジャンドル数列と呼ばれることがある。{0,1,−1}という値は{1,0,1}または{0,1,0}であることがある。次の表の各行は、説明したように周期性を示していることが分かる。