平方剰余のソースを表示

[[数論]]において、{{mvar|p}} を[[剰余演算|法]]として[[平方数]]と[[合同関係|合同]]である[[整数]] {{mvar|q}} を、{{mvar|p}} を法とする'''平方剰余'''（へいほうじょうよ、{{lang-en-short|quadratic residue}}）と呼ぶ。つまり、{{mvar|q}} が平方剰余であるとは、{{mvar|q}} に対し以下の条件を満たす整数 {{mvar|x}} が存在することを意味する：
: <math>x^2\equiv q \pmod{p}.</math>
平方剰余でない数を'''平方非剰余'''（へいほうひじょうよ、{{lang-en-short|quadratic nonresidue}}）と呼ぶ。

元々、[[合同算術]]という数論の一分野からの抽象的な[[数学]]的概念であった平方剰余は、現在様々な分野で応用されており、その応用先は[[音響工学]]から[[暗号理論|暗号化]]、大きな数の[[素因数分解]]にまで至る。

== 歴史、規約、および基本的な事実 ==
[[ピエール・ド・フェルマー|フェルマー]]、[[レオンハルト・オイラー|オイラー]]、[[ジョゼフ＝ルイ・ラグランジュ|ラグランジュ]]、[[アドリアン＝マリ・ルジャンドル|ルジャンドル]]をはじめとする17〜18世紀の数論者たちはそれぞれ平方剰余についての定理を確立し<ref>Lemmemeyer, Ch.1</ref>、予想を打ち立てた<ref>Lemmermeyer, pp.6-8, p.16 ff</ref>が、最初の体系的な扱いは[[カール・フリードリヒ・ガウス|ガウス]]の''[[Disquisitiones Arithmeticae]]''のIV節 (1801) である。Article 95では、「平方剰余」と「平方非剰余」という用語を導入し、文脈から明らかであれば、形容詞「平方」を削除できると述べている。

与えられた {{mvar|n}} に対して、{{mvar|n}} を法とする平方剰余のリストは単に {{math2|0, 1, …, {{Nowrap|''n'' &minus; 1}}}} を二乗するだけで得られる。{{math2|''a''{{sup|''2''}} ≡ (''n'' &minus; ''a''){{sup|2}} (mod ''n'')}} であるので、{{mvar|n}} を法とする平方数のリストは {{math|{{sfrac|''n''|2}}}} に対して対称であり、リストアップは {{math|{{sfrac|''n''|2}}}} まで続ければ十分である。これは下の表で確認できる。

つまり、{{mvar|n}} を法とする平方剰余の数は、{{math2|{{sfrac|''n''|2}} + 1}}（{{mvar|n}} が偶数）または {{math2|{{sfrac|''n'' + 1|2}}}}（{{mvar|n}} が奇数）を超えることはない<ref>Gauss, DA, art.94</ref>。

2つの剰余の積は常に剰余となる。

=== 素数の法 ===
2 を法とすると、すべての整数が平方剰余となる。

[[オイラーの規準]] (Euler's criterion) によると、奇[[素数]] ''p'' を法とすると、{{sfrac|''p'' + 1|2}} 個の剰余（0を含む）と {{sfrac|''p'' &minus; 1|2}} 個の非剰余が存在する。この場合、慣例として0を特殊なケースと見なし、[[可換体|体]] '''Z/''p''Z''' の{{仮リンク|Nを法とする整数の乗法群|en|Multiplicative group of integers modulo n|label=非ゼロ要素の乗法群}}内に議論を限定する。（言い換えると、''p'' を法とするゼロを除くすべての合同類は乗法逆元を持つ。これは合成数の法には当てはまらない。）<ref name="Gauss, DA, art.96">Gauss, DA, art.96</ref>

この規約に従うと、剰余の乗法逆元は剰余、非剰余の乗法逆元は非剰余であり<ref name="Gauss, DA, art.98">Gauss, DA, art.98</ref>、また、奇数の素数を法とすると剰余と非剰余が同数存在する<ref name="Gauss, DA, art.96">Gauss, DA, art.96</ref>。

素数を法とすると、2つの非剰余の積は剰余であり、非剰余と（非ゼロ）剰余の積は非剰余である<ref name="Gauss, DA, art.98">Gauss, DA, art.98</ref>。

[[平方剰余の相互法則]]への最初の補足<ref>Gauss, DA, art 111</ref>は、''p'' ≡ 1 (mod 4) ならば &minus;1 は ''p'' を法とする平方剰余であり、''p'' ≡ 3 (mod 4) ならば &minus;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) と同値である<ref>Gauss, DA, art.103</ref>。
<blockquote>たとえば、mod 32 の奇数の平方数は
: 1{{sup|2}} ≡ 15{{sup|2}} ≡ 1
: 3{{sup|2}} ≡ 13{{sup|2}} ≡ 9
: 5{{sup|2}} ≡ 11{{sup|2}} ≡ 25
: 7{{sup|2}} ≡ 9{{sup|2}} ≡ 49 ≡ 17

そして偶数のものは
: 0{{sup|2}} ≡ 8{{sup|2}} ≡ 16{{sup|2}} ≡ 0
: 2{{sup|2}} ≡ 6{{sup|2}} ≡ 10{{sup|2}} ≡ 14{{sup|2}} ≡ 4
: 4{{sup|2}} ≡ 12{{sup|2}} ≡ 16.
</blockquote>
したがって、0 以外の数が 8, 16, … を法として剰余となるのは、その数が 4{{sup|''k''}}(8''n'' + 1) の形で表現できる場合でかつその場合に限る。

奇素数 ''p'' と互いに素な数 ''a'' が、''p'' の任意のべき乗を法として剰余であるのは、''p'' を法として剰余である場合でかつその場合に限る<ref name="Gauss, DA, art.101">Gauss, DA, art.101</ref>。

法が ''p{{sup|n}}'' の場合、
: ''p{{sup|k}}a'' は
:: 剰余である（''k'' ≥ ''n'' の場合）
:: 非剰余である（''k'' < ''n'' が奇数の場合）
:: 剰余である（''k'' < ''n'' が偶数で ''a'' が剰余の場合）
:: 非剰余である（''k'' < ''n'' が偶数で ''a'' が非剰余の場合）<ref>Gauss, DA, art.102</ref>
ただし、2のべき乗と奇素数のべき乗では、ルールが異なることに注意せよ。

奇素数のべき乗 ''n'' = ''p{{sup|k}}'' を法として、''p'' と互いに素な剰余と非剰余の積は、''p'' を法としたときと同じルールに従う。''p'' は非剰余であり、一般に全ての剰余と非剰余に対して、その積の中の ''p'' のべき乗が ''n'' 以上ならば積がゼロとなることを除けば、同じルールに従う。

例えば 8 を法とすると、非剰余 3 と 5 の積は非剰余 7 であり、3, 5, 7 を互いに入れ替えた場合も同様である。実際、非剰余と1の乗法群は[[クラインの四元群]]を成す。

=== 素数のべき乗以外の合成数の法 ===
この場合の基本的な事実は
: ''a'' が ''n'' を法として剰余である場合、''a'' は'''すべての'''素数のべき乗 ''p{{sup|k}}'' が ''n'' を割り切る ''p{{sup|k}}'' を法として剰余である。
: ''a'' が ''n'' を法として非剰余である場合、''a'' は'''少なくとも1つの'''素数のべき乗 ''p{{sup|k}}'' が ''n'' を割り切る ''p{{sup|k}}'' を法として非剰余である。

合成数を法として、2つの剰余の積は剰余である。剰余と非剰余の積は、剰余、非剰余、またはゼロの場合がある。
<blockquote>たとえば、mod 6 の表から
: '''1''', 2, '''3''', '''4''', 5（'''太字'''は剰余）
剰余 3 と非剰余 5 の積は剰余 3 であるが、剰余 4と非剰余 2 の積は非剰余 2 である。
</blockquote>
また、2つの非剰余の積は、剰余、非剰余、またはゼロのいずれかになる。
<blockquote>たとえば、mod 15 の表から
: '''1''', 2, 3, '''4''', 5, '''6''', 7, 8, '''9''', '''10''', 11, 12, 13, 14（'''太字'''は剰余）
非剰余2と非剰余8の積は剰余1だが、非剰余2と非剰余7の積は非剰余14である。</blockquote>
この現象は、抽象代数の言葉でよく説明できる。法と互いに素な合同類は、[[環 (数学)|環]] '''Z/''n''Z''' の[[可逆元|単元群]]と呼ばれる乗法に関する[[群 (数学)|群]]であり、平方数はその[[部分群]]となる。異なる非剰余は異なる[[剰余類]]に属している可能性があり、それらの積がどの類に属するかを予測する単純なルールは存在しない。素数を法として、平方数の部分群と単一の剰余類が存在するのみである。

たとえば15を法とする非剰余3と5の積、または非剰余5と剰余9の積、または2つの剰余9と10の積がすべてゼロであるという事実は、完全な環 '''Z/''n''Z''' の中にあることから生じ、この環は合成数 ''n'' の [[零因子]]を持つ。

このため、一部の著者<ref>e.g., {{Harvnb|Ireland|Rosen|1990|p=50}}</ref>は、平方剰余 ''a'' は平方数であるだけでなく、法 ''n'' と[[互いに素 (整数論)|互いに素]]でなければならないという定義を追加している。（''a'' が ''n'' と互いに素となるのは、''a''{{sup|2}} が ''n'' と互いに素である場合でかつその場合に限る。）

これで話は片付くが、本記事では剰余が法と互いに素であるという定義は用いない。

== 記法 ==
ガウス<ref>Gauss, DA, art.131</ref>は、{{math|R}} と {{math|N}} を使用して、それぞれ剰余性と非剰余性を表現した。
: たとえば、{{math|2 R 7}} と {{math|5 N 7}}、また {{math|1 R 8}} と {{math|3 N 8}}
この表記はコンパクトで、いくつかの目的には便利であるが<ref>e.g. Hardy and Wright use it</ref><ref>Gauss, DA, art 230 ff.</ref>、より有用な表記は[[ディリクレ指標|二次指標]]とも呼ばれる[[ルジャンドル記号]]であり、すべての整数 ''a'' および正の奇[[素数]] {{mvar|p}} に対して次のように定義される。
: <math>\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}</math>
数値 ≡ 0 (mod {{mvar|p}}) を特別に扱う理由は2つある。1つは、これまで見てきたように、多くの公式や定理を簡単に説明できるためである。もう1つは、二次指標が乗算の下で、{{仮リンク|Nを法とする整数の乗法群|en|Multiplicative group of integers modulo n|label={{mvar|p}}を法とする非ゼロ合同類の乗法群}}から[[複素数]]への[[準同型]]であるためである。<math>(\tfrac{np}{p}) = 0</math> とすると、その[[定義域]]をすべての整数の乗法[[半群]]に拡張することができる<ref>This extension of the domain is necessary for defining ''L'' functions.</ref>。

ガウスの表記法よりも優れている点の1つは、ルジャンドル記号が数式として使用できる関数であることである<ref>See [[Legendre symbol#Properties of the Legendre symbol]] for examples</ref>。また、[[三次剰余の相互法則|3次]]、4次、および高次の剰余に簡単に一般化できる<ref>Lemmermeyer, pp.111-end</ref>。

ルジャンドル記号を {{mvar|p}} が合成数である場合に一般化したものとして[[ヤコビ記号]]があるが、その特性はそれほど単純ではない。{{mvar|m}} が合成数で、ヤコビ記号が <math>(\tfrac{a}{m}) = -1</math> ならば {{math|''a'' N ''m''}} であり、{{math2|''a'' R ''m''}} ならば <math>(\tfrac{a}{m}) = 1</math> である。しかし、<math>(\tfrac{a}{m}) = 1</math> ならば、{{math|''a'' R ''m''}} と {{math|''a'' N ''m''}} のいずれなのかは判断できない。例えば、<math>(\tfrac{2}{15}) = 1</math> と <math>(\tfrac{4}{15}) = 1</math> に対して、{{math|2 N 15}} と {{math|4 R 15}} である。{{mvar|m}} が素数の場合、ヤコビ記号とルジャンドル記号は同一のものとなる。

== 平方剰余の分布 ==
平方剰余は ''n'' を法としてランダムなパターンが見られ、これは音響や暗号などの応用で利用されているが、一方でその分布は規則性も示す。

[[等差数列|算術級数]]の素数に関する[[算術級数定理|ディリクレの定理]]、[[平方剰余の相互法則|平方剰余の定理]]、および[[中国の剰余定理]] (CRT) を使うと、任意の ''M'' > 0 に対して、1, 2, …, ''M'' が全て素数 ''p'' を法として剰余であることが簡単に分かる。
<blockquote>例えば、''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{{sup|2}} ≡ 1, 1046{{sup|2}} ≡ 2, 123{{sup|2}} ≡ 3, 2{{sup|2}} ≡ 4, 643{{sup|2}} ≡ 5, 87{{sup|2}} ≡ 6, 668{{sup|2}} ≡ 7, 429{{sup|2}} ≡ 8, 3{{sup|2}} ≡ 9, 529{{sup|2}} ≡ 10 (mod 2521) となる。
</blockquote>

=== ディリクレの公式 ===
こうした規則性の研究は、二進[[二次形式]]の[[イデアル類群|類数]]の[[類数公式|公式]]に関する（1830年代の）[[ペーター・グスタフ・ディリクレ|ディリクレ]]の研究に由来する<ref>{{Harvnb|Davenport|2000|pp=8-9, 43-51}}. These are classical results.</ref>。''q'' を素数、''s'' を複素変数とし、[[ディリクレのL関数]]を次のように定義する。
: <math>L(s) = \textstyle\sum\limits_{n=1}^\infty \left( \dfrac{n}{q} \right)n^{-s}</math>
ディリクレは、''q'' ≡ 3 (mod 3) のとき、
: <math>L(1) = -\frac{\pi}{\sqrt{q}} \textstyle\sum\limits_{n=1}^{q-1} \dfrac{n}{q} \left( \dfrac{n}{q} \right) > 0</math>
となることを示した。したがってこの場合（素数 ''q'' ≡ 3 (mod 4)）、平方剰余の和から 1, 2, …, ''q'' &minus; 1 の範囲における非剰余の和を引いたものは負の数になる。
<blockquote>たとえば、11を法とすると
:'''1''', 2, '''3''', '''4''', '''5''', 6, 7, 8, '''9''', 10（'''太字'''は剰余）
: 1 + 4 + 9 + 5 + = 22, 2 + 6 + 7 + 8 + 10 = 33、そして差は &minus;11 である。</blockquote>
実際、''q'' > 3の場合、差は常に ''q'' の奇数倍になる<ref>{{Harvnb|Davenport|2000|pp=49-51}}, (conjectured by [[カール・グスタフ・ヤコブ・ヤコビ|Jacobi]], proved by Dirichlet)</ref>。対照的に、平方剰余の和から 1, 2, …, ''q'' &minus; 1 の範囲における非剰余の和を引いたものはゼロであり、両方の和が <math>\frac{q(q-1)}{4}</math> と等しいことを意味する。

ディリクレは素数 ''q'' ≡ 3 (mod 4) の場合も証明した。
: <math>L(1) = \frac{\pi}{\left( 2-\left( \frac{2}{q} \right) \right) \!\sqrt{q}} \textstyle\sum\limits_{n=1}^{\frac{q-1}{2}} \left( \dfrac{n}{q} \right) > 0.</math>
これは、1, 2, …, {{sfrac|''q'' &minus; 1|2}} の範囲で、平方剰余が非剰余よりも多いことを意味する。
<blockquote>たとえば11を法とすると、6未満の剰余は4つ (1, 3, 4, 5) だが、非剰余は1つだけ (2) である。</blockquote>
これらの2つの定理に関する興味深い点は、これまでに知られているすべての証明が解析に基づくということである。どちらの定理についても、単純な証明あるいは直接の証明は発表されていない<ref>{{Harvnb|Davenport|2000|p=9}}</ref>。

=== 平方剰余の相互法則 ===
''p'' と ''q'' が奇素数の場合、
:「『''p'' は ''q'' を法とする平方剰余』と『''q'' は ''p'' を法とする平方剰余』が同値であること」は「''p'' と ''q'' の少なくとも1つが4を法として1に合同である」と同値である。
つまり、
: <math>\left( \frac{p}{q} \right) \left( \frac{q}{p} \right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}</math>
である。<math>\left( \frac{p}{q} \right)</math> は[[ルジャンドル記号]]である。

したがって、''a'' と ''a'' を割り切らない奇素数 ''p'' に対して、以下のようになる。
{|class="wikitable"
!''a''
!''a'' が ''p'' を法として平方剰余になる同値条件
!''a''
!''a'' が ''p'' を法として平方剰余になる同値条件
|-
|1
|（すべての素数''p'' ）
| −1
|''p'' ≡1 (mod 4)
|-
|2
|''p'' ≡1, 7 (mod 8)
| −2
|''p'' ≡1, 3 (mod 8)
|-
|3
|''p'' ≡1, 11 (mod 12)
| −3
|''p'' ≡1 (mod 3)
|-
|4
|（すべての素数''p''）
| −4
|''p'' ≡1 (mod 4)
|-
|5
|''p'' ≡1, 4 (mod 5)
| −5
|''p'' ≡1, 3, 7, 9 (mod 20)
|-
|6
|''p'' ≡1, 5, 19, 23 (mod 24)
| −6
|''p'' ≡1, 5, 7, 11 (mod 24)
|-
|7
|''p'' ≡1, 3, 9, 19, 25, 27 (mod 28)
| −7
|''p'' ≡1, 2, 4 (mod 7)
|-
|8
|''p'' ≡1, 7 (mod 8)
| −8
|''p'' ≡1, 3 (mod 8)
|-
|9
|（すべての素数''p'' ）
| −9
|''p'' ≡1 (mod 4)
|-
|10
|''p'' ≡1, 3, 9, 13, 27, 31, 37, 39, 43 (mod 40)
| −10
|''p'' ≡1, 7, 9, 11, 13, 19, 23, 37 (mod 40)
|-
|11
|''p'' ≡1, 5, 7, 9, 19, 26, 35, 37, 39, 43 (mod 44)
| −11
|''p'' ≡1, 3, 4, 5, 9 (mod 11)
|-
|12
|''p'' ≡1, 11 (mod 12)
| −12
|''p'' ≡1 (mod 3)
|}
{{See also|平方剰余の相互法則}}

=== 剰余と非剰余のペア ===
素数 ''p'' を法として、{{math2|''n'' R ''p''}} かつ {{math2|''n'' + 1 R ''p''}}、または {{math|''n'' N ''p''}} と {{math|''n'' + 1 R ''p''}} 等となるペア {{math2|''n'', ''n'' + 1}} の数はほぼ同じである。より正確には<ref>Lemmermeyer, p.29 ex.1.22; cf pp.26-27, Ch.10</ref><ref>Crandall & Pomerance, ex 2.38, pp.106-108</ref>、''p'' を奇素数として、''i'', ''j'' = 0, 1 によって以下の集合を定義し
: <math>A_{ij} = \left\{ k\in\{1,2,\cdots,p-2 \}: \left( \frac{k}{p} \right) = (-1)^i \land \left( \frac{k+1}{p} \right) = (-1)^j \right\},</math>

以下のように ''α{{sub|ij}}'' を定義する。
: <math>\alpha_{ij} = |A_{ij}|.</math>
つまり、以下のようになる。
: α{{sub|00}} は剰余に続く剰余の数
: α{{sub|01}} は非剰余に続く剰余の数
: α{{sub|10}} は剰余に続く非剰余の数
: α{{sub|11}} は非剰余に続く非剰余の数
すると、''p'' ≡ 1 (mod4) の場合、
: <math>\alpha_{00} = \frac{p-5}{4},\;\alpha_{01} =\alpha_{10} =\alpha_{11} = \frac{p-1}{4}</math>
であり、''p'' ≡ 3 (mod4) の場合、
: <math>\alpha_{01} = \frac{p+1}{4},\;\alpha_{00} =\alpha_{10} =\alpha_{11} = \frac{p-3}{4}.</math>
である。
<blockquote>例：（'''太字'''は剰余）
mod 17
:'''1''', '''2''', 3, '''4''', 5, 6, 7, '''8''', '''9''', 10, 11, 12, '''13''', 14, '''15''', '''16'''
:: ''A''{{sub|00}} = {1,8,15},
:: ''A''{{sub|01}} = {2,4,9,13},
:: ''A''{{sub|10}} = {3,7,12,14},
:: ''A''{{sub|11}} = {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''{{sub|00}} = {4、5、6、16},
:: ''A''{{sub|01}} = {1,7,9,11,17},
:: ''A''{{sub|10}} = {3,8,10,15},
:: ''A''{{sub|11}} = {2,12,13,14}.
</blockquote>
ガウス (1828)<ref>Gauss, ''Theorie der biquadratischen Reste, Erste Abhandlung'' (pp.511-533 of the ''Untersuchungen über hohere Arithmetik)''</ref>は、''p'' ≡ 1 (mod 4) ならば ''x''{{sup|4}} ≡ 2 (mod ''p'') という命題が ''p'' = ''a''{{sup|2}} + 64 ''b''{{sup|2}} と同値であることを証明し、この種の数え上げを導入した。

=== ポリア＝ヴィノグラドフの不等式 (Pólya-;Vinogradov inequality) ===
連続値 ''a'' に対する <math>(\tfrac{a}{p})</math> の値は[[コイントス]]のような確率変数で擬似的に表現できる<ref>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.</ref>。具体的には、[[ジョージ・ポリア|ポリア]]と{{仮リンク|イワン・ヴィノグラードフ|en|Ivan Matveyevich Vinogradov|label=ヴィノグラドフ}} (Vinogradov)<ref>{{Harvnb|Davenport|2000|pp=135–137}}, (proof of P-V, (in fact big-O can be replaced by 2); journal references for Paley, Montgomery, and Schur)</ref>が、1918年に（独立して）''q'' をとする非主(non-principal)[[ディリクレ指標]] χ(''n'') と任意の整数 ''M'', ''N'' に対して、[[ランダウの記号]]を用いて以下のように表現できることを証明した。
: <math>\left| \textstyle\sum\limits_{n=M+1}^{M+N} \chi(n) \right| =O \left( \sqrt{q} \log q \right)</math>
ここで
: <math>\chi(n) = \left( \frac{n}{q} \right)</math>
とすると、長さ ''N'' の任意の区間における ''q'' を法とする平方剰余の数が以下のように表せる。
: <math>\frac{1}{2}N + O(\sqrt{q} \log q)</math>
以下の式の証明は容易<ref>Planet Math: Proof of Pólya-Vinogradov Inequality in [[Quadratic residue#External links|external links]]. The proof is a page long and only requires elementary facts about Gaussian sums</ref>である。
: <math>\left| \textstyle\sum\limits_{n=M+1}^{M+N} \left( \dfrac{n}{q} \right) \right| < \sqrt{q} \log q</math>
実際<ref>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</ref>、
: <math>\left| \textstyle\sum\limits_{n=M+1}^{M+N} \left( \dfrac{n}{q} \right) \right| < \frac{4}{\pi^2} \sqrt{q} \log q+0.41 \sqrt{q} +0.61</math>
となる。

[[ヒュー・モンゴメリー|モンゴメリー]](Montgomery)と{{仮リンク|ボブ・ヴォーン|en|Robert Charles Vaughan (mathematician)|label=ヴォーン}}(Vaughan)は1977年にこれを改良し、[[一般化されたリーマン予想]]が真である場合、以下の式が成り立つことを示した。
: <math>\left| \textstyle\sum\limits_{n=M+1}^{M+N} \chi(n) \right| =O \left( \sqrt{q} \log \log q \right)</math>
この結果から本質的に改良されたわけではないが、[[イサイ・シューア|シューア]]は1918年に
: <math>\max_N \left| \textstyle\sum\limits_{n=1}^N \left( \dfrac{n}{q} \right) \right| > \dfrac{1}{2\pi} \sqrt{q}</math>
を示し、{{仮リンク|レイモンド・ペイリー|en|Raymond Paley|label=ペイリー}}(Paley)は1932年に
: <math>\max_N \left| \textstyle\sum\limits_{n=1}^N \left( \dfrac{d}{n} \right) \right| > \dfrac{1}{7} \sqrt{d} \log \log d</math>
を満たす ''d'' > 0 が無限に存在することを示した。

=== 最小二次非剰余 ===
''p'' を法とする最小平方剰余は明らかに1である。最小二次非剰余の大きさ ''n''(''p'') の問題は難しいが、常に素数である。上記ポリア＝ヴィノグラードフの不等式は <math>O(\sqrt{p} \log p)</math> を与える。無条件での最良推定値は、任意の {{math2|''θ'' > {{sfrac|1|4}}{{radic|''e''}}}} に対して ''n''(''p'') ≪ ''p{{sup|θ}}'' というものであり、{{仮リンク|指標の和|en|character sum}} (character sum) に関するバージェス (Burgess) の推定から得られた。[[一般化されたリーマン予想]]の仮定下では、アンケニー (Ankeny) が ''n''(''p'') ≪ (log ''p''){{sup|2}} を得た<ref>{{Cite book |title=Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis |first=Hugh L. |last=Montgomery |authorlink=Hugh Montgomery (mathematician) |publisher=[[American Mathematical Society]] |year=1994 |isbn=0-8218-0737-4 |zbl=0814.11001 |page=176}}</ref>。リニック (Linnik) は、''n''(''p'') > ''X{{sup|ε}}'' となる ''X'' より小さい ''p'' の数は、ε に依存する定数によって制限されることを示した<ref name="FI156">{{Cite book |title=Opera De Cribro |first=John B. |last=Friedlander |authorlink=John Friedlander |first2=Henryk |last2=Iwaniec |author2-link=Henryk Iwaniec |publisher=[[American Mathematical Society]] |year=2010 |isbn=0-8218-4970-0 |zbl=1226.11099 |page=156}}</ref>。

奇素数 ''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, …{{OEIS|id=A053760}}

=== 二次超過 ===
''p'' を奇素数とする。'''二次超過''' (Quadratic excess) ''E''(''p'') は、範囲 (0, {{sfrac|''p''|2}}) の平方剰余の数から 範囲 ({{sfrac|''p''|2}}, ''p'') の平方剰余の数を引いたものである（{{OEIS|A178153}}）。''p'' ≡ 1 mod 4 となる ''p'' では、−1 が平方剰余であり、剰余は {{math2|''r'' ↔ ''p'' - ''r''}} に対して対称であるので過剰はゼロである。''p'' ≡ 3 mod 4 となる ''p'' では、超過 ''E'' は常に正である<ref>{{Cite book |first=Paul T. |last=Bateman |authorlink=Paul T. Bateman |first2=Harold G. |last2=Diamond |title=Analytic Number Theory |publisher=World Scientific |year=2004 |isbn=981-256-080-7 |zbl=1074.11001 |page=250}}</ref>。

== 平方根を見つけることの複雑さ ==
つまり、数値 ''a'' と法 ''n'' が与えられたときに、以下のタスクがどれほど難しいか、ということである。
# ''x''{{sup|2}} ≡ ''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''{{sub|1}} 個、次のものを法として根の数が ''n''{{sub|2}} 個…と続けていくと、''n'' を法として ''n''{{sub|1}}''n''{{sub|2}}… 個の根が存在する。

素数のべき乗を法とする解を組み合わせて ''n'' を法とする解を作る理論的な方法は、[[中国の剰余定理]]と呼ばれ、効率的なアルゴリズムで実装できる<ref>{{Harvnb|Bach|Shallit|1996|p=104 ff}}; it requires O(log{{sup|2}} ''m'') steps where ''m'' is the number of primes dividing ''n''.</ref>。
<blockquote>例えば：
: ''x''{{sup|2}} ≡ 6 (mod 15) を解く。
:: ''x''{{sup|2}} ≡ 6 (mod 3) は1つの解 ''x'' = 0, ''x''{{sup|2}} ≡ 6 (mod 5) が2つの解 ''x'' = 1, 4 を持つ。
:: したがって、15を法として2つの解 ''x'' = 6, 9 が存在する。

: x{{sup|2}} ≡ 4 (mod 15) を解く。
:: x{{sup|2}} ≡ 4 (mod 3) は2つの解 ''x'' = 1, 2, x{{sup|2}} ≡ 4 (mod 5) が2つの解 ''x'' = 2, 3 を持つ。
:: したがって、15を法として4つの解 ''x'' = 2, 7, 8, 13 が存在する。

: x{{sup|2}} ≡ 7 (mod 15) を解く。
:: x{{sup|2}} ≡ 7 (mod 3) は2つの解 ''x'' = 1, 2 を持ち、''x''{{sup|2}} ≡ 7 (mod 5) は解が存在しない。
:: したがって、15を法として解が存在しない。
</blockquote>

=== 素数または素数べき乗の法 ===
まず、法 ''n'' が素数である場合、[[ルジャンドル記号]] <math>\left( \frac{a}{n} \right)</math> は[[ユークリッドの互除法]]のバリエーション<ref>{{Harvnb|Bach|Shallit|1996|p=113}}; computing <math>\left( \frac{a}{n} \right)</math> requires O(log ''a'' log ''n'') steps</ref>または[[オイラーの規準]]を使用して、[[ヤコビ記号|すばやく計算できる]]。-1の場合、解は存在しない。

次に <math>\left( \frac{a}{n} \right)=1</math> と仮定すると、''n'' ≡ 3 (mod 4) の場合 [[ジョゼフ＝ルイ・ラグランジュ|ラグランジュ]]は、解が以下の式によって与えられることを発見した。
: <math>x \equiv \pm\; a^{(n+1)/4} \pmod{n}</math>

そして[[アドリアン＝マリ・ルジャンドル|ルジャンドル]]は、''n'' ≡ 5 (mod 8) の場合の同様の解を発見した<ref>Lemmermeyer, p.29</ref>。
: <math>x \equiv \begin{cases}
  \pm\; a^{(n+3)/8} \pmod{n}
  & \text{ if } a \text{ is a quartic residue modulo } n \\
  \pm\; a^{(n+3)/8} 2^{(n-1)/4} \pmod{n}
  & \text{ if } a \text{ is a quartic non-residue modulo } n
  \end{cases}</math>
しかし、素数 ''n'' ≡ 1 (mod 8) に対しては、既知の公式が存在しない。{{仮リンク|トネリ・シャンクスのアルゴリズム|en|Tonelli–Shanks_algorithm|label=トネリ}}<ref>{{Harvnb|Bach|Shallit|1996|p=156 ff}}; the algorithm requires O(log{{sup|4}}''n'') steps.</ref>（1891年）と{{仮リンク|チポラのアルゴリズム|en|Cipolla's algorithm|label=チポラ}}<ref>{{Harvnb|Bach|Shallit|1996|p=156 ff}}; the algorithm requires O(log{{sup|3}} ''n'') steps and is also nondetermisitic.</ref>は、それぞれすべての素数の法に使える効率的なアルゴリズムを発見した。どちらのアルゴリズムも ''n'' を法とする平方非剰余を見つける必要があり、そのための効率的な既知の決定論的アルゴリズムは存在しない。しかし、1 から ''n'' の間の数の半分は非剰余であるため、非剰余が見つかるまで、ランダムに数 ''x'' を選んでルジャンドル記号 <math>\left( \frac{x}{n} \right)</math> を計算すると、すぐに非剰余が求まる。このアルゴリズムをわずかに変形したものが{{仮リンク|トネリ・シャンクスのアルゴリズム|en|Tonelli–Shanks algorithm}}である。

法 ''n'' が[[素数冪|素数]]のべき乗 ''n'' = ''p{{sup|e}}'' である場合、解は ''p'' を法として見つかるので、[[ヘンゼルの補題]]またはガウスのアルゴリズムを使用して ''n'' を法とする解に「持ち上げて」得られる<ref name="Gauss, DA, art.101">Gauss, DA, art.101</ref>。

=== 合成数の法 ===
法 ''n'' が素数のべき乗に素因数分解される場合、解は上記の通りである。

<math>n \not \equiv 2 \pmod4</math> で{{仮リンク|クロネッカーの記号|en|Kronecker symbol|label=クロネッカー記号}}(Kronecker symbol)が<math>\left( \tfrac{a}{n} \right) =-1</math> であれば、解は存在しない。''n'' ≡ 2 (mod 4) で <math>\left( \tfrac{a}{n/2} \right) =-1</math> である場合も、解は存在しない。「 <math>n \not \equiv 2 \pmod4</math> かつ <math>\left( \tfrac{a}{n} \right) =1</math>」または「 ''n'' ≡ 2 (mod 4) かつ <math>\left( \tfrac{a}{n/2} \right)=1</math>」 ならば、解が存在する場合としない場合がある。

''n'' の完全な素因数分解が不明な場合、「<math>\left( \tfrac{a}{n} \right) =1</math> かつ <math>n \not \equiv 2 \pmod4</math>」または「''n'' ≡ 2 (mod 4) かつ <math>\left( \tfrac{a}{n/2} \right)=1</math>」ならば、問題は ''n'' の[[素因数分解]]と等価であることが分かっている（つまり、どちらかの問題の効率的に解ければ、もう一方を効率的に解くことができる）。

<blockquote>上記の議論は、''n'' の素因数を知ることでどのくらい根を効率的に見つけることができるかを示している。合成数を法とする平方根を見つけるための効率的なアルゴリズムがあったとしよう。{{仮リンク|平方合同|en|congruence of squares}} (congruence of squares) の記事では、{{math2|''x''{{sup|2}} ≡ ''y''{{sup|2}} (mod ''n'')}} である二つの数 ''x'', ''y'' の求め方について説明しており、{{math2|''x'' ≠ ±''y''}} であれば ''n'' は十分効率的に素因数分解される。ここで乱数を生成し、''n'' を法として乱数を二乗し、効率的な平方根アルゴリズムで根を見つける。これを、最初に二乗した値（または ''n'' を法とする負の数）と等しくない数を返すまで繰り返した後に、平方合同で説明したアルゴリズムを用いる。素因数分解アルゴリズムの効率性は、この根探索器の特性そのものに依存するが（たとえば、すべての根を返すか？最小の根だけを返すか？ランダムな根を返すか？）、これは効率的である<ref>Crandall & Pomerance, ex.6.5 & 6.6, p.273</ref>。</blockquote>

''n'' を法として ''a'' が平方剰余であるか非剰余であるか（ {{math2|''a'' R ''n''}} または {{math2|''a'' N ''n''}} と表される）の判定は、ルジャンドル記号を計算することで、素数 ''n'' に対して効率的に行うことができる。ただし、''n'' が合成数の場合は{{仮リンク|平方剰余性問題|en|quadratic residuosity problem}} (quadratic residuosity problem) となり、これは素因数分解ほど{{仮リンク|計算難度の仮定|en|Computational hardness assumption|label=難しい}}かは分かっていないが、かなり難しいと考えられている。

一方、ある上限値 ''c'' より小さい ''x'' の解があるかどうかを判定する場合、この問題は[[NP完全問題|NP完全]]である<ref>{{Harvnb|Manders|Adleman|1978}}</ref>。ただし、これは ''c'' をパラメータとする{{仮リンク|固定パラメータ容易性|en|Parameterized complexity|label=固定パラメーターの扱いやすい}}問題である。

一般に、合成数 ''n'' を法として ''a'' が平方剰余であるかどうかを判定するには、次の定理を使用できる： <ref>{{Cite book |last=Burton |first=David |title=Elementary Number Theory |year=2007 |publisher=McGraw HIll |location=New York |page=195}}</ref>

{{math2|''n'' > 1}}とし、{{math2|1=gcd(''a'',''n'') = 1}}とする。{{math2|''x''{{sup|2}} ≡ ''a'' (mod ''n'')}} が解けることと以下の条件は同値である：
* ''n'' のすべての奇数の約数 ''p'' について、[[ルジャンドル記号]]表現が <math>\left( \frac{a}{p} \right) =1</math> である。
* ''n'' が4割り切れるが8で割り切れない場合は {{math2|''a'' ≡ 1 (mod 4)}}。または ''n'' が8で割り切れる場合は {{math2|''a'' ≡ 1 (mod 8)}}。
注：この定理を使うに当たって本質的には ''n'' の素因数分解が既知である必要がある。また、{{math2|1=gcd(''a'',''n'') = ''m''}} の場合、合同関係は {{math2|''a''/''m'' ≡ ''x''{{sup|2}}/''m'' (mod ''n''/''m'')}} に還元することができるが、（''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, …（{{OEIS|id=A000224}}）
''n'' を法とする平方数の数を数える式は、スタングル (Stangl) によって与えられる<ref>{{Citation |last=Stangl |first1=Walter D. |title=Counting Squares in ℤ{{sub|''n''}} |journal=Mathematics Magazine |volume=69 |number=4 |pages=285-289 |date=1996-10 |url=http://www.maa.org/sites/default/files/Walter_D22068._Stangl.pdf |doi=10.2307/2690536}}</ref>。

== 平方剰余の応用 ==
=== 音響 ===
[[拡散|サウンドディフューザー]]は、[[指数 (初等整数論)|原始根]]や平方剰余などの数論的概念に基づいている<ref>{{Cite web |author=Walker |first=R |title=The design and application of modular acoustic diffusing elements |url=http://downloads.bbc.co.uk/rd/pubs/reports/1990-15.pdf |publisher=BBC Research Department |accessdate=2016-10-25}}</ref>。

=== グラフ理論 ===
{{仮リンク|ペイリーグラフ|en|Paley graph}} (Paley graph) は、各素数 ''p'' ≡ 1 (mod 4) が{{仮リンク|カンファレンスグラフ|en|conference graph}}(conference graph)の無限族を形成する稠密な無向グラフであり、これによって[[対称行列|対称]]{{仮リンク|カンファレンス行列|en|conference matrix}} (conference matrix) の無限族が導かれる。

ペイリー双グラフ (Paley digraph) はペイリーグラフを有向グラフとしたもので、素数は ''p'' ≡ 3 (mod 4) を用い、[[交代行列|反対称]][[カンファレンス行列]]が導かれる。

これらのグラフの作成には、平方剰余が用いられる。

=== 暗号 ===
大きな合成数 ''n'' を法とする数値の平方根を見つけることは、素因数分解（これは{{仮リンク|計算難度の仮定|en|Computational hardness assumption|label=難しい}}と広く信じられている）に相当するという事実は、[[Rabin暗号]]や[[紛失通信プロトコル|紛失転送プロトコル]]などの[[暗号理論|暗号化スキーム]]の構築に使用されている。{{仮リンク|平方剰余性問題|en|quadratic residuosity problem}}は、{{仮リンク|ゴールドワッサー-ミカリ暗号|en|Goldwasser-Micali cryptosystem}}の基礎を成す。

[[離散対数]]も暗号化で用いられる同様の問題である。

=== 素数判定 ===
[[オイラーの規準]]は、''p'' が素数であるルジャンドル記号 (''a''|''p'') の公式である。''p'' が合成数の場合、公式は (''a''|''p'') を正しく計算できる場合もできない場合もある。与えられた数 ''n'' が素数であるか合成数であるかについての[[ソロベイ–シュトラッセン素数判定法|ソロベイ-シュトラッセン素数判定法]]は、ランダムな ''a'' を選び、ユークリッドの互除法の修正<ref>{{Harvnb|Bach|Shallit|1996|p=113}}</ref>とオイラーの基準を使用して (''a''|''n'') を計算する<ref>{{Harvnb|Bach|Shallit|1996|pp=109-110}}; Euler's criterion requires O(log{{sup|3}} ''n'') steps</ref>。結果が一致しない場合、''n'' は合成数である。一致する場合、''n'' は合成数または素数である。合成数 ''n'' に対して、2, 3, …, ''n'' &minus; 1 の範囲中、少なくとも半分の ''a'' では「''n'' は合成数」と判定されるが、素数 ''n'' に対しては何も出力しない。多くの異なる ''a'' を試しても ''n'' が合成数と判定されなければ、''n'' は[[確率的素数]]と呼ばれる。

[[ミラー–ラビン素数判定法]]も同じ原理に基づく。この判定法は決定論的なバージョンがあるが、これが正しく判定できるかの証明は[[一般化されたリーマン予想|一般化されたリーマン仮説]] (GRH) 依存する。この判定法の出力は、「''n'' は完全に合成数」または「''n'' は素数かGRHは偽である」のいずれかである。合成数 ''n'' に対して出力が後者の場合、GRHは偽になり、数学の多くの分野に影響を及ぼす可能性がある。

=== 素因数分解 ===
''Disquisitiones Arithmeticae''<ref>Gauss, DA, arts 329-334</ref>''§VI''で、ガウスは平方剰余と[[平方剰余の相互法則]]を使用する2つの素因数分解アルゴリズムについて説明している。

最新の素因数分解アルゴリズムのいくつか（{{仮リンク|ディクソンのアルゴリズム|en|Dixon's algorithm}} (Dixon's algorithm)、{{仮リンク|連分数法|en|continued fraction method}} (continued fraction method)、[[二次ふるい法]] (quadratic sieve)、{{仮リンク|数体ふるい|en|number field sieve}} (number field sieve) など）は、素因数分解につながる{{仮リンク|平方合同|en|congruence of squares}}を探す中で、（素因数分解される数を法とする）小さい平方剰余を生成する。数体ふるいは、既知の最も高速な汎用素因数分解アルゴリズムである。

== 平方剰余の表 ==
次の表（{{OEIS|id=A096008}}）は、法 1から75までの平方剰余のリストである（{{Color|crimson|赤字}}は、''n'' と互いに素ではないことを意味する）。（''n'' と互いに素な平方剰余については {{oeis|id=A096103}} を、非ゼロな平方剰余については {{oeis|id=A046071}} を参照せよ。）
{|class="wikitable"
!''n''
!法 ''n'' の平方剰余
!''n''
!法 ''n'' の平方剰余
!''n''
!法 ''n'' の平方剰余
|-
|1
|0
|26
|{{Color|crimson|0}}, 1, 3, {{Color|crimson|4}}, 9, {{Color|crimson|10}}, {{Color|crimson|12}}, {{Color|crimson|13}}, {{Color|crimson|14}}, {{Color|crimson|16}}, 17, {{Color|crimson|22}}, 23, 25
|51
|{{Color|crimson|0}}, 1, 4, {{Color|crimson|9}}, 13, {{Color|crimson|15}}, 16, {{Color|crimson|18}}, 19, {{Color|crimson|21}}, 25, {{Color|crimson|30}}, {{Color|crimson|33}}, {{Color|crimson|34}}, {{Color|crimson|36}}, {{Color|crimson|42}}, 43, 49
|-
|2
|{{Color|crimson|0}}, 1
|27
|{{Color|crimson|0}}, 1, 4, 7, {{Color|crimson|9}}, 10, 13, 16, 19, 22, 25
|52
|{{Color|crimson|0}}, 1, {{Color|crimson|4}}, 9, {{Color|crimson|12}}, {{Color|crimson|13}}, {{Color|crimson|16}}, 17, 25, 29, {{Color|crimson|36}}, {{Color|crimson|40}}, {{Color|crimson|48}}, 49
|-
|3
|{{Color|crimson|0}}, 1
|28
|{{Color|crimson|0}}, 1, {{Color|crimson|4}}, {{Color|crimson|8}}, 9, {{Color|crimson|16}}, {{Color|crimson|21}}, 25
|53
|{{Color|crimson|0}}, 1, 4, 6, 7, 9, 10, 11, 13, 15, 16, 17, 24, 25, 28, 29, 36, 37, 38, 40, 42, 43, 44, 46, 47, 49, 52
|-
|4
|{{Color|crimson|0}}, 1
|29
|{{Color|crimson|0}}, 1, 4, 5, 6, 7, 9, 13, 16, 20, 22, 23, 24, 25, 28
|54
|{{Color|crimson|0}}, 1, {{Color|crimson|4}}, 7, {{Color|crimson|9}}, {{Color|crimson|10}}, 13, {{Color|crimson|16}}, 19, {{Color|crimson|22}}, 25, {{Color|crimson|27}}, {{Color|crimson|28}}, 31, {{Color|crimson|34}}, {{Color|crimson|36}}, 37, {{Color|crimson|40}}, 43, {{Color|crimson|46}}, 49, {{Color|crimson|52}}
|-
|5
|{{Color|crimson|0}}, 1, 4
|30
|{{Color|crimson|0}}, 1, {{Color|crimson|4}}, {{Color|crimson|6}}, {{Color|crimson|9}}, {{Color|crimson|10}}, {{Color|crimson|15}}, {{Color|crimson|16}}, 19, {{Color|crimson|21}}, {{Color|crimson|24}}, {{Color|crimson|25}}
|55
|{{Color|crimson|0}}, 1, 4, {{Color|crimson|5}}, 9, {{Color|crimson|11}}, 14, {{Color|crimson|15}}, 16, {{Color|crimson|20}}, {{Color|crimson|25}}, 26, 31, 34, 36, {{Color|crimson|44}}, {{Color|crimson|45}}, 49
|-
|6
|{{Color|crimson|0}}, 1, {{Color|crimson|3}}, {{Color|crimson|4}}
|31
|{{Color|crimson|0}}, 1, 2, 4, 5, 7, 8, 9, 10, 14, 16, 18, 19, 20, 25, 28
|56
|{{Color|crimson|0}}, 1, {{Color|crimson|4}}, {{Color|crimson|8}}, 9, {{Color|crimson|16}}, 25, {{Color|crimson|28}}, {{Color|crimson|32}}, {{Color|crimson|36}}, {{Color|crimson|44}}, {{Color|crimson|49}}
|-
|7
|{{Color|crimson|0}}, 1, 2, 4
|32
|{{Color|crimson|0}}, 1, {{Color|crimson|4}}, 9, {{Color|crimson|16}}, 17, 25
|57
|{{Color|crimson|0}}, 1, 4, {{Color|crimson|6}}, 7, {{Color|crimson|9}}, 16, {{Color|crimson|19}}, {{Color|crimson|24}}, 25, 28, {{Color|crimson|30}}, {{Color|crimson|36}}, {{Color|crimson|39}}, {{Color|crimson|42}}, 43, {{Color|crimson|45}}, 49, {{Color|crimson|54}}, 55
|-
|8
|{{Color|crimson|0}}, 1, {{Color|crimson|4}}
|33
|{{Color|crimson|0}}, 1, {{Color|crimson|3}}, 4, {{Color|crimson|9}}, {{Color|crimson|12}}, {{Color|crimson|15}}, 16, {{Color|crimson|22}}, 25, {{Color|crimson|27}}, 31
|58
|{{Color|crimson|0}}, 1, {{Color|crimson|4}}, 5, {{Color|crimson|6}}, 7, 9, 13, {{Color|crimson|16}}, {{Color|crimson|20}}, {{Color|crimson|22}}, 23, {{Color|crimson|24}}, 25, {{Color|crimson|28}}, {{Color|crimson|29}}, {{Color|crimson|30}}, 33, {{Color|crimson|34}}, 35, {{Color|crimson|36}}, {{Color|crimson|38}}, {{Color|crimson|42}}, 45, 49, 51, {{Color|crimson|52}}, 53, {{Color|crimson|54}}, 57
|-
|9
|{{Color|crimson|0}}, 1, 4, 7
|34
|{{Color|crimson|0}}, 1, {{Color|crimson|2}}, {{Color|crimson|4}}, {{Color|crimson|8}}, 9, 13, 15, {{Color|crimson|16}}, {{Color|crimson|17}}, {{Color|crimson|18}}, 19, 21, 25, {{Color|crimson|26}}, {{Color|crimson|30}}, {{Color|crimson|32}}, 33
|59
|{{Color|crimson|0}}, 1, 3, 4, 5, 7, 9, 12, 15, 16, 17, 19, 20, 21, 22, 25, 26, 27, 28, 29, 35, 36, 41, 45, 46, 48, 49, 51, 53, 57
|-
|10
|{{Color|crimson|0}}, 1, {{Color|crimson|4}}, {{Color|crimson|5}}, {{Color|crimson|6}}, 9
|35
|{{Color|crimson|0}}, 1, 4, 9, 11, {{Color|crimson|14}}, {{Color|crimson|15}}, 16, {{Color|crimson|21}}, {{Color|crimson|25}}, 29, {{Color|crimson|30}}
|60
|{{Color|crimson|0}}, 1, {{Color|crimson|4}}, {{Color|crimson|9}}, {{Color|crimson|16}}, {{Color|crimson|21}}, {{Color|crimson|24}}, {{Color|crimson|25}}, {{Color|crimson|36}}, {{Color|crimson|40}}, {{Color|crimson|45}}, 49
|-
|11
|{{Color|crimson|0}}, 1, 3, 4, 5, 9
|36
|{{Color|crimson|0}}, 1, {{Color|crimson|4}}, {{Color|crimson|9}}, 13, {{Color|crimson|16}}, 25, {{Color|crimson|28}}
|61
|{{Color|crimson|0}}, 1, 3, 4, 5, 9, 12, 13, 14, 15, 16, 19, 20, 22, 25, 27, 34, 36, 39, 41, 42, 45, 46, 47, 48, 49, 52, 56, 57, 58, 60
|-
|12
|{{Color|crimson|0}}, 1, {{Color|crimson|4}}, {{Color|crimson|9}}
|37
|{{Color|crimson|0}}, 1, 3, 4, 7, 9, 10, 11, 12, 16, 21, 25, 26, 27, 28, 30, 33, 34, 36
|62
|{{Color|crimson|0}}, 1, {{Color|crimson|2}}, {{Color|crimson|4}}, 5, 7, {{Color|crimson|8}}, 9, {{Color|crimson|10}}, {{Color|crimson|14}}, {{Color|crimson|16}}, {{Color|crimson|18}}, 19, {{Color|crimson|20}}, 25, {{Color|crimson|28}}, {{Color|crimson|31}}, {{Color|crimson|32}}, 33, 35, {{Color|crimson|36}}, {{Color|crimson|38}}, 39, {{Color|crimson|40}}, 41, 45, 47, 49, {{Color|crimson|50}}, 51, {{Color|crimson|56}}, 59
|-
|13
|{{Color|crimson|0}}, 1, 3, 4, 9, 10, 12
|38
|{{Color|crimson|0}}, 1, {{Color|crimson|4}}, 5, {{Color|crimson|6}}, 7, 9, 11, {{Color|crimson|16}}, 17, {{Color|crimson|19}}, {{Color|crimson|20}}, 23, {{Color|crimson|24}}, 25, {{Color|crimson|26}}, {{Color|crimson|28}}, {{Color|crimson|30}}, 35, {{Color|crimson|36}}
|63
|{{Color|crimson|0}}, 1, 4, {{Color|crimson|7}}, {{Color|crimson|9}}, 16, {{Color|crimson|18}}, 22, 25, {{Color|crimson|28}}, {{Color|crimson|36}}, 37, 43, 46, {{Color|crimson|49}}, 58
|-
|14
|{{Color|crimson|0}}, 1, {{Color|crimson|2}}, {{Color|crimson|4}}, {{Color|crimson|7}}, {{Color|crimson|8}}, 9, 11
|39
|{{Color|crimson|0}}, 1, {{Color|crimson|3}}, 4, {{Color|crimson|9}}, 10, {{Color|crimson|12}}, {{Color|crimson|13}}, 16, 22, 25, {{Color|crimson|27}}, {{Color|crimson|30}}, {{Color|crimson|36}}
|64
|{{Color|crimson|0}}, 1, {{Color|crimson|4}}, 9, {{Color|crimson|16}}, 17, 25, 33, {{Color|crimson|36}}, 41, 49, 57
|-
|15
|{{Color|crimson|0}}, 1, 4, {{Color|crimson|6}}, {{Color|crimson|9}}, {{Color|crimson|10}}
|40
|{{Color|crimson|0}}, 1, {{Color|crimson|4}}, 9, {{Color|crimson|16}}, {{Color|crimson|20}}, {{Color|crimson|24}}, {{Color|crimson|25}}, {{Color|crimson|36}}
|65
|{{Color|crimson|0}}, 1, 4, 9, {{Color|crimson|10}}, 14, 16, {{Color|crimson|25}}, {{Color|crimson|26}}, 29, {{Color|crimson|30}}, {{Color|crimson|35}}, 36, {{Color|crimson|39}}, {{Color|crimson|40}}, 49, 51, {{Color|crimson|55}}, 56, 61, 64
|-
|16
|{{Color|crimson|0}}, 1, {{Color|crimson|4}}, 9
|41
|{{Color|crimson|0}}, 1, 2, 4, 5, 8, 9, 10, 16, 18, 20, 21, 23, 25, 31, 32, 33, 36, 37, 39, 40
|66
|{{Color|crimson|0}}, 1, {{Color|crimson|3}}, {{Color|crimson|4}}, {{Color|crimson|9}}, {{Color|crimson|12}}, {{Color|crimson|15}}, {{Color|crimson|16}}, {{Color|crimson|22}}, 25, {{Color|crimson|27}}, 31, {{Color|crimson|33}}, {{Color|crimson|34}}, {{Color|crimson|36}}, 37, {{Color|crimson|42}}, {{Color|crimson|45}}, {{Color|crimson|48}}, 49, {{Color|crimson|55}}, {{Color|crimson|58}}, {{Color|crimson|60}}, {{Color|crimson|64}}
|-
|17
|{{Color|crimson|0}}, 1, 2, 4, 8, 9, 13, 15, 16
|42
|{{Color|crimson|0}}, 1, {{Color|crimson|4}}, {{Color|crimson|7}}, {{Color|crimson|9}}, {{Color|crimson|15}}, {{Color|crimson|16}}, {{Color|crimson|18}}, {{Color|crimson|21}}, {{Color|crimson|22}}, 25, {{Color|crimson|28}}, {{Color|crimson|30}}, {{Color|crimson|36}}, 37, {{Color|crimson|39}}
|67
|{{Color|crimson|0}}, 1, 4, 6, 9, 10, 14, 15, 16, 17, 19, 21, 22, 23, 24, 25, 26, 29, 33, 35, 36, 37, 39, 40, 47, 49, 54, 55, 56, 59, 60, 62, 64, 65
|-
|18
|{{Color|crimson|0}}, 1, {{Color|crimson|4}}, 7, {{Color|crimson|9}}, {{Color|crimson|10}}, 13, {{Color|crimson|16}}
|43
|{{Color|crimson|0}}, 1, 4, 6, 9, 10, 11, 13, 14, 15, 16, 17, 21, 23, 24, 25, 31, 35, 36, 38, 40, 41
|68
|{{Color|crimson|0}}, 1, {{Color|crimson|4}}, {{Color|crimson|8}}, 9, 13, {{Color|crimson|16}}, {{Color|crimson|17}}, 21, 25, {{Color|crimson|32}}, 33, {{Color|crimson|36}}, 49, {{Color|crimson|52}}, 53, {{Color|crimson|60}}, {{Color|crimson|64}}
|-
|19
|{{Color|crimson|0}}, 1, 4, 5, 6, 7, 9, 11, 16, 17
|44
|{{Color|crimson|0}}, 1, {{Color|crimson|4}}, 5, 9, {{Color|crimson|12}}, {{Color|crimson|16}}, {{Color|crimson|20}}, 25, {{Color|crimson|33}}, {{Color|crimson|36}}, 37
|69
|{{Color|crimson|0}}, 1, {{Color|crimson|3}}, 4, {{Color|crimson|6}}, {{Color|crimson|9}}, {{Color|crimson|12}}, 13, 16, {{Color|crimson|18}}, {{Color|crimson|24}}, 25, {{Color|crimson|27}}, 31, {{Color|crimson|36}}, {{Color|crimson|39}}, {{Color|crimson|46}}, {{Color|crimson|48}}, 49, 52, {{Color|crimson|54}}, 55, 58, 64
|-
|20
|{{Color|crimson|0}}, 1, {{Color|crimson|4}}, {{Color|crimson|5}}, 9, {{Color|crimson|16}}
|45
|{{Color|crimson|0}}, 1, 4, {{Color|crimson|9}}, {{Color|crimson|10}}, 16, 19, {{Color|crimson|25}}, 31, 34, {{Color|crimson|36}}, {{Color|crimson|40}}
|70
|{{Color|crimson|0}}, 1, {{Color|crimson|4}}, 9, 11, {{Color|crimson|14}}, {{Color|crimson|15}}, {{Color|crimson|16}}, {{Color|crimson|21}}, {{Color|crimson|25}}, 29, {{Color|crimson|30}}, {{Color|crimson|35}}, {{Color|crimson|36}}, 39, {{Color|crimson|44}}, {{Color|crimson|46}}, {{Color|crimson|49}}, {{Color|crimson|50}}, 51, {{Color|crimson|56}}, {{Color|crimson|60}}, {{Color|crimson|64}}, {{Color|crimson|65}}
|-
|21
|{{Color|crimson|0}}, 1, 4, {{Color|crimson|7}}, {{Color|crimson|9}}, {{Color|crimson|15}}, 16, {{Color|crimson|18}}
|46
|{{Color|crimson|0}}, 1, {{Color|crimson|2}}, 3, {{Color|crimson|4}}, {{Color|crimson|6}}, {{Color|crimson|8}}, 9, {{Color|crimson|12}}, 13, {{Color|crimson|16}}, {{Color|crimson|18}}, {{Color|crimson|23}}, {{Color|crimson|24}}, 25, {{Color|crimson|26}}, 27, 29, 31, {{Color|crimson|32}}, 35, {{Color|crimson|36}}, 39, 41
|71
|{{Color|crimson|0}}, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 19, 20, 24, 25, 27, 29, 30, 32, 36, 37, 38, 40, 43, 45, 48, 49, 50, 54, 57, 58, 60, 64
|-
|22
|{{Color|crimson|0}}, 1, 3, {{Color|crimson|4}}, 5, 9, {{Color|crimson|11}}, {{Color|crimson|12}}, {{Color|crimson|14}}, 15, {{Color|crimson|16}}, {{Color|crimson|20}}
|47
|{{Color|crimson|0}}, 1, 2, 3, 4, 6, 7, 8, 9, 12, 14, 16, 17, 18, 21, 24, 25, 27, 28, 32, 34, 36, 37, 42
|72
|{{Color|crimson|0}}, 1, {{Color|crimson|4}}, {{Color|crimson|9}}, {{Color|crimson|16}}, 25, {{Color|crimson|28}}, {{Color|crimson|36}}, {{Color|crimson|40}}, 49, {{Color|crimson|52}}, {{Color|crimson|64}}
|-
|23
|{{Color|crimson|0}}, 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18
|48
|{{Color|crimson|0}}, 1, {{Color|crimson|4}}, {{Color|crimson|9}}, {{Color|crimson|16}}, 25, {{Color|crimson|33}}, {{Color|crimson|36}}
|73
|{{Color|crimson|0}}, 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 19, 23, 24, 25, 27, 32, 35, 36, 37, 38, 41, 46, 48, 49, 50, 54, 55, 57, 61, 64, 65, 67, 69, 70, 71, 72
|-
|24
|{{Color|crimson|0}}, 1, {{Color|crimson|4}}, {{Color|crimson|9}}, {{Color|crimson|12}}, {{Color|crimson|16}}
|49
|{{Color|crimson|0}}, 1, 2, 4, 8, 9, 11, 15, 16, 18, 22, 23, 25, 29, 30, 32, 36, 37, 39, 43, 44, 46
|74
|{{Color|crimson|0}}, 1, 3, {{Color|crimson|4}}, 7, 9, {{Color|crimson|10}}, 11, {{Color|crimson|12}}, {{Color|crimson|16}}, 21, 25, {{Color|crimson|26}}, 27, {{Color|crimson|28}}, {{Color|crimson|30}}, 33, {{Color|crimson|34}}, {{Color|crimson|36}}, {{Color|crimson|37}}, {{Color|crimson|38}}, {{Color|crimson|40}}, 41, {{Color|crimson|44}}, {{Color|crimson|46}}, 47, {{Color|crimson|48}}, 49, 53, {{Color|crimson|58}}, {{Color|crimson|62}}, 63, {{Color|crimson|64}}, 65, 67, {{Color|crimson|70}}, 71, 73
|-
|25
|{{Color|crimson|0}}, 1, 4, 6, 9, 11, 14, 16, 19, 21, 24
|50
|{{Color|crimson|0}}, 1, {{Color|crimson|4}}, {{Color|crimson|6}}, 9, 11, {{Color|crimson|14}}, {{Color|crimson|16}}, 19, 21, {{Color|crimson|24}}, {{Color|crimson|25}}, {{Color|crimson|26}}, 29, 31, {{Color|crimson|34}}, {{Color|crimson|36}}, 39, 41, {{Color|crimson|44}}, {{Color|crimson|46}}, 49
|75
|{{Color|crimson|0}}, 1, 4, {{Color|crimson|6}}, {{Color|crimson|9}}, 16, 19, {{Color|crimson|21}}, {{Color|crimson|24}}, {{Color|crimson|25}}, 31, 34, {{Color|crimson|36}}, {{Color|crimson|39}}, 46, 49, {{Color|crimson|51}}, {{Color|crimson|54}}, 61, 64, {{Color|crimson|66}}, {{Color|crimson|69}}
|}
{|class="wikitable" style="text-align:right"
|+平方剰余
!''x''
!1!!2!!3!!4!!5!!6!!7!!8!!9!!10!!11!!12!!13!!14!!15!!16!!17!!18!!19!!20!!21!!22!!23!!24!!25
|-style="text-align:right"
!''x''{{sup|2}}
!style="width:25px"|1
!style="width:25px"|4
!style="width:25px"|9
!style="width:25px"|16
!style="width:25px"|25
!style="width:25px"|36
!style="width:25px"|49
!style="width:25px"|64
!style="width:25px"|81
!100!!121!!144!!169!!196!!225!!256!!289!!324!!361!!400!!441!!484!!529!!576!!625
|-
!mod 1
|0||0||0||0||0||0||0||0||0||0||0||0||0||0||0||0||0||0||0||0||0||0||0||0||0
|-
!mod 2
|1||0||1||0||1||0||1||0||1||0||1||0||1||0||1||0||1||0||1||0||1||0||1||0||1
|-
!mod 3
|1||1||0||1||1||0||1||1||0||1||1||0||1||1||0||1||1||0||1||1||0||1||1||0||1
|-
!mod 4
|1||0||1||0||1||0||1||0||1||0||1||0||1||0||1||0||1||0||1||0||1||0||1||0||1
|-
!mod 5
|1||4||4||1||0||1||4||4||1||0||1||4||4||1||0||1||4||4||1||0||1||4||4||1||0
|-
!mod 6
|1||4||3||4||1||0||1||4||3||4||1||0||1||4||3||4||1||0||1||4||3||4||1||0||1
|-
!mod 7
|1||4||2||2||4||1||0||1||4||2||2||4||1||0||1||4||2||2||4||1||0||1||4||2||2
|-
!mod 8
|1||4||1||0||1||4||1||0||1||4||1||0||1||4||1||0||1||4||1||0||1||4||1||0||1
|-
!mod 9
|1||4||0||7||7||0||4||1||0||1||4||0||7||7||0||4||1||0||1||4||0||7||7||0||4
|-
!mod 10
|1||4||9||6||5||6||9||4||1||0||1||4||9||6||5||6||9||4||1||0||1||4||9||6||5
|-
!mod 11
|1||4||9||5||3||3||5||9||4||1||0||1||4||9||5||3||3||5||9||4||1||0||1||4||9
|-
!mod 12
|1||4||9||4||1||0||1||4||9||4||1||0||1||4||9||4||1||0||1||4||9||4||1||0||1
|-
!mod 13
|1||4||9||3||12||10||10||12||3||9||4||1||0||1||4||9||3||12||10||10||12||3||9||4||1
|-
!mod 14
|1||4||9||2||11||8||7||8||11||2||9||4||1||0||1||4||9||2||11||8||7||8||11||2||9
|-
!mod 15
|1||4||9||1||10||6||4||4||6||10||1||9||4||1||0||1||4||9||1||10||6||4||4||6||10
|-
!mod 16
|1||4||9||0||9||4||1||0||1||4||9||0||9||4||1||0||1||4||9||0||9||4||1||0||1
|-
!mod 17
|1||4||9||16||8||2||15||13||13||15||2||8||16||9||4||1||0||1||4||9||16||8||2||15||13
|-
!mod 18
|1||4||9||16||7||0||13||10||9||10||13||0||7||16||9||4||1||0||1||4||9||16||7||0||13
|-
!mod 19
|1
|4
|9||16||6||17||11||7||5||5||7||11||17||6||16||9||4||1||0||1||4||9||16||6||17
|-
!mod 20
|1||4||9||16||5||16||9||4||1||0||1||4||9||16||5||16||9||4||1||0||1||4||9||16||5
|-
!mod 21
|1||4||9||16||4||15||7||1||18||16||16||18||1||7||15||4||16||9||4||1||0||1||4||9||16
|-
!mod 22
|1||4||9||16||3||14||5||20||15||12||11||12||15||20||5||14||3||16||9||4||1||0||1||4||9
|-
!mod 23
|1||4||9||16||2||13||3||18||12||8||6||6||8||12||18||3||13||2||16||9||4||1||0||1||4
|-
!mod 24
|1||4||9||16||1||12||1||16||9||4||1||0||1||4||9||16||1||12||1||16||9||4||1||0||1
|-
!mod 25
|1||4||9||16||0||11||24||14||6||0||21||19||19||21||0||6||14||24||11||0||16||9||4||1||0
|}

== 関連項目 ==
* [[オイラーの規準]]
* [[ガウスの補題 (数論)]]
* {{仮リンク|ゾロタレフの補題|en|Zolotarev's lemma}}(Zolotarev's lemma)
* {{仮リンク|指標の和|en|character sum}}(Character sum)
* [[平方剰余の相互法則]]
* {{仮リンク|平方剰余コード|en|Quadratic residue code}}(Quadratic residue code)

== 脚注 ==
{{Reflist|30em}}

== 参考文献 ==
''[[Disquisitiones Arithmeticae]]''は、ガウスの[[古典ラテン語]]から[[英語]]と[[ドイツ語]]に翻訳されている。ドイツ語版には、数論に関するガウスのすべての論文が含まれている（平方剰余のすべての証明、[[ガウス和]]の符号の決定、[[四次剰余の相互法則]]の研究、および未発表のノート）。
* {{Citation|last=Gauss|first1=Carl Friedrich|last2=Clarke|first2=Arthur A. (translator into English)|title=Disquisitiones Arithemeticae|edition=Second corrected|publisher=[[Springer Science+Business Media|Springer]]|place=New York|year=1986|isbn=0-387-96254-9}}
* {{Citation|last=Gauss|first1=Carl Friedrich|last2=Maser|first2=H. (translator into German)|title=Untersuchungen über hohere Arithmetik|trans-title=Disquisitiones Arithemeticae & other papers on number theory|edition=second|publisher=Chelsea|place=New York|year=1965|isbn=0-8284-0191-8}}
* {{Citation|last=Bach|first1=Eric|last2=Shallit|first2=Jeffrey|series=Algorithmic Number Theory|volume=I|title=Efficient Algorithms|publisher=[[The MIT Press]]|place=Cambridge|year=1996|isbn=0-262-02405-5}}
* {{Citation|last=Crandall|first1=Richard|last2=Pomerance|first2=Carl|title=Prime Numbers: A Computational Perspective|publisher=Springer|place=New York|year=2001|isbn=0-387-94777-9}}
* {{Citation|last=Davenport|first1=Harold|title=Multiplicative Number Theory|edition=third|publisher=Springer|place=New York|year=2000|isbn=0-387-95097-4}}
* {{Citation|last=Garey|first1=Michael R.|author-link=Michael R. Garey|last2=Johnson|first2=David S.|author2-link=David S. Johnson|year=1979|title=Computers and Intractability: A Guide to the Theory of NP-Completeness|publisher=W. H. Freeman|isbn=0-7167-1045-5|url=https://archive.org/details/computersintract0000gare}} A7.1: AN1, pg.249.
* {{Citation|last=Hardy|first1=G. H.|last2=Wright|first2=E. M.|author1-link=G. H. Hardy|author2-link=E. M. Wright|title=An Introduction to the Theory of Numbers|edition=fifth|publisher=[[Oxford University Press]]|place=Oxford|year=1980|isbn=978-0-19-853171-5|url=https://archive.org/details/introductiontoth00hard}}
* {{Citation|last=Ireland|first1=Kenneth|last2=Rosen|first2=Michael|title=A Classical Introduction to Modern Number Theory|edition=second|publisher=Springer|place=New York|year=1990|isbn=0-387-97329-X}}
* {{Citation|last=Lemmermeyer|first1=Franz|title=Reciprocity Laws: from Euler to Eisenstein|publisher=Springer|place=Berlin|year=2000|isbn=3-540-66957-4}}
* {{Citation|first1=Kenneth L.|last=Manders|last2=Adleman|first2=Leonard|author2-link=Leonard Adleman|title=''NP''-Complete Decision Problems for Binary Quadratics|journal=Journal of Computer and System Sciences|volume=16|number=2|year=1978|pages=168&ndash;184|doi=10.1016/0022-0000(78)90044-2|postscript=.}}

== 外部リンク ==
* {{高校数学の美しい物語|685|平方剰余と基本的な問題}}
* {{MathWorld|urlname=QuadraticResidue|title=Quadratic Residue}}
* {{PlanetMath|urlname=PolyaVinogradovInequality|title=Proof of Pólya&ndash;Vinogradov inequality}}

{{DEFAULTSORT:へいほうしようよ}}
[[Category:NP完全問題]]
[[Category:合同算術]]
[[Category:平方剰余]]
[[Category:未査読の翻訳があるページ]]