平方剰余
平方剰余は n を法としてランダムなパターンが見られ、これは音響や暗号などの応用で利用されているが、一方でその分布は規則性も示す。
算術級数の素数に関するディリクレの定理、平方剰余の定理、および中国の剰余定理 (CRT) を使うと、任意の M > 0 に対して、1, 2, ..., M が全て素数 p を法として剰余であることが簡単に分かる。
例えば、p ≡ 1 (mod 8), (mod 12), (mod 5), (mod 28) ならば、平方剰余の定理から 2, 3, 5, 7 は素数 p を法として剰余であり、故に1〜10のすべての数字が剰余になる。CRTはこれが p ≡1 (mod 840) の場合と同じであり、ディリクレの定理はこの形式の素数の無限に存在すると主張する。これを満たす素数 p は 2521 が最小であり、実際に 1 ≡ 1, 1046 ≡ 2, 123 ≡ 3, 2 ≡ 4, 643 ≡ 5, 87 ≡ 6, 668 ≡ 7, 429 ≡ 8, 3 ≡ 9, 529 ≡ 10 (mod 2521) となる。
この場合の基本的な事実は
a が n を法として剰余である場合、a はすべての素数のべき乗 p が n を割り切る p を法として剰余である。
a が n を法として非剰余である場合、a は少なくとも1つの素数のべき乗 p が n を割り切る p を法として非剰余である。
合成数を法として、2つの剰余の積は剰余である。剰余と非剰余の積は、剰余、非剰余、またはゼロの場合がある。
たとえば、mod 6 の表から
1, 2, 3, 4, 5(太字は剰余)
剰余 3 と非剰余 5 の積は剰余 3 であるが、剰余 4と非剰余 2 の積は非剰余 2 である。
また、2つの非剰余の積は、剰余、非剰余、またはゼロのいずれかになる。
たとえば、mod 15 の表から
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14(太字は剰余)
非剰余2と非剰余8の積は剰余1だが、非剰余2と非剰余7の積は非剰余14である。
ガウスは、R と N を使用して、それぞれ剰余性と非剰余性を表現した。
たとえば、2 R 7 と 5 N 7、また 1 R 8 と 3 N 8
この表記はコンパクトで、いくつかの目的には便利であるが、より有用な表記は二次指標とも呼ばれるルジャンドル記号であり、すべての整数 a および正の奇素数 p に対して次のように定義される。
( a p ) = { 0 if p divides a + 1 if a R  p and p does not divide a − 1 if a N  p and p does not divide a {\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}\;\;\,0&{\text{ if }}p{\text{ divides }}a\\+1&{\text{ if }}a\operatorname {R} p{\text{ and }}p{\text{ does not divide }}a\\-1&{\text{ if }}a\operatorname {N} p{\text{ and }}p{\text{ does not divide }}a\end{cases}}}
数値 ≡ 0 (mod p) を特別に扱う理由は2つある。1つは、これまで見てきたように、多くの公式や定理を簡単に説明できるためである。もう1つは、二次指標が乗算の下で、pを法とする非ゼロ合同類の乗法群(英語版)から複素数への準同型であるためである。
つまり、数値 a と法 n が与えられたときに、以下のタスクがどれほど難しいか、ということである。
x ≡ a (mod n) の解 x が存在するかどうかの判定
存在すると仮定して、その具体的な計算
ここでは、法が素数と合成数の場合で重要な違いが明らかになる。素数 p を法として、平方剰余 a は 1 + (a|p) 個の根を持つ(つまり、a N p の場合は根なし、a ≡ 0 (mod p) の場合は1個、a R p で (a, p) = 1 の場合は2個。)
一般に、もし法が合成数 n であれば、n を異なる素数のべき乗の積として表現したときに、その最初のものを法として根の数が n1 個、次のものを法として根の数が n2 個...と続けていくと、n を法として n1n2... 個の根が存在する。
ペイリーグラフ(英語版) (Paley graph) は、各素数 p ≡ 1 (mod 4) がカンファレンスグラフ(英語版)(conference graph)の無限族を形成する稠密な無向グラフであり、これによって対称カンファレンス行列(英語版) (conference matrix) の無限族が導かれる。
ペイリー双グラフ (Paley digraph) はペイリーグラフを有向グラフとしたもので、素数は p ≡ 3 (mod 4) を用い、反対称カンファレンス行列が導かれる。
これらのグラフの作成には、平方剰余が用いられる。