平方剰余

数論 において、整数 q は、nを法とした完全な平方と合同である場合、n を法とした平方剰余 と 呼ばれます。つまり、次のような 整数x が存在する場合です。

${\displaystyle x^{2}\equiv q{\pmod {n}}.}$

それ以外の場合、q はn を法とする二次非剰余と呼ばれます 。

もともとモジュラー算術として知られる数論の分野からの抽象的な数学的概念であった平方剰余は、現在では音響工学から暗号化、大きな数の因数分解まで幅広い用途で使用されています。

フェルマー、オイラー、ラグランジュ、ルジャンドル、および17世紀と18世紀の他の数論学者は、平方剰余に関する定理^[1]を確立し、予想^{[2]を形成したが、最初の体系的な扱いは}ガウスの算数論（1801年）の§IVである。第95条では、「平方剰余」と「平方非剰余」という用語が導入され、文脈から明らかな場合は形容詞「平方」を省略してもよいと述べられている。

与えられたnに対して、 n を法とする平方剰余のリストは、 0, 1, ..., n − 1のすべての数を単に二乗することによって得られます。a ≡ b (mod n ) はa ² ≡ b ² (mod n )を意味するため、他の平方剰余は、得られたリストのいずれかと合同​​ (mod n ) です。 しかし、得られたリストは、互いに合同でない平方剰余 (mod n ) のみで構成されているわけではありません。 a ² ≡( n − a ) ² (mod n ) であるため、リスト 1, 2, ..., n − 1 (またはリスト 0, 1, ..., n ) のすべての数を二乗して得られたリストは、その中点について対称 (mod n ) であり、したがって実際にはリスト 0, 1, ..., n /2のすべての数を二乗するだけで済みます。 このようにして得られたリストには、互いに合同な数 (mod n )がまだ含まれている可能性があります。したがって、 nを法とする互いに不同な平方剰余の数はn /2 + 1（nが偶数）または（n + 1）/2（nが奇数）を超えることはできない。^[3]${\displaystyle \lfloor}$ ${\displaystyle \rfloor}$

2 つの剰余の積は常に剰余です。

2 を法として、すべての整数は平方剰余です。

奇数素数 pを法として、オイラーの基準により、 ( p + 1)/2個の剰余（0を含む）と( p −1)/2個の非剰余が存在する。この場合、0を特別な場合とみなし、体の非ゼロ元の乗法群内で作業するのが通例である。（言い換えると、pを法とするゼロ以外のすべての合同類には乗法逆が存在する。これは合成法には当てはまらない。）^[4] ${\displaystyle (\mathbb {Z} /p\mathbb {Z} )}$

この慣例に従うと、剰余の逆数は剰余であり、非剰余の逆数は非剰余である。^[5]

この規則に従うと、奇数の素数を法として剰余と非剰余の数は同数となる。^[4]

素数を法として、2つの非剰余数の積は剰余であり、非剰余数と（非ゼロの）剰余数の積は非剰余である。^[5]

二次相互法則の最初の補足^[6]は、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 ≡ 1 (mod 8)のときのみ、a はm を法とする剰余となる。^[7]

例えば、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.

したがって、非ゼロの数が 4 ^k (8 n + 1) の形式である場合に限り、その数は 8、16 などを法とする剰余となります。

奇数素数pと互いに素な数aがpの任意の累乗を法とした剰余である場合、かつその場合のみ、pを法とした剰余となる。^[8]

係数がp ^{n の}場合、

次にp ^k a

k ≥ nならばp ^{n を}法とする剰余である

k < nが奇数の場合、 p ^{n を}法とする非剰余である

k < nが偶数でaが剰余である場合、 p ^nを法とする剰余である

k < nが偶数でaが非剰余である場合、 aはp ^nを法とする非剰余である。^[9]

2 の累乗と奇数の素数の累乗ではルールが異なることに注意してください。

奇数の素数累乗n = p ^{k を}法として、 p と互いに素な剰余と非剰余の積は、p を法として扱う場合と同じ規則に従います。p は非剰余であり、一般にすべての剰余と非剰余は同じ規則に従いますが、積におけるpの累乗がn以上の場合には積がゼロになる点が異なります。

8 を法として、非剰余数 3 と 5 の積は非剰余数 7 であり、3、5、7 の順列についても同様です。実際、非剰余数と 1 の乗法群は、クラインの 4 元群を形成します。

この場合の基本的な事実は

a がn を法とする剰余である場合、n を割り切るすべての素数に対して、 a はp ^{k を}法とする剰余である。

aがn を法として非剰余である場合、少なくとも 1 つの素数n のべき乗に対して、a はp ^{k を}法として非剰余である。

合成数を法として、2 つの剰余の積は剰余です。剰余と非剰余の積は、剰余、非剰余、または 0 になります。

たとえば、係数 6 の表   から1、2、3、4、5 (剰余は太字)。

残基 3 と非残基 5 の積は残基 3 であり、残基 4 と非残基 2 の積は非残基 2 である。

また、2 つの非剰余の積は、剰余、非剰余、またはゼロのいずれかになります。

たとえば、   係数15 の表から1、2、3、4、5、6、7、8、9、10、11、12、13、14 ( 剰余は太字) 。

非残基 2 と 8 の積は残基 1 であり、非残基 2 と 7 の積は非残基 14 である。

この現象は、抽象代数の語彙を使用すると最もよく説明できます。法と互いに素な合同類は、乗法の下での群であり、環の単位群と呼ばれ、平方はその部分群です。異なる非剰余は異なる剰余類に属する可能性があり、それらの積がどの剰余類 に属するかを予測する単純な規則はありません。素数を法とすると、平方の部分群と単一の剰余類のみがあります。 ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )}$

例えば、15 を法として非剰余数 3 と 5 の積、非剰余数 5 と剰余数 9 の積、または 2 つの剰余数 9 と 10 の積がすべて 0 になるという事実は、合成数nに対して零因子を持つ完全環 での作業から得られます。 ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )}$

このため、一部の著者^[10]は、平方剰余aは平方であるだけでなく、法nと互いに素でなければならないという定義を追加しています。（aがnと互いに素である場合、かつa2^がnと互いに素である場合に限ります。）

物事はより整理されますが、この記事では留数が絶対値と互いに素でなければならないと主張しているわけではありません。

ガウス^{[11]は、残差と非残差を表すためにそれぞれ}RとNを使用した。

たとえば、2 つの R 7と5 つの N 7、または1 つの R 8と3 つの N 8 です。

この表記法は簡潔で、いくつかの目的には便利であるが、^{[12] [13]}より便利な表記法はルジャンドル記号であり、これは2次特性とも呼ばれ、すべての整数aと正の奇数素数 pに対して次のよう に定義される。

${\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}\;\;\,0&{\text{ if }}p{\text{ }}a\\+1&{\text{ if }}a\operatorname {R} p{\text{ and }}p{\text{ does not }}a\\-1&{\text{ if }}a\operatorname {N} p{\text{ and }}p{\text{ does not }}a\end{cases}}}$

数 ≡ 0 (mod p ) が特別に扱われる理由は 2 つあります。すでに述べたように、これによって多くの式や定理が簡単に述べられるようになります。もう 1 つの (関連する) 理由は、2 次特性がp を法とする非ゼロ合同類の乗法群から乗法による複素数への準同型であることです。 を設定することで、その定義域をすべての整数の乗法半群に拡張できます。^[14]${\displaystyle ({\tfrac {np}{p}})=0}$

ガウスの表記法に対するこの表記法の利点の1つは、ルジャンドル記号が数式で使用できる関数であるという点です。^{[15]また、} 3次、4次、さらに高次の剰余 に簡単に一般化できます。^[16]

pの合成値に対するルジャンドル記号の一般化であるヤコビ記号がありますが、その特性はそれほど単純ではありません。m が合成値でヤコビ記号 の場合、 N mとなり、 R m の場合、R mとN mのどちらがわからない場合は、 となります。たとえば、および ですが、 2 N 15かつ4 R 15です。mが素数の場合、ヤコビ記号とルジャンドル記号は一致します。 ${\displaystyle ({\tfrac {a}{m}})=-1,}$${\displaystyle ({\tfrac {a}{m}})=1,}$${\displaystyle ({\tfrac {a}{m}})=1}$${\displaystyle ({\tfrac {2}{15}})=1}$${\displaystyle ({\tfrac {4}{15}})=1}$

平方剰余はn を法としてかなりランダムなパターンで発生するように見え、これは音響や暗号化などのアプリケーションで利用されてきましたが、その分布にはいくつかの驚くべき規則性も見られます。

等差数列における素数に関するディリクレの定理、二次相互法則、および中国剰余定理(CRT)を使用すると、任意のM > 0に対して、数 1、2、...、M がすべてpを法とする剰余となるような素数pが存在することが簡単にわかります。

たとえば、p ≡ 1 (mod 8)、(mod 12)、(mod 5)、(mod 28) の場合、二次の相互法則により、 2、3、5、7 はすべてp を法とする剰余となり、したがって 1 から 10 までのすべての数も p を法とする剰余となります。 CRT によれば、これはp ≡ 1 (mod 840) と同じであり、ディリクレの定理によれば、この形式の素数は無限にあります。 2521 が最小で、実際は 1 ² ≡ 1、1046 ² ≡ 2、123 ² ≡ 3、2 2 ^≡ 4、643 ² ≡ 5、87 ² ≡ 6、668 ² ≡ 7、429 ² ≡ 8、3 ² ≡ 9、529 ² ≡ 10 (mod 2521) となります。

最初の規則性は、ピーター・グスタフ・ルジューン・ディリクレの2元2次形式の類数の解析公式に関する研究（1830年代）に由来する。^[17] qを素数、sを複素変数とし、ディリクレL関数を次のように 定義する。

${\displaystyle L(s)=\sum _{n=1}^{\infty }\left({\frac {n}{q}}\right)n^{-s}.}$

ディリクレは、q ≡ 3 (mod 4)ならば、

${\displaystyle L(1)=-{\frac {\pi }{\sqrt {q}}}\sum _{n=1}^{q-1}{\frac {n}{q}}\left({\frac {n}{q}}\right)>0.}$

したがって、この場合（素数q≡3 （mod4））、範囲1、2、...、 q −1の平方剰余の合計から非剰余の合計を引いた値は負の数になります。

例えば、11を法として、

1、2、3、4、5、6、7、8、9、10 （残基は太字）​​​​​​

1 + 4 + 9 + 5 + 3 = 22、2 + 6 + 7 + 8 + 10 = 33、差は -11 です。

実際、 q > 3の場合、差は常にqの奇数倍になります。^[18]対照的に、素数q ≡ 1 (mod 4) の場合、範囲 1、2、...、 q − 1の平方剰余の合計から非剰余の合計を引いた値はゼロであり、両方の合計が等しいことを意味します。^[要出典]${\displaystyle {\frac {q(q-1)}{4}}}$

ディリクレはまた、素数q≡3（mod4）に対して、

${\displaystyle L(1)={\frac {\pi }{\left(2-\left({\frac {2}{q}}\right)\right)\!{\sqrt {q}}}}\sum _{n=1}^{\frac {q-1}{2}}\left({\frac {n}{q}}\right)>0.}$

これは、数1、2、...、( q − 1)/2の中に、平方剰余の数のほうが非剰余の数よりも多いことを意味します。

たとえば、11 を法として、6 未満の剰余は 4 つ (つまり、1、3、4、5) ありますが、非剰余は 1 つ (2) だけです。

これら2つの定理に関する興味深い事実は、既知の証明はすべて分析に依存しているということです。どちらの定理についても、これまで誰も単純または直接的な証明を発表したことはありません。^[19]

pとq が奇数の素数である 場合、次のようになります。

(( p はq を法とする平方剰余である) かつその場合に限り、( q はp を法とする平方剰余である)) かつその場合に限り、( pとqの少なくとも 1 つが4 を法とする 1 と合同である)。

つまり、

${\displaystyle \left({\frac {p}{q}}\right)\left({\frac {q}{p}}\right)=(-1)^{{\frac {p-1}{2}}\cdot {\frac {q-1}{2}}}}$

ルジャンドル記号はどこにありますか。 ${\displaystyle \left({\frac {p}{q}}\right)}$

したがって、数aとaを割り切れない奇数の素数pについては次のようになります。

素数pを法として、n R pとn + 1 R p、またはn N pとn + 1 R pなどがほぼ等しいn 、 n + 1のペアの数。より正確には、 ^{[20] [21]} p を奇数の素数とする。i 、j = 0、1に対して、集合を定義する。

${\displaystyle A_{ij}=\left\{k\in \{1,2,\dots ,p-2\}:\left({\frac {k}{p}}\right)=(-1)^{i}\land \left({\frac {k+1}{p}}\right)=(-1)^{j}\right\},}$

そして

${\displaystyle \alpha _{ij}=|A_{ij}|.}$

つまり、

α _{00 は}残基が続く残基の数であり、

α _{01 は}非残基が続く残基の数であり、

α _{10 は}残基が続く非残基の数であり、

α _{11 は、}非残基の後に続く非残基の数です。

そしてp ≡ 1 (mod 4) の場合

${\displaystyle \alpha _{00}={\frac {p-5}{4}},\;\alpha _{01}=\alpha _{10}=\alpha _{11}={\frac {p-1}{4}}}$

そしてp≡3（mod4） の場合

${\displaystyle \alpha _{01}={\frac {p+1}{4}},\;\alpha _{00}=\alpha _{10}=\alpha _{11}={\frac {p-3}{4}}.}$

例えば: (残基は太字)

モジュロ17

1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16​​​​​​​​​​​​​​

00 = _{ 1,8,15}、

A ₀₁ = {2,4,9,13}、

10 = {3,7,12,14} _、

11 = {5,6,10,11} _。

モジュロ19

1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18​​​​​​​​​​​​​​​​​

00 = { _4,5,6,16 }、

A ₀₁ = {1,7,9,11,17}、

10 = { _3,8,10,15 }、

11 = {2,12,13,14} _。

ガウス（1828）^[22]は、 p≡1（mod 4）ならばx4≡2（mod p ）^がp  =  a2  + 64  b2^の場合にのみ解けることを証明したときに^、この種のカウントを導入しました。

の連続した値に対するの値は、コイン投げのようなランダム変数を模倣する。 [ ^23]具体的には、ポリアとヴィノグラドフは1918年に（独立に） ^[24]、任意の非主ディリクレ指標χ( n ) modulo qと任意の整数MとNに対して、 ${\displaystyle ({\tfrac {a}{p}})}$

${\displaystyle \left|\sum _{n=M+1}^{M+N}\chi (n)\right|=O\left({\sqrt {q}}\log q\right),}$

ビッグO表記法で設定

${\displaystyle \chi (n)=\left({\frac {n}{q}}\right),}$

これは、長さNの任意の区間におけるqを法とする平方剰余の数が

${\displaystyle {\frac {1}{2}}N+O({\sqrt {q}}\log q).}$

証明するのは 簡単である^[25]

${\displaystyle \left|\sum _{n=M+1}^{M+N}\left({\frac {n}{q}}\right)\right|<{\sqrt {q}}\log q.}$

実際、^[26]

${\displaystyle \left|\sum _{n=M+1}^{M+N}\left({\frac {n}{q}}\right)\right|<{\frac {4}{\pi ^{2}}}{\sqrt {q}}\log q+0.41{\sqrt {q}}+0.61.}$

モンゴメリとヴォーンは1977年にこれを改良し、一般化リーマン予想が正しいなら ば

${\displaystyle \left|\sum _{n=M+1}^{M+N}\chi (n)\right|=O\left({\sqrt {q}}\log \log q\right).}$

この結果は大幅に改善することはできない。なぜなら、シュアは1918年に次のことを証明していたからである。

${\displaystyle \max _{N}\left|\sum _{n=1}^{N}\left({\frac {n}{q}}\right)\right|>{\frac {1}{2\pi }}{\sqrt {q}}}$

そしてペイリーは1932年に

${\displaystyle \max _{N}\left|\sum _{n=1}^{N}\left({\frac {d}{n}}\right)\right|>{\frac {1}{7}}{\sqrt {d}}\log \log d}$

d > 0は無限にあります。

p を法とする最小の二乗剰余は明らかに 1 です。最小の二乗非剰余n ( p )の大きさの問題はより微妙ですが、常に素数であり、7 は 71 で初めて現れます。

上記のポリア・ヴィノグラードフの不等式はO( √p log p )となる。

最良の無条件推定値は、任意のθ>1/4√eに対してn ⁽ p ) ≪pθであり、これはバージェスの性格和の推定値によって得られる。^[27]

一般化リーマン予想を仮定すると、アンケニーはn ( p ) ≪ (log p ) ²を得た。^[28]

リンニックは、 n ( p )>Xε^となるようなXより小さいpの数はεに依存する定数で制限されることを示した。^[27]

奇数の素数pに対するp を法とする最小の二次非剰余は次のとおりです。

2、2、3、2、2、3、2、5、2、3、2、...（OEISの配列A053760）

p を奇数の素数とする。平方剰余 E ( p ) は、範囲 (0, p /2) の平方剰余の数から範囲 ( p /2, p ) の数を引いたものである ( OEISのシーケンスA178153 )。pが1 mod 4 と合同な場合、-1 は平方剰余であり、剰余はr ↔ p − rに関して対称であるため、剰余は0 になる。pが3 mod 4 と合同な場合、剰余Eは常に正になる。^[29]

つまり、数aと法nが与えられたとき、それはどれほど難しいか？

1. x ² ≡ a (mod n )を解くxが存在するかどうかを調べる
2. 存在すると仮定して、それを計算しますか?

ここで、素数法と合成法の重要な違いが現れます。a 素数pを法として、平方剰余a には1 + ( a | p ) 個の根があります (つまり、 a N pの場合は 0、 a ≡ 0 (mod p )の場合は 1 、 a R pかつ gcd( a,p ) = 1 の場合は 2 つです)。

一般に、合成係数n が異なる素数の累乗の積として表され、最初の係数を法とするn _{1 個の根、2 番目の係数を法とする}n _{2 個の根、… がある場合、 n を}法とするn ₁ n ₂ … 個の根が存在します。

素数累乗を法とする解を組み合わせてnを法とする解を作る理論的な方法は中国剰余定理と呼ばれ、効率的なアルゴリズムで実装することができる。^[30]

例えば：

x ² ≡ 6 (mod 15) を解きます。

x ² ≡ 6 (mod 3) には 0 という 1 つの解があります。x ² ≡ 6 (mod 5) には 1 と 4 という 2 つの解があります。

15 を法とする解は 6 と 9 の 2 つあります。

x ² ≡ 4 (mod 15) を解きます。

x ² ≡ 4 (mod 3) には 1 と 2 の 2 つの解があります。x ² ≡ 4 (mod 5) には 2 と 3 の 2 つの解があります。

15 を法とする解は 2、7、8、13 の 4 つあります。

x ² ≡ 7 (mod 15) を解きます。

x ² ≡ 7 (mod 3) には 1 と 2 の 2 つの解があります。x ² ≡ 7 (mod 5) には解はありません。

15 を法とする解は存在しません。

まず、法nが素数であれば、ルジャンドル記号は ユークリッドの互除法^[31]またはオイラーの判定法の変形を使用して素早く計算できる。それが−1であれば解はない。次に、 と仮定すると、n≡3(mod 4)であれば、ラグランジュは解が次のように与えられることを発見した 。${\displaystyle \left({\frac {a}{n}}\right)}$${\displaystyle \left({\frac {a}{n}}\right)=1}$

${\displaystyle x\equiv \pm \;a^{(n+1)/4}{\pmod {n}},}$

そしてルジャンドルはn≡5 （mod 8）の場合には同様の解^[32]を発見した。

${\displaystyle 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}}}$

しかし、素数n ≡ 1 (mod 8) の場合、既知の公式はありません。Tonelli ^[33] (1891 年) とCipolla ^{[34] は、}すべて の素数を法として機能できる効率的なアルゴリズムを発見しました。どちらのアルゴリズムも、n を法とする二次非剰余を求める必要があり、これを実行するための効率的な決定論的アルゴリズムは知られていません。しかし、1 からnまでの数の半分は非剰余なので、数x をランダムに選択し、非剰余が見つかるまでルジャンドル記号を計算すると、すぐに非剰余が生成されます。このアルゴリズムのわずかなバリエーションがTonelli–Shanks アルゴリズムです。 ${\displaystyle \left({\frac {x}{n}}\right)}$

nを法とする素数n = p ^{e の}べき乗 であれば、 pを法とする解が見つかり、ヘンゼルの補題またはガウスのアルゴリズムを使用してnを法とする解に「持ち上げる」ことができる。 ^[8]

モジュラスnが素因数分解されている場合の解決法は上で説明しました。

n が2 を法として 4 およびクロネッカー記号 と合同でない場合、解は存在しません。nが2 を法として 4 および と合同である場合も、解は存在しません。n が2を法として 4 および と合同でない場合、またはn が2 を法として 4 および と合同である場合、解が存在する場合と存在しない場合があります。 ${\displaystyle \left({\tfrac {a}{n}}\right)=-1}$${\displaystyle \left({\tfrac {a}{n/2}}\right)=-1}$${\displaystyle \left({\tfrac {a}{n}}\right)=1}$${\displaystyle \left({\tfrac {a}{n/2}}\right)=1}$

nの完全な因数分解が不明で、かつn が4 を法として 2 に合同でない場合、またはn が4 を法として 2 に合同で、かつ である場合、問題はnの整数因数分解と同等であることが分かっています(つまり、どちらかの問題に対する効率的な解法を使用して、もう一方の問題を効率的に解決できます)。 ${\displaystyle \left({\tfrac {a}{n}}\right)=1}$${\displaystyle \left({\tfrac {a}{n/2}}\right)=1}$

上の議論は、 nの因数を知ることで、いかに効率的に平方根を見つけられるかを示している。合成数を法として平方根を求める効率的なアルゴリズムがあるとしよう。記事「平方の合同」では、x ² ≡ y ² (mod n )かつx ≠ ± yとなる 2 つの数 x と y を見つけることが、いかにしてn を効率的に因数分解するのに十分であるかを論じている。乱数を生成し、それをn を法として二乗し、効率的な平方根アルゴリズムで根を求める。最初に二乗した数 (またはnを法として負の数) と等しくない数を返すまで繰り返し、その後「平方の合同」で説明されているアルゴリズムに従う。因数分解アルゴリズムの効率は、根を求めるアルゴリズムの正確な特性 (例えば、すべての根を返すのか、最小の根だけを返すのか、ランダムな根を返すのかなど) に依存するが、効率的である。^[35]

a が n を法とする平方剰余か非剰余か( a R nまたはa N nと表記) の判定は、素数nの場合はルジャンドル記号を計算することで効率的に行うことができます。ただし、合成数nの場合は、平方剰余問題が形成されます。これは因数分解ほど難しいとは知られていませんが、かなり難しいと想定されています。

一方、ある与えられた限界cより小さいxの解が存在するかどうかを知りたい場合、この問題はNP完全である。^[36]しかし、これはcをパラメータ とする固定パラメータ問題である。

一般に、aが合成数nを法とした平方剰余であるかどうかを判断するには、次の定理を使用することができます。^[37]

n > 1、かつgcd( a , n ) = 1とします。このとき、x ² ≡ a (mod n )が解けるのは、次の場合のみです。

• nのすべての奇数素因数pを表すルジャンドル 記号。${\displaystyle \left({\tfrac {a}{p}}\right)=1}$
• nが 4 で割り切れるが 8 で割り切れない場合はa ≡ 1 (mod 4) 、 nが 8 で割り切れる場合はa ≡ 1 (mod 8) 。

注: この定理は、本質的にnの因数分解が既知であることを前提としています。また、gcd( a , n ) = mの場合、合同はa / m ≡ x ² / 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、...（OEISのシーケンスA000224）

nを法とする平方数を数える公式はスタングルによって与えられている。^[38]

音響拡散装置は原始根や平方剰余などの数論的概念に基づいている。 ^[39]

ペイリーグラフは、各素数p ≡ 1 (mod 4)ごとに 1 つずつ存在する密な無向グラフで、無限の会議グラフ族を形成し、無限の対称 会議行列族を生成します。

Paley ダイグラフは、各p ≡ 3 (mod 4)ごとに 1 つずつ存在する Paley グラフの有向類似物であり、反対称の会議行列を生成します。

これらのグラフの構築には、平方剰余が使用されます。

大きな合成数n を法とする数の平方根を求めることが因数分解（一般に難しい問題であると考えられている）と同等であるという事実は、ラビン暗号システムや忘却転送などの暗号方式の構築に利用されてきた。2次剰余問題が、ゴールドワッサー-ミカリ暗号システムの基礎となっている。

離散対数も同様の問題であり、暗号化にも使用されます。

オイラーの判定法は、ルジャンドル記号 ( a | p )の公式であり、 pは素数です。pが合成数の場合、この公式は ( a | p ) を正しく計算する場合としない場合があります。与えられた数nが素数か合成数かを判定するSolovay–Strassen 素数判定法では、ランダムにaを選び、ユークリッドの互除法^[40]の修正版とオイラーの判定法^{[41]を使用して (} a | n ) を計算します。結果が一致しない場合は、n は合成数です。 結果が一致する場合は、n は合成数か素数かのどちらかです。 合成数nの場合、範囲 2、3、...、 n − 1 にあるaの値の少なくとも 1/2 は「 nは合成数」を返しますが、素数nの場合はどれも返しません。 aのさまざまな値を使用してもnが合成数であることが証明されない場合は、「可能性のある素数」と呼ばれます。

ミラー・ラビン素数判定も同じ原理に基づいています。この判定には決定論的バージョンがありますが、それが機能するという証明は一般化されたリーマン予想に依存します。この判定からの出力は「n は間違いなく合成数である」または「nが素数であるか、GRH が偽であるかのいずれかである」です。合成数nに対して 2 番目の出力が発生した場合、GRH は偽となり、数学の多くの分野に影響を及ぼします。

ガウスは『算術論』第6章^[42]で、平方剰余と平方相互法則を使った2つの因数分解アルゴリズムについて論じている。

いくつかの最新の因数分解アルゴリズム (ディクソンのアルゴリズム、連分数法、二次ふるい、数体ふるいなど) は、因数分解される平方の合同性を見つけようとして、小さな二次剰余 (因数分解される数を法として) を生成します。数体ふるいは、知られている中で最も高速な汎用因数分解アルゴリズムです。

次の表 ( OEISのシーケンスA096008 ) には、 1 から 75 までの剰余がリストされています (赤い数字はnと互いに素でないことを意味します)。 ( nと互いに素な剰余については、 OEIS : A096103を参照してください。非ゼロの剰余については、OEIS : A046071を参照してください。)

• オイラーの基準
• ガウスの補題
• ゾロタレフの補題
• 文字の合計
• 二次相互法則
• 二次剰余コード

『算数論』はガウスのキケロ語ラテン語から英語とドイツ語に翻訳されています。ドイツ語版には、数論に関するガウスの論文がすべて収録されています。二次の相互法則のすべての証明、ガウス和の符号の決定、双二次の相互法則の研究、未発表のメモなどです。

• ガウス、カール・フリードリヒ（1986）、Disquisitiones Arithemeticae、クラーク、アーサー・A（第2版）訳、ニューヨーク：シュプリンガー、ISBN 0-387-96254-9
• Gauss, Carl Friedrich (1965)、Untersuchungen über hohere Arithmetik [ Disquisitiones Arithemeteticae & other places on Number Theory ]、Maser, H. 訳 (第 2 版)、ニューヨーク: チェルシー、ISBN 0-8284-0191-8
• バッハ、エリック、シャリット、ジェフリー（1996）、効率的なアルゴリズム、アルゴリズム的数論、第1巻、ケンブリッジ：MITプレス、ISBN 0-262-02405-5
• クランドール、リチャード、ポメランス、カール（2001）、素数：計算の観点、ニューヨーク：シュプリンガー、ISBN 0-387-94777-9
• ダベンポート、ハロルド（2000）、乗法数論（第3版）、ニューヨーク：シュプリンガー、ISBN 0-387-95097-4
• ゲイリー、マイケル・R. ;ジョンソン、デビッド・S. (1979)、「コンピュータと扱いにくさ：NP完全性理論へのガイド」、WHフリーマン、ISBN 0-7167-1045-5A7.1: AN1、249ページ。
• ハーディ、GH ;ライト、EM（1980）、数論入門（第5版）、オックスフォード：オックスフォード大学出版局、ISBN 978-0-19-853171-5
• アイルランド、ケネス、ローゼン、マイケル（1990）、現代数論への古典的入門（第2版）、ニューヨーク：シュプリンガー、ISBN 0-387-97329-X
• Lemmermeyer、Franz (2000)、相反性の法則: オイラーからエイゼンシュタインまで、ベルリン: Springer、ISBN 3-540-66957-4
• Manders, Kenneth L.; Adleman, Leonard (1978)、「二項二次方程式のNP完全決定問題」、Journal of Computer and System Sciences、16 (2): 168–184、doi : 10.1016/0022-0000(78)90044-2。

• Weisstein、Eric W.「二次剰余」。MathWorld。
• PlanetMathにおける Pólya–Vinogradov 不等式の証明。