平方剰余（オイラーの基準）
１．平方剰余
このワークシートはMath by Codeの一部です。
＜２次合同式が解けるかどうか＞
xが整数なら
２次方程式ｘ2=ｂが整数解ともつのはｂが平方数のとき
というのはわかる。
たとえば、x2=4は解けるが、ｘ2=5は解けない。
では方程式が合同方程式ならどうだろうか。
たとえば、mod 7のとき
剰余はx={1,2,3,4,5,6}
x2(mod 7)={1,4,2,2,4,1}
xに７の倍数をたしてもこの結果はかわらない。
だから、x2≡b(mod 7)に解があるのはb={1,2,4}のとき、
b={3,5,6}のときは解がない。
このように、｛1,2,4}は２回ずつ登場して、{3,5,6}の登場を阻んでいる。
この２回登場するｂの候補になる数と、阻まれて候補にならない数とに分かれている。
ｂの候補になる剰余を平方剰余と呼ぶ、候補にならない剰余を平方非剰余と呼ぶ。
mod pを変えてやってみても、同じ現象が起きる。
mod 13なら 6個の平方剰余と 6個の平方非剰余。
mod 17なら８個の平方剰余と８個の平方非剰余。
mod 37なら 1８個の平方剰余と1８個の平方非剰余。
（一般化）
mod pの剰余p-1個のうち、平方剰余は剰余の２乗リストに２回登場して、
平方非剰余の登場を阻む。
平方剰余と平方非剰余は同数で、(p-1)/2= 個ある。
（同数の理由）
剰余をx={1,2,...,,.....,p-2,p-1}とするとき、
平均は(1+(p-1))/2=p/2だからこれが線対称の中心。
対称な位置にあるx=kとx=p-k が2乗すると、同一な剰余になるかを計算してみよう。
(mod p)
だから、剰余の中央(p/2)からあとは線対称に反復される。
また、剰余は(p-1)/2以下の相異なる２数i,ｊの２乗の剰余が異なることを確認しよう。
iよりjが大きとすると、その差j-iは１以上で 以下だ。
その和i+jは1+2＝３以上で、 以下となる。
j2-i2=(j+i)(j-i)≡0(mod p)が言えるためには
和j+iがpの倍数になるか、差j-iがｐの倍数になること。
しかし、和は３以上p-2以下だからpの倍数にならない。
そして、差は１以上(p-1)/2-1だからp以上にはらず、０にもｐの倍数にもならない。
だから、j2-i2の剰余が0になることはないので、iとjの２乗の剰余はバラバラだね。
ｐ−１個の剰余を平方剰余と非剰余にわけてみよう。
２．オイラーの基準
フェルマーの小定理から
と関連付けてみよう。
素数pは３以上ならすべて奇数だから、ｐ−１は偶数だね。
だから、 は整数になる。
フェルマーの小定理は とかける。
だからam≡±1(mod p)になるね。
オイラーは
am≡１(mod p)になるとき、aは平方剰余となり、
am≡-1≡p-1 (mod p)になるとき、aは平方非剰余となる。
という、基準を見つけた。
つまり、剰余のp-1乗の半分乗の剰余が１なら平方剰余だということだ。
実際に確認してみよう。
オイラー基準を確認してみよう
３．平方の剰余と非剰余の積は、正と負の積
＜平方剰余の積の法則＞
平方剰余と平方非剰余の積を調べてみよう。
mod pのとき、m=(p-1)/2として、オイラー基準を思い出すと便利だ。
a,bが平方剰余ならam≡1(mod p), bm≡1(mod p)
x,yが平方非剰余ならxm≡-1(mod p), ym≡-1(mod p)となる。
だから、
平方剰余同士の積のm乗は(ab)m≡ambm≡１・１≡1(mod p)で平方剰余
平方非剰余同士の積のｍ乗は(xy)m≡xmym≡(-1)(-1)≡1(mod p)から平方剰余
平方剰余と非剰余の積のｍ乗は(ax)m≡amxm≡(1)(-1)≡-1(mod p)から平方非剰余。
まるで、正負の数の積、偶数奇数の和のような法則が成り立つね。
＜ルジャンドル記号＞
よく使うものは記号化すると便利だ。
mod ｐでaが平方剰余なら、オイラー基準のm=(p-1)/2乗が１，非剰余なら−１だった。
もう、ｍ乗のこともかかずに結果だけ書こうという記号ができた。
mod p の剰余a の平方剰余を1、非剰余を−１と返す記号だ。だ。この値は1か-1。
こうすると、上記の３パータンを１つの式で表すことができる。
(ab/p)が-1になるのは異符号つまり、平方剰余と非剰余が１つずつ。
(ab/p)が1になるのは同符号つまり、平方剰余どうしか、非剰余どうし。
だから、どんなaでも2乗すれば１なので、(a2/p)=1です。
たとえば、
すると、合成数のルジャンドル値は2乗を取り去った素数の積で
あらわせる。
（例) となるね。
ただ、ルジャンドル記号はtex文を使わないと、分数と同様に表示できないので入力も手間だ。
そこで、今後は代用して(a/b)とかくことにする。
＜ルジャンドル×オイラー＞
つぎは、ルジャンドルとオイラーの合体だ。
・オイラー基準によれば
mod ｐでaが平方剰余なら、オイラー基準のm=(p-1)/2乗が１，非剰余なら−１だった。
・ルジャンドル記号は、
mod ｐでaが平方剰余なら、（a/p)=１，非剰余なら（a/p)=−１だった。
この２つを合体しよう。
・ で、任意のaが法ｐで、平方剰余か非剰余かが、計算で出せるということになる。
（例） p=4k+1なら、指数が偶数のため、値は１で平方剰余となる。
p=4k-1なら、指数が奇数のため、値は−１で平方非剰余となるね。
・「ラストの剰余（−１）のテスト」を各 mod pでやろう。
法p= { 3, 5, 7,11,13,17,19,23,29}に対して
半分の指数m=(p-1)/2={ 1, 2, 3, 5, 6, 8, 9, 11,14}
ラストのテスト(-1)m ={-1,+1,-1, -1,+1,+1,-1,-1, +1}
一応調べてはみたが、これは、やる前から結果が見えている。
ｐは奇数で、p-1で偶数にして、それ２で割ったのがｍだった。
それでもｍ自体が偶数２ｎになっていれば、（−１）偶数乗＝１になるから、平方剰余だし、
奇数２n＋１になっていれば平方非剰余になるだけのことだね。
m=2nの場合は、（ｐ−１）/2 = 2n だから、ｐ＝４n＋１、
m=2n+1の場合は、（p-1)/2=2n+1だから、ｐ＝４n＋3となる。
こうやって記号化することで法則が見えてきた。
ｐ≡１(mod4)なら(-1/p)≡1で平方剰余。
ｐ≡３≡-1(mod4)なら(-1/p)≡-1 で平方非剰余。
ということだ。
当然といえば当然な内容を形式化しただけだが、まとめると、
(平方剰余の基本法則（第１））
ともかけるね。
質問：「剰余２のテスト」をすると、どんな法則が見つかりますか。
-1ほど単純ではないようだから、法ｐをmod 4やmod8で種類分けして
調べてみよう。
p=1(mod 4)≡1,5から、p≡1,5（mod8)
p=3(mod 4)=3,7から、p≡3,7(mod8)となる。
このために、p=1,3,5,7（mod８）に目をつけて調べてみよう。
法 p= { 3, 5, 7,11,13,17,19,23,29}に対して
半分の指数m=(p-1)/2={ 1, 2, 3, 5, 6, 8, 9, 11,14}
剰余２のテスト(2)m ={ -1,-1,+1, -1,-1,+1, -1, +1, -1}
分類 p(mod8) ={ 3, 5, 7, 3, 5, 1, 3 , 7, 5 }
（平方剰余の基本法則（第２））
あくまでも、これは予想である。mod4の分類では解決できないが、mod8で分類すると成り立つかもしれないね。
では、理由は？
基本法則（第１）
４．平方剰余の第２法則の理由
（第２法則）
が成り立つ理由を考えるために
オイラー基準の成り立ち、
つまりフェルマーの小定理に遡って実験してみよう。
p= 7≡7(mod 8)のときは(2/p)=1,
p=11≡3(mod 8)のときは(2/p)=-1,
p=13≡5(mod 8)のときは(2/p)=-1,
p=17≡1(mod 8)のときは(2/p)=1を
フェルマーのときと同様に観察しよう。
正の剰余を1からp-1までならべる。
ただし、
ｘ＝{1,2,...,p-1}
2xをp-1以下になるようにp-1を超えたらpを引く。
さらに、m=(p-1)/2をこえたら、pをひいて負の数になるように表示してみよう。
・p= 7≡7(mod 8) のとき
x={1,2,3,4,5,6} の2xを7-1=6以下にする。
2x={2,4,6,8,10,12}={2,4,6,1,3,5}
m=(7-1)/2=3をこえたらp=7を引こう。2xがm=3以下ならそのまま。
2x(mod p)={2,4-7,6-7,1,3,5-7}={2,-3,-1,1,3,-2}
符号は除外すると、前半で絶対値が1,2,3が出揃い、後半で線対称で異符号に配置されたね。
そこで、ｘも２ｘも前半半分だけで比較しよう。
x={1,2,3}, 2x(mod p)={2,-3,-1}
これの積はマイナスが２個あるので、３！で等しくなるね。
剰余なしならxの方の積は3!で、2x(mod p)の方の積は233!だ。
だから、233!≡3!(mod 7)となる。この２の3乗の３こそがm=(p-1)/3だ。しかも3!で約せる。
23≡1(mod 7)こうして、半分だけ調べることと、mをこえたらp引くことで、
オイラー基準の形につなげられたね。こうして、2はmod 7で平方剰余だね。
・p=11≡3(mod 8) のとき
m=(11-1)/2=5までの剰余で調べよう。
x={1,2,3,4,5} の2xを11-1=10以下にする。
2x={2,4,6,8,10}={2,4,6,8,10}
m=5をこえたらp=11をひこう。2xがm=5以下ならそのまま。
2x(mod p)={2,4,6-11,8-11,10-11}={2,4,-5,-3,-1}
x={1,2,3,4,5}これの積は5！になり、2x(mod p)の積はマイナスが3個あるので、-5！に等しくなるね。
剰余なしならxの方の積は5!で、2xの方の積は255!だ。
だから、255!≡-5!(mod 11)となる。5!で約せる。
25≡-1(mod 11)こうして、オイラー基準から２はmod 11で平方非剰余となるね。
・p=13≡5(mod 8) のとき
m=(13-1)/2=6までの剰余で調べよう。
x={1,2,3,4,5,6} の2xを13-1=12以下にする。
2x={2,4,6,8,10,12}={2,4,6,8,10,12}
m=6をこえたらp=13をひこう。2xがm=6以下ならそのまま。
2x(mod p)={2,4,6,8-13,10-13,12-13}={2,4,6,-5,-3,-1}
x={1,2,3,4,5,6}これの積は6！になり、2x(mod p)の積はマイナスが3個あるので、-6！に等しくなるね。
剰余なしならxの方の積は6!で、2xの方の積は266!だ。
だから、266!≡-6!(mod 13)となる。6!で約せる。
26≡-1(mod 13)こうして、オイラー基準から２はmod 13で平方非剰余となるね。
・p=17≡1(mod 8) のとき
m=(17-1)/2=8までの剰余で調べよう。
x={1,2,3,4,5,6,7,8}の2xを17-1=16以下にする。
2x={2,4,6,8,10,12,14,16}={2,4,6,8,10,12,14,16}
m=8をこえたらp=17をひこう。2xがm=8以下ならそのまま。
2x(mod p)={2,4,6,8,10-17,12-17,14-17,16-17}={2,4,6,8,-7,-5,-3,-1}
x={1,2,3,4,5,6,7,8}これの積は8！になり、2x(mod p)の積はマイナスが4個あるので、8！に等しくなるね。
剰余なしならxの方の積は8!で、2xの方の積は288!だ。
だから、288!≡8!(mod 17)となる。8!で約せる。
28≡1(mod 17)こうして、オイラー基準から２はmod 17で平方剰余となるね。
（一般化に向けて）
p＝2m+1(mod 8)のとき、
m=(p-1)/2までの剰余で調べる。
x={1,2,...,m}の2xをp-1=2m以下にする。
2x={2,3,4,......,2m}までは共通だ。
mをこえたときにpを引いた結果は
2x(mod p)={2,4,...,-3,-1}のように
2からの偶数の数列のあとに、-奇数の数列が-1までならぶ。
2x(mod p)も積の符号は負の数の個数で決まる。
それを次に詳しくみよう。
（一般化）
・p=8k+2n+1 (n=0,1,2,3) とする。
m=(p-1)/2=4k+n={4k, 4k+1, 4k+2, 4k+3}までの剰余で調べる。
mod pの剰余はちょうど中央までで、x={1,2,.....,m}となる。だから、2x={2,4,......,2m}
2xがm＝4k+n (n=0,1,2,3)以下なら２ｘはそのまま。
xはm/2=(4k+n)/2=2k+n/2={2k, 2k+0.5, 2k+1,2k+1.5} 以下の整数剰余で、
ｓ={2k、2k, 2k+1, 2k+1 }以下が正の剰余の個数。
p=8k+{1,3,5,7}のときに対応する、
負の剰余の個数は、m-s={4k-2k, (4k+1)-2k, (4k+2)-(2k+1),(4k+3)-(2k+1)}
={2k, 2k+1, 2k+1,2k+2}個。
負の剰余が偶数になるときに、オイラー基準が１だから平方剰余、
負の剰余が奇数の場合は、オイラー基準が−１だから平方非剰余となる。
だから、p≡1,7(mod 8)なら(2/p)は平方剰余、p≡3,5(mod 8)なら(2/p)は平方非剰余。
ちなみに, t= とおくと、p≡r(mod 8)のとき、
r=1,7＝±1を代入すると、t=0で偶数になる。
r=3,5＝±3を代入すると、t=1で奇数になる。
だから、平方剰余の基本法則（第２）は
ともかけるね。
基本法則（第２）
５．相互法則
＜オイラー基準の思い起こし＞
オイラー基準で法と剰余を入れ替えてみよう。
法と剰余を入れ替えたとしても、
ルジャンドルの記号の計算を別々に実行し、
剰余の中央での剰余が１か−１で判断するものだった。
相互関係はないものとして計算してきましたね。
それに対して、相互関係を主張するのが相互法則です。
相互法則とは
のように、法と剰余を入れ替えたルジャンドル値が連動するというものです。
法ごと剰余の半分の指数が両方奇数のときだけ値は別符号で−１、１つでも偶数があれば、値は同符号の＋１と判定できる。
たとえば(23/3)と(3/23)はm=(3-1)/2=1、n=(23-1)/2=11で両方奇数だから、異符号となる。
(23/3)の確認は23≡2≡-1(mod 3) 、23m≡231=-1（mod3)ですぐできるね。
だから、(3/23）は-1と異符号だから、1となる。