平方剰余
素数のべき乗を法とする解を組み合わせて n を法とする解を作る理論的な方法は、中国の剰余定理と呼ばれ、効率的なアルゴリズムで実装できる。
例えば:
x ≡ 6 (mod 15) を解く。 x ≡ 6 (mod 3) は1つの解 x = 0, x ≡ 6 (mod 5) が2つの解 x = 1, 4 を持つ。 したがって、15を法として2つの解 x = 6, 9 が存在する。
x ≡ 4 (mod 15) を解く。 x ≡ 4 (mod 3) は2つの解 x = 1, 2, x ≡ 4 (mod 5) が2つの解 x = 2, 3 を持つ。 したがって、15を法として4つの解 x = 2, 7, 8, 13 が存在する。
x ≡ 7 (mod 15) を解く。 x ≡ 7 (mod 3) は2つの解 x = 1, 2 を持ち、x ≡ 7 (mod 5) は解が存在しない。 したがって、15を法として解が存在しない。
( n p p ) = 0 {\displaystyle ({\tfrac {np}{p}})=0} とすると、その定義域をすべての整数の乗法半群に拡張することができる。
ガウスの表記法よりも優れている点の1つは、ルジャンドル記号が数式として使用できる関数であることである。また、3次、4次、および高次の剰余に簡単に一般化できる。
ルジャンドル記号を p が合成数である場合に一般化したものとしてヤコビ記号があるが、その特性はそれほど単純ではない。m が合成数で、ヤコビ記号が ( a m ) = − 1 {\displaystyle ({\tfrac {a}{m}})=-1} ならば a N m であり、a R m ならば ( a m ) = 1 {\displaystyle ({\tfrac {a}{m}})=1} である。しかし、 ( a m ) = 1 {\displaystyle ({\tfrac {a}{m}})=1} ならば、a R m と a N m のいずれなのかは判断できない。例えば、 ( 2 15 ) = 1 {\displaystyle ({\tfrac {2}{15}})=1} と ( 4 15 ) = 1 {\displaystyle ({\tfrac {4}{15}})=1} に対して、2 N 15 と 4 R 15 である。m が素数の場合、ヤコビ記号とルジャンドル記号は同一のものとなる。