平方剰余
2 を法とすると、すべての整数が平方剰余となる。
オイラーの規準 (Euler's criterion) によると、奇素数 p を法とすると、p + 1/2 個の剰余(0を含む)と p − 1/2 個の非剰余が存在する。この場合、慣例として0を特殊なケースと見なし、体 Z/pZ の非ゼロ要素の乗法群(英語版)内に議論を限定する。(言い換えると、p を法とするゼロを除くすべての合同類は乗法逆元を持つ。これは合成数の法には当てはまらない。)
この規約に従うと、剰余の乗法逆元は剰余、非剰余の乗法逆元は非剰余であり、また、奇数の素数を法とすると剰余と非剰余が同数存在する。
素数を法とすると、2つの非剰余の積は剰余であり、非剰余と(非ゼロ)剰余の積は非剰余である。
平方剰余の相互法則への最初の補足は、p ≡ 1 (mod 4) ならば −1 は p を法とする平方剰余であり、p ≡ 3 (mod 4) ならば −1 は p を法とする非剰余である。これは以下のことを意味する。
p ≡ 1 (mod 4) ならば p を法とする負の剰余(絶対値が同じで符号を反転したもの)は剰余であり、負の非剰余は非剰余である。
p ≡ 3 (mod 4) ならば p を法とする負の剰余は非剰余であり、負の非剰余は剰余である。
n の完全な素因数分解が不明な場合、「 ( a n ) = 1 {\displaystyle \left({\tfrac {a}{n}}\right)=1} かつ n ≢ 2 ( mod 4 ) {\displaystyle n\not \equiv 2{\pmod {4}}} 」または「n ≡ 2 (mod 4) かつ ( a n / 2 ) = 1 {\displaystyle \left({\tfrac {a}{n/2}}\right)=1} 」ならば、問題は n の素因数分解と等価であることが分かっている(つまり、どちらかの問題の効率的に解ければ、もう一方を効率的に解くことができる)。
上記の議論は、n の素因数を知ることでどのくらい根を効率的に見つけることができるかを示している。合成数を法とする平方根を見つけるための効率的なアルゴリズムがあったとしよう。平方合同(英語版) (congruence of squares) の記事では、x ≡ y (mod n) である二つの数 x, y の求め方について説明しており、x ≠ ±y であれば n は十分効率的に素因数分解される。ここで乱数を生成し、n を法として乱数を二乗し、効率的な平方根アルゴリズムで根を見つける。これを、最初に二乗した値(または n を法とする負の数)と等しくない数を返すまで繰り返した後に、平方合同で説明したアルゴリズムを用いる。素因数分解アルゴリズムの効率性は、この根探索器の特性そのものに依存するが(たとえば、すべての根を返すか?最小の根だけを返すか?ランダムな根を返すか?)、これは効率的である。
n を法として a が平方剰余であるか非剰余であるか( a R n または a N n と表される)の判定は、ルジャンドル記号を計算することで、素数 n に対して効率的に行うことができる。
すべての奇数の平方数は ≡ 1 (mod 8) であり、それ故に ≡ 1 (mod 4) でもある。a が奇数で、m = 8, 16 またはそれよりも大きな 2 のべき乗の場合、a は m を法とする剰余であり、これは a ≡ 1 (mod 8) と同値である。
たとえば、mod 32 の奇数の平方数は
1 ≡ 15 ≡ 1
3 ≡ 13 ≡ 9
5 ≡ 11 ≡ 25
7 ≡ 9 ≡ 49 ≡ 17
そして偶数のものは
0 ≡ 8 ≡ 16 ≡ 0
2 ≡ 6 ≡ 10 ≡ 14 ≡ 4
4 ≡ 12 ≡ 16.
したがって、0 以外の数が 8, 16, ... を法として剰余となるのは、その数が 4(8n + 1) の形で表現できる場合でかつその場合に限る。
奇素数 p と互いに素な数 a が、p の任意のべき乗を法として剰余であるのは、p を法として剰余である場合でかつその場合に限る。