平方剰余編集

  を奇素数、   で割り切れない数、  としたときに解を持つ、持たないにしたがって   平方剰余平方非剰余 という。

  のとき   が平方剰余、非剰余にしたがって

  とする。また、便宜上   とする。これをルジャンドル記号と呼ぶ。

したがって    の属する剰余類にのみ依存する。そして   ならば   の形の平方数は存在しない。

  である。

補題 1    の原始根とする。定理 2.3.4 から   が解を持つのと    で割り切れるというのは同値である。したがって

 

定理 2.10編集

  ならば  

証明
合同の推移性、または補題 1 によって明白。

定理 2.11編集

 

証明
補題 1 より  

定理 2.3.4 より 、これは

 

に等しい。ここで再び補題 1 より、これは

 

に等しい。

定理 2.12 (オイラーの規準)編集

 

証明 1
定理 2.3.4 から   が解を持つ、つまり   のとき、

 

ここで、  より、 

したがって  

逆に   、つまり   が解を持たないとき、再び定理 2.3.4 から

  このときフェルマーの小定理より

 

よって  

以上より定理は証明される。

証明 2
定理 1.8 より、  は剰余系をなすので、この中の任意の数   について   となる   がただ一つ存在する。これを  配偶と呼ぶことにする。

ここで   のとき    の解とすれば、  の配偶はそれ自身である。また、

  より   も方程式の解である。このとき   とすると   となり、奇素数であるという仮定に反する。したがって  

合同方程式の基本定理から、上の方程式の解を満たすもの、すなわち配偶が自身であるものは   の2つであり、他の   個の数は2個ずつ配偶があって、それらの積は

 

であるから、

 

以上より  

次に   のときは上の   のような数はないので配偶が   ペアできて

 

  は自明に前に属すので  (すなわちウィルソンの定理)。したがって、

  •  
  •  

これがオイラーの規準である。

平方剰余の相互法則編集

  を相異なる奇素数としたときに

  1.  
  2.  
  3.  

2, 3 をそれぞれ第一補充法則第二補充法則という。まずはそれぞれの意味を説明する。

1 は、  のどちらかが   の形のとき   で、どちらとも   の形のときに限り   である、という意味である。

2 は、  に解がある  

3 は、  のとき   で、  のとき   である。つまり   に解がある  

証明
2 から証明する。

オイラーの規準より、 

どちらも   の値を取り、  は奇素数なので  

さて、3 であるが、これにはガウスの補題を用いる。

ガウスの補題編集

  のとき、  をそれぞれ   で割ったときの余りが   より大きい数が   個あったとき、

 

証明
ある数を   で割った余りが   よりも大きいならば、それから   を引くと   よりも大きい負の余りを得る。つまり、絶対最小剰余である。上の   というのは負の絶対最小剰余の個数である。

  の任意の2つの数   について、

  であり、  より、  の中には絶対最小剰余として等しいもの、また絶対最小剰余として符号が逆なものも存在しない。すなわち全体として符号を無視すれば

  に合同で、そのうち負の数の個数が   である。したがって

 

だが、 1, 2, ...,   はいずれも   と互いに素なので

 

を得る。オイラーの規準によって

 

どちらも   に等しく、  は奇素数なので

 

さて 3 の証明だが、

 

の中で   より多いものの個数が   である。


(i)   のとき

  なので、この間にある偶数の数は   であり、 

また   より、  で、

 


(ii)   のとき

  なので、この間にある偶数の数は   であり、 

また   より、  で、

 


(iii)   のとき

  なので、この間にある偶数の数は   であり、 

また   より、  で、

 


(iv)   のとき

  なので、この間にある偶数の数は   であり、 

また   より、  で、

 


以上により 3 が証明される。


最後に相互法則であるが、初等整数論/平方剰余の相互法則の証明に譲る。

例 1   を求めよ。

相互法則より

 

となる。ここで、第二補充法則と相互法則を用いて

 

を得るから

 

とわかる。

例 2   が奇素数のとき

 

が成り立つ。