数論において、 を法として平方数と合同である整数 を、 を法とする平方剰余（へいほうじょうよ、）と呼ぶ。つまり、 が平方剰余であるとは、 に対し以下の条件を満たす整数 が存在することを意味する：
平方剰余でない数を平方非剰余（へいほうひじょうよ、）と呼ぶ。
元々、合同算術という数論の一分野からの抽象的な数学的概念であった平方剰余は、現在様々な分野で応用されており、その応用先は音響工学から暗号化、大きな数の素因数分解にまで至る。
歴史、規約、および基本的な事実 フェルマー、オイラー、ラグランジュ、ルジャンドルをはじめとする17〜18世紀の数論者たちはそれぞれ平方剰余についての定理を確立しLemmemeyer, Ch.1、予想を打ち立てたLemmermeyer, pp.6-8, p.16 ffが、最初の体系的な扱いはガウスのDisquisitiones ArithmeticaeのIV節 (1801) である。Article 95では、「平方剰余」と「平方非剰余」という用語を導入し、文脈から明らかであれば、形容詞「平方」を削除できると述べている。
与えられた に対して、 を法とする平方剰余のリストは単に を二乗するだけで得られる。 であるので、 を法とする平方数のリストは に対して対称であり、リストアップは まで続ければ十分である。これは下の表で確認できる。
つまり、 を法とする平方剰余の数は、（ が偶数）または （ が奇数）を超えることはないGauss, DA, art.94。
2つの剰余の積は常に剰余となる。
素数の法 2 を法とすると、すべての整数が平方剰余となる。
オイラーの規準 (Euler's criterion) によると、奇素数 p を法とすると、 個の剰余（0を含む）と 個の非剰余が存在する。この場合、慣例として0を特殊なケースと見なし、体 Z/pZ の内に議論を限定する。（言い換えると、p を法とするゼロを除くすべての合同類は乗法逆元を持つ。これは合成数の法には当てはまらない。）Gauss, DA, art.96
この規約に従うと、剰余の乗法逆元は剰余、非剰余の乗法逆元は非剰余でありGauss, DA, art.98、また、奇数の素数を法とすると剰余と非剰余が同数存在するGauss, DA, art.96。
素数を法とすると、2つの非剰余の積は剰余であり、非剰余と（非ゼロ）剰余の積は非剰余であるGauss, DA, art.98。
平方剰余の相互法則への最初の補足Gauss, DA, art 111は、p ≡ 1 (mod 4) ならば −1 は p を法とする平方剰余であり、p ≡ 3 (mod 4) ならば −1 は p を法とする非剰余である。これは以下のことを意味する。
p ≡ 1 (mod 4) ならば p を法とする負の剰余（絶対値が同じで符号を反転したもの）は剰余であり、負の非剰余は非剰余である。
p ≡ 3 (mod 4) ならば p を法とする負の剰余は非剰余であり、負の非剰余は剰余である。
素数のべき乗の法 すべての奇数の平方数は ≡ 1 (mod 8) であり、それ故に ≡ 1 (mod 4) でもある。a が奇数で、m = 8, 16 またはそれよりも大きな 2 のべき乗の場合、a は m を法とする剰余であり、これは a ≡ 1 (mod 8) と同値であるGauss, DA, art.103。 たとえば、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 を法として剰余である場合でかつその場合に限るGauss, DA, art.101。
法が p の場合、 pa は 剰余である（k ≥ n の場合） 非剰余である（k < n が奇数の場合） 剰余である（k < n が偶数で a が剰余の場合） 非剰余である（k < n が偶数で a が非剰余の場合）Gauss, DA, art.102 ただし、2のべき乗と奇素数のべき乗では、ルールが異なることに注意せよ。
奇素数のべき乗 n = p を法として、p と互いに素な剰余と非剰余の積は、p を法としたときと同じルールに従う。p は非剰余であり、一般に全ての剰余と非剰余に対して、その積の中の p のべき乗が n 以上ならば積がゼロとなることを除けば、同じルールに従う。
例えば 8 を法とすると、非剰余 3 と 5 の積は非剰余 7 であり、3, 5, 7 を互いに入れ替えた場合も同様である。実際、非剰余と1の乗法群はクラインの四元群を成す。
素数のべき乗以外の合成数の法 この場合の基本的な事実は 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である。 この現象は、抽象代数の言葉でよく説明できる。法と互いに素な合同類は、環 Z/nZ の単元群と呼ばれる乗法に関する群であり、平方数はその部分群となる。異なる非剰余は異なる剰余類に属している可能性があり、それらの積がどの類に属するかを予測する単純なルールは存在しない。素数を法として、平方数の部分群と単一の剰余類が存在するのみである。
たとえば15を法とする非剰余3と5の積、または非剰余5と剰余9の積、または2つの剰余9と10の積がすべてゼロであるという事実は、完全な環 Z/nZ の中にあることから生じ、この環は合成数 n の 零因子を持つ。
このため、一部の著者e.g., は、平方剰余 a は平方数であるだけでなく、法 n と互いに素でなければならないという定義を追加している。（a が n と互いに素となるのは、a が n と互いに素である場合でかつその場合に限る。）
これで話は片付くが、本記事では剰余が法と互いに素であるという定義は用いない。
記法 ガウスGauss, DA, art.131は、 と を使用して、それぞれ剰余性と非剰余性を表現した。 たとえば、 と 、また と この表記はコンパクトで、いくつかの目的には便利であるがe.g. Hardy and Wright use itGauss, DA, art 230 ff.、より有用な表記は二次指標とも呼ばれるルジャンドル記号であり、すべての整数 a および正の奇素数 に対して次のように定義される。
数値 ≡ 0 (mod ) を特別に扱う理由は2つある。1つは、これまで見てきたように、多くの公式や定理を簡単に説明できるためである。もう1つは、二次指標が乗算の下で、から複素数への準同型であるためである。 とすると、その定義域をすべての整数の乗法半群に拡張することができるThis extension of the domain is necessary for defining L functions.。
ガウスの表記法よりも優れている点の1つは、ルジャンドル記号が数式として使用できる関数であることであるSee Legendre symbol#Properties of the Legendre symbol for examples。また、3次、4次、および高次の剰余に簡単に一般化できるLemmermeyer, pp.111-end。
ルジャンドル記号を が合成数である場合に一般化したものとしてヤコビ記号があるが、その特性はそれほど単純ではない。 が合成数で、ヤコビ記号が ならば であり、 ならば である。しかし、 ならば、 と のいずれなのかは判断できない。例えば、 と に対して、 と である。 が素数の場合、ヤコビ記号とルジャンドル記号は同一のものとなる。
平方剰余の分布 平方剰余は 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) となる。
ディリクレの公式 こうした規則性の研究は、二進二次形式の類数の公式に関する（1830年代の）ディリクレの研究に由来する. These are classical results.。q を素数、s を複素変数とし、ディリクレのL関数を次のように定義する。
ディリクレは、q ≡ 3 (mod 3) のとき、
となることを示した。したがってこの場合（素数 q ≡ 3 (mod 4)）、平方剰余の和から 1, 2, …, q − 1 の範囲における非剰余の和を引いたものは負の数になる。 たとえば、11を法とすると 1, 2, 3, 4, 5, 6, 7, 8, 9, 10（太字は剰余） 1 + 4 + 9 + 5 + = 22, 2 + 6 + 7 + 8 + 10 = 33、そして差は −11 である。 実際、q > 3の場合、差は常に q の奇数倍になる, (conjectured by Jacobi, proved by Dirichlet)。対照的に、平方剰余の和から 1, 2, …, q − 1 の範囲における非剰余の和を引いたものはゼロであり、両方の和が と等しいことを意味する。
ディリクレは素数 q ≡ 3 (mod 4) の場合も証明した。
これは、1, 2, …, の範囲で、平方剰余が非剰余よりも多いことを意味する。 たとえば11を法とすると、6未満の剰余は4つ (1, 3, 4, 5) だが、非剰余は1つだけ (2) である。 これらの2つの定理に関する興味深い点は、これまでに知られているすべての証明が解析に基づくということである。どちらの定理についても、単純な証明あるいは直接の証明は発表されていない。
平方剰余の相互法則 p と q が奇素数の場合、 「『p は q を法とする平方剰余』と『q は p を法とする平方剰余』が同値であること」は「p と q の少なくとも1つが4を法として1に合同である」と同値である。 つまり、
である。 はルジャンドル記号である。
したがって、a と a を割り切らない奇素数 p に対して、以下のようになる。 aa が p を法として平方剰余になる同値条件aa が p を法として平方剰余になる同値条件1（すべての素数p ） −1p ≡1 (mod 4)2p ≡1, 7 (mod 8) −2p ≡1, 3 (mod 8)3p ≡1, 11 (mod 12) −3p ≡1 (mod 3)4（すべての素数p） −4p ≡1 (mod 4)5p ≡1, 4 (mod 5) −5p ≡1, 3, 7, 9 (mod 20)6p ≡1, 5, 19, 23 (mod 24) −6p ≡1, 5, 7, 11 (mod 24)7p ≡1, 3, 9, 19, 25, 27 (mod 28) −7p ≡1, 2, 4 (mod 7)8p ≡1, 7 (mod 8) −8p ≡1, 3 (mod 8)9（すべての素数p ） −9p ≡1 (mod 4)10p ≡1, 3, 9, 13, 27, 31, 37, 39, 43 (mod 40) −10p ≡1, 7, 9, 11, 13, 19, 23, 37 (mod 40)11p ≡1, 5, 7, 9, 19, 26, 35, 37, 39, 43 (mod 44) −11p ≡1, 3, 4, 5, 9 (mod 11)12p ≡1, 11 (mod 12) −12p ≡1 (mod 3)
剰余と非剰余のペア 素数 p を法として、 かつ 、または と 等となるペア の数はほぼ同じである。より正確にはLemmermeyer, p.29 ex.1.22; cf pp.26-27, Ch.10Crandall & Pomerance, ex 2.38, pp.106-108、p を奇素数として、i, j = 0, 1 によって以下の集合を定義し
以下のように α を定義する。
つまり、以下のようになる。 α は剰余に続く剰余の数 α は非剰余に続く剰余の数 α は剰余に続く非剰余の数 α は非剰余に続く非剰余の数 すると、p ≡ 1 (mod4) の場合、
であり、p ≡ 3 (mod4) の場合、
である。 例：（太字は剰余） mod 17 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 A = {1,8,15}, A = {2,4,9,13}, A = {3,7,12,14}, A = {5,6,10,11}.
mod 19 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 A = {4、5、6、16}, A = {1,7,9,11,17}, A = {3,8,10,15}, A = {2,12,13,14}. ガウス (1828)Gauss, Theorie der biquadratischen Reste, Erste Abhandlung (pp.511-533 of the Untersuchungen über hohere Arithmetik)は、p ≡ 1 (mod 4) ならば x ≡ 2 (mod p) という命題が p = a + 64 b と同値であることを証明し、この種の数え上げを導入した。
ポリア＝ヴィノグラドフの不等式 (Pólya-;Vinogradov inequality) 連続値 a に対する の値はコイントスのような確率変数で擬似的に表現できるCrandall & Pomerance, ex 2.38, pp.106-108 discuss the similarities and differences. For example, tossing n coins, it is possible (though unlikely) to get n/2 heads followed by that many tails. V-P inequality rules that out for residues.。具体的には、ポリアと (Vinogradov), (proof of P-V, (in fact big-O can be replaced by 2); journal references for Paley, Montgomery, and Schur)が、1918年に（独立して）q をとする非主(non-principal)ディリクレ指標 χ(n) と任意の整数 M, N に対して、ランダウの記号を用いて以下のように表現できることを証明した。
ここで
とすると、長さ N の任意の区間における q を法とする平方剰余の数が以下のように表せる。
以下の式の証明は容易Planet Math: Proof of Pólya-Vinogradov Inequality in external links. The proof is a page long and only requires elementary facts about Gaussian sumsである。
実際Pomerance & Crandall, ex 2.38 pp.106-108. result from T. Cochrane, "On a trigonometric inequality of Vinogradov", J. Number Theory, 27:9-16, 1987、
となる。
モンゴメリー(Montgomery)と(Vaughan)は1977年にこれを改良し、一般化されたリーマン予想が真である場合、以下の式が成り立つことを示した。
この結果から本質的に改良されたわけではないが、シューアは1918年に
を示し、(Paley)は1932年に
を満たす d > 0 が無限に存在することを示した。
最小二次非剰余 p を法とする最小平方剰余は明らかに1である。最小二次非剰余の大きさ n(p) の問題は難しいが、常に素数である。上記ポリア＝ヴィノグラードフの不等式は を与える。無条件での最良推定値は、任意の に対して n(p) ≪ p というものであり、 (character sum) に関するバージェス (Burgess) の推定から得られた。一般化されたリーマン予想の仮定下では、アンケニー (Ankeny) が n(p) ≪ (log p) を得た。リニック (Linnik) は、n(p) > X となる X より小さい p の数は、ε に依存する定数によって制限されることを示した。
奇素数 p を法とする最小二次非剰余は次の通り。 2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, 3, 2, 5, 2, 2, 2, 2, 7, 5, 3, 2, 3, 5, 23, 2, 2, 3, 3, 2, 3, 2, 2, 3, 2, 2, 5, 2, 2, 2, 7, 5, 2, 3, 2, 3, 2, 2, 37, 7, 2, 3, 5, 2, 3, 2, 3, 2, 2, 2, 11, 5, 2, 2, 5, 2, 2, 3, 7, 3, 2, 2, …
二次超過 p を奇素数とする。二次超過 (Quadratic excess) E(p) は、範囲 (0, ) の平方剰余の数から 範囲 (, p) の平方剰余の数を引いたものである（）。p ≡ 1 mod 4 となる p では、−1 が平方剰余であり、剰余は に対して対称であるので過剰はゼロである。p ≡ 3 mod 4 となる p では、超過 E は常に正である。
平方根を見つけることの複雑さ つまり、数値 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 を異なる素数のべき乗の積として表現したときに、その最初のものを法として根の数が n 個、次のものを法として根の数が n 個…と続けていくと、n を法として nn… 個の根が存在する。
素数のべき乗を法とする解を組み合わせて n を法とする解を作る理論的な方法は、中国の剰余定理と呼ばれ、効率的なアルゴリズムで実装できる; it requires O(log m) steps where m is the number of primes dividing 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 が素数である場合、ルジャンドル記号 はユークリッドの互除法のバリエーション; computing requires O(log a log n) stepsまたはオイラーの規準を使用して、すばやく計算できる。-1の場合、解は存在しない。
次に と仮定すると、n ≡ 3 (mod 4) の場合 ラグランジュは、解が以下の式によって与えられることを発見した。
そしてルジャンドルは、n ≡ 5 (mod 8) の場合の同様の解を発見したLemmermeyer, p.29。
しかし、素数 n ≡ 1 (mod 8) に対しては、既知の公式が存在しない。トネリ; the algorithm requires O(logn) steps.（1891年）と; the algorithm requires O(log n) steps and is also nondetermisitic.は、それぞれすべての素数の法に使える効率的なアルゴリズムを発見した。どちらのアルゴリズムも n を法とする平方非剰余を見つける必要があり、そのための効率的な既知の決定論的アルゴリズムは存在しない。しかし、1 から n の間の数の半分は非剰余であるため、非剰余が見つかるまで、ランダムに数 x を選んでルジャンドル記号 を計算すると、すぐに非剰余が求まる。このアルゴリズムをわずかに変形したものがトネリ・シャンクスのアルゴリズムである。
法 n が素数のべき乗 n = p である場合、解は p を法として見つかるので、ヘンゼルの補題またはガウスのアルゴリズムを使用して n を法とする解に「持ち上げて」得られるGauss, DA, art.101。
合成数の法 法 n が素数のべき乗に素因数分解される場合、解は上記の通りである。
で(Kronecker symbol)が であれば、解は存在しない。n ≡ 2 (mod 4) で である場合も、解は存在しない。「 かつ 」または「 n ≡ 2 (mod 4) かつ 」 ならば、解が存在する場合としない場合がある。
n の完全な素因数分解が不明な場合、「 かつ 」または「n ≡ 2 (mod 4) かつ 」ならば、問題は n の素因数分解と等価であることが分かっている（つまり、どちらかの問題の効率的に解ければ、もう一方を効率的に解くことができる）。
上記の議論は、n の素因数を知ることでどのくらい根を効率的に見つけることができるかを示している。合成数を法とする平方根を見つけるための効率的なアルゴリズムがあったとしよう。 (congruence of squares) の記事では、 である二つの数 x, y の求め方について説明しており、 であれば n は十分効率的に素因数分解される。ここで乱数を生成し、n を法として乱数を二乗し、効率的な平方根アルゴリズムで根を見つける。これを、最初に二乗した値（または n を法とする負の数）と等しくない数を返すまで繰り返した後に、平方合同で説明したアルゴリズムを用いる。素因数分解アルゴリズムの効率性は、この根探索器の特性そのものに依存するが（たとえば、すべての根を返すか？最小の根だけを返すか？ランダムな根を返すか？）、これは効率的であるCrandall & Pomerance, ex.6.5 & 6.6, p.273。
n を法として a が平方剰余であるか非剰余であるか（ または と表される）の判定は、ルジャンドル記号を計算することで、素数 n に対して効率的に行うことができる。ただし、n が合成数の場合は (quadratic residuosity problem) となり、これは素因数分解ほどかは分かっていないが、かなり難しいと考えられている。
一方、ある上限値 c より小さい x の解があるかどうかを判定する場合、この問題はNP完全である。ただし、これは c をパラメータとする問題である。
一般に、合成数 n を法として a が平方剰余であるかどうかを判定するには、次の定理を使用できる：
とし、とする。 が解けることと以下の条件は同値である： n のすべての奇数の約数 p について、ルジャンドル記号表現が である。 n が4割り切れるが8で割り切れない場合は 。または n が8で割り切れる場合は 。 注：この定理を使うに当たって本質的には n の素因数分解が既知である必要がある。また、 の場合、合同関係は に還元することができるが、（m が平方数でない限り）これは平方剰余の問題の範疇を超える。
平方剰余の数 n = 1, 2, 3, … に対する n を法とする平方剰余の数のリストは、以下の通りである。 1, 2, 2, 2, 3, 4, 4, 3, 4, 6, 6, 4, 7, 8, 6, 4, 9, 8, 10, 6, 8, 12, 12, 6, 11, 14, 11, 8, 15, 12, 16, 7, 12, 18, 12, 8, 19, 20, 14, 9, 21, 16, 22, 12, 12, 24, 24, 8, 22, 22, …（） n を法とする平方数の数を数える式は、スタングル (Stangl) によって与えられる。
平方剰余の応用 音響 は、原始根や平方剰余などの数論的概念に基づいている。
グラフ理論 (Paley graph) は、各素数 p ≡ 1 (mod 4) が(conference graph)の無限族を形成する稠密な無向グラフであり、これによって対称 (conference matrix) の無限族が導かれる。
ペイリー双グラフ (Paley digraph) はペイリーグラフを有向グラフとしたもので、素数は p ≡ 3 (mod 4) を用い、反対称カンファレンス行列が導かれる。
これらのグラフの作成には、平方剰余が用いられる。
暗号 大きな合成数 n を法とする数値の平方根を見つけることは、素因数分解（これはと広く信じられている）に相当するという事実は、Rabin暗号や紛失転送プロトコルなどの暗号化スキームの構築に使用されている。は、の基礎を成す。また、コックスによるIDベース暗号も平方剰余に基づいている。
離散対数も暗号化で用いられる同様の問題である。
素数判定