[b][size=150][b]このワークシートは[url=https://www.geogebra.org/m/twxxx3yq]Math by Code[/url]の一部です。[br][/b][br]＜２次合同式が解けるかどうか＞[/size][/b][br]xが整数なら[br]２次方程式ｘ[sup]2[/sup]=ｂが整数解ともつのはｂが平方数のとき[br]というのはわかる。[br]たとえば、x[sup]2[/sup]=4は解けるが、ｘ[sup]2[/sup]=5は解けない。[br]では方程式が合同方程式ならどうだろうか。[br][br]たとえば、mod 7のとき[br]剰余はx={1,2,3,4,5,6}[br]x[sup]2[/sup](mod 7)={1,4,2,2,4,1}[br]xに７の倍数をたしてもこの結果はかわらない。[br]だから、x[sup]2[/sup]≡b(mod 7)に解があるのはb={1,2,4}のとき、[br]b={3,5,6}のときは解がない。[br]このように、｛1,2,4}は２回ずつ登場して、{3,5,6}の登場を阻んでいる。[br]この２回登場するｂの候補になる数と、阻まれて候補にならない数とに分かれている。[br]ｂの候補になる剰余を[color=#0000ff][b]平方剰余[/b][/color]と呼ぶ、候補にならない剰余を[color=#0000ff][b]平方非剰余[/b][/color]と呼ぶ。[br][br]mod pを変えてやってみても、同じ現象が起きる。[br][br]mod 13なら 6個の平方剰余と 6個の平方非剰余。[br]mod 17なら８個の平方剰余と８個の平方非剰余。[br]mod 37なら 1８個の平方剰余と1８個の平方非剰余。[br][color=#0000ff]（一般化）[br][b][size=150]mod pの剰余p-1個のうち、平方剰余は剰余の２乗リストに２回登場して、[br]平方非剰余の登場を阻む。[br][/size][size=200]平方剰余と平方非剰余は同数で、(p-1)/2[/size][/b][/color]=[math]\frac{p-1}{2}[/math] 個ある。[br] [br][color=#0000ff]（同数の理由）[/color][br]剰余をx={1,2,...,[math]\frac{p-1}{2},\frac{p+1}{2}[/math],.....,p-2,p-1}とするとき、[br]平均は(1+(p-1))/2=p/2だからこれが線対称の中心。[br]対称な位置にあるx=kとx=p-k が2乗すると、同一な剰余になるかを計算してみよう。[br][math]\left(p-k\right)^2\equiv\left(-k\right)^2\equiv k^2[/math](mod p)[br]だから、[b]剰余の中央(p/2)からあとは線対称に反復[/b]される。[br][br]また、剰余は(p-1)/2以下の[b]相異なる２数i,ｊの２乗の剰余が異なる[/b]ことを確認しよう。[br]iよりjが大きとすると、その差j-iは１以上で[math]\frac{p-1}{2}-1[/math]　以下だ。[br]その和i+jは1+2＝３以上で、[math]\frac{p-1}{2}+\frac{p-1}{2}-1=p-1-1=p-2[/math] 以下となる。[br]j[sup]2[/sup]-i[sup]2[/sup]=(j+i)(j-i)≡0(mod p)が言えるためには[br]和j+iがpの倍数になるか、差j-iがｐの倍数になること。[br]しかし、和は３以上p-2以下だからpの倍数にならない。[br]そして、差は１以上(p-1)/2-1だからp以上にはらず、０にもｐの倍数にもならない。[br]だから、j[sup]2[/sup]-i[sup]2[/sup]の剰余が0になることはないので、[b]iとjの２乗の剰余はバラバラだね。[/b]

フェルマーの小定理から[math]a^{p-1}\equiv1\left(modp\right)[/math][br]と関連付けてみよう。[br][br]素数pは３以上ならすべて奇数だから、ｐ−１は偶数だね。[br]だから、[math]m=\frac{p-1}{2}[/math] は整数になる。[br]フェルマーの小定理は[math]\left(a^m\right)^2\equiv1\left(modp\right)[/math] とかける。[br]だからa[sup]m[/sup]≡±1(mod p)になるね。[br]オイラーは[br]a[sup]m[/sup]≡[b]１(mod p)になるとき、aは平方剰余[/b]となり、[br]a[sup]m[/sup]≡[b]-1≡p-1 (mod p)になるとき、aは平方非剰余[/b]となる。[br]という、基準を見つけた。[br]つまり、[color=#0000ff][b][size=150]剰余のp-1乗の半分乗の剰余が１なら平方剰余[/size][/b][/color]だということだ。[br][br]実際に確認してみよう。[br]

[b][size=150]＜平方剰余の積の法則＞[/size][/b][br][br]平方剰余と平方非剰余の積を調べてみよう。[br]mod pのとき、m=(p-1)/2として、オイラー基準を思い出すと便利だ。[br]a,bが平方剰余ならa[sup]m[/sup]≡1(mod p), b[sup]m[/sup]≡1(mod p)[br]x,yが平方非剰余ならx[sup]m[/sup]≡-1(mod p), y[sup]m[/sup]≡-1(mod p)となる。[br]だから、[br]平方剰余同士の積のm乗は(ab)[sup]m[/sup]≡a[sup]m[/sup]b[sup]m[/sup]≡１・１≡1(mod p)で平方剰余[br]平方非剰余同士の積のｍ乗は(xy)[sup]m[/sup]≡x[sup]m[/sup]y[sup]m[/sup]≡(-1)(-1)≡1(mod p)から平方剰余[br]平方剰余と非剰余の積のｍ乗は(ax)[sup]m[/sup]≡a[sup]m[/sup]x[sup]m[/sup]≡(1)(-1)≡-1(mod p)から平方非剰余。[br]まるで、[color=#0000ff][b]正負の数の積、偶数奇数の和のような法則[/b][/color]が成り立つね。[br][br][b][size=150]＜ルジャンドル記号＞[/size][/b][br]よく使うものは記号化すると便利だ。[br]mod ｐでaが平方剰余なら、オイラー基準のm=(p-1)/2乗が１，非剰余なら−１だった。[br]もう、[color=#0000ff][b]ｍ乗のこともかかずに結果だけ書こう[/b][/color]という記号ができた。[br][br]mod p の剰余a の平方剰余を1、非剰余を−１と返す記号だ。[math]\left(\frac{a}{p}\right)[/math]だ。この値は1か-1。[br]こうすると、上記の３パータンを１つの式で表すことができる。[math]\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)=\left(\frac{ab}{p}\right)[/math] [br](ab/p)が-1になるのは異符号つまり、平方剰余と非剰余が１つずつ。[br](ab/p)が1になるのは同符号つまり、平方剰余どうしか、非剰余どうし。[br]だから、どんなaでも2乗すれば１なので、(a[sup]2[/sup]/p)=1です。[br]たとえば、[br][math]\left(\frac{a}{p}\right)\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)=\left(\frac{a^2}{p}\right)\left(\frac{b}{p}\right)=\left(\frac{b}{p}\right)[/math]　[br]すると、合成数のルジャンドル値は2乗を取り去った素数の積で[br]あらわせる。[br][color=#0000ff]（例)[/color]　[math]\left(\frac{50}{37}\right)=\left(\frac{5^2\cdot2}{37}\right)=\left(\frac{2}{37}\right)[/math] となるね。[br][br]ただ、ルジャンドル記号はtex文を使わないと、分数と同様に表示できないので入力も手間だ。[br]そこで、今後は[b][size=150]代用して(a/b)[/size][/b]とかくことにする。[br][br][b][size=150]＜ルジャンドル×オイラー＞[br][/size][/b]つぎは、ルジャンドルとオイラーの合体だ。[br]・オイラー基準によれば[br]mod ｐでaが平方剰余なら、オイラー基準のm=(p-1)/2乗が１，非剰余なら−１だった。[br]・ルジャンドル記号は、[br]mod ｐでaが平方剰余なら、（a/p)=１，非剰余なら（a/p)=−１だった。[br]この２つを合体しよう。[br]・[math]\left(\frac{a}{p}\right)=a^{\frac{\left(p-1\right)}{2}}\left(modp\right)[/math]　で、任意のaが法ｐで、平方剰余か非剰余かが、計算で出せるということになる。[br]（例）[math]\left(\frac{-1}{p}\right)=\left(-1\right)^{\frac{p-1}{2}}\left(modp\right)[/math] p=4k+1なら、指数が偶数のため、値は１で平方剰余となる。[br]　p=4k-1なら、指数が奇数のため、値は−１で平方非剰余となるね。[br][color=#0000ff][b][size=150][br]・「ラストの剰余（−１）のテスト」を各　mod pでやろう。[br]法p= 　　　　 { 3, 5, 7,11,13,17,19,23,29}に対して[br]半分の指数m=(p-1)/2={ 1, [u]2[/u], 3, 5, [u]6, 8[/u], 9, 11,[u]14[/u]}[br]ラストのテスト(-1)[sup]m [/sup]={-1,+1,-1, -1,+1,+1,-1,-1, +1} [br][/size][/b][/color][br]一応調べてはみたが、これは、やる前から結果が見えている。[br]ｐは奇数で、p-1で偶数にして、それ２で割ったのがｍだった。[br]それでも[color=#0000ff][b]ｍ自体が偶数２ｎになっていれば、（−１）[sup]偶数乗[/sup]＝１になるから、平方剰余[/b][/color]だし、[br]奇数２n＋１になっていれば平方非剰余になるだけのことだね。[br][br][color=#0000ff][b]m=2nの場合は、（ｐ−１）/2 = 2n だから、ｐ＝４n＋１、[br][/b][/color]m=2n+1の場合は、（p-1)/2=2n+1だから、ｐ＝４n＋3となる。[br][br]こうやって記号化することで法則が見えてきた。[br][color=#0000ff][b]ｐ≡１(mod4)なら(-1/p)≡1で平方剰余。[br][/b][/color]ｐ≡３≡-1(mod4)なら(-1/p)≡-1 で平方非剰余。[br]ということだ。[br]当然といえば当然な内容を形式化しただけだが、まとめると、[br][math]p\equiv1\left(mod4\right)\Longrightarrow\left(\frac{-1}{p}\right)=1,p\equiv-1\left(mod4\right)\Longrightarrow\left(\frac{-1}{p}\right)=-1[/math] [color=#0000ff][b][size=150](平方剰余の基本法則（第１））[br][math]\left(\frac{-1}{p}\right)=\left(-1\right)^{\frac{p-1}{2}}[/math][/size][/b][/color] ともかけるね。[br][br][color=#0000ff][b][size=150][u][br]質問：「剰余２のテスト」をすると、どんな法則が見つかりますか。[br][br][/u][/size][/b][/color]-1ほど単純ではないようだから、法ｐをmod 4やmod8で種類分けして[br]調べてみよう。[br]p=1(mod 4)≡1,5から、p≡1,5（mod8)[br]p=3(mod 4)=3,7から、p≡3,7(mod8)となる。[br]このために、p=1,3,5,7（mod８）に目をつけて調べてみよう。[br][color=#0000ff][b][size=150]法　p=　　　　　　　{ 3, 5, 7,11,13,17,19,23,29}に対して[br]半分の指数m=(p-1)/2={ 1, 2, [u]3[/u], 5, 6, [u]8[/u], 9, [u]11[/u],14}[br]剰余２のテスト(2)[sup]m [/sup]={ -1,-1,+1, -1,-1,+1, -1, +1, -1} [br]分類　p(mod8) 　　 ={ 3, 5, [u] 7[/u], 3, 5, [u]1[/u], 3 , [u]7[/u], 5 }[br][/size][/b][/color] [br][math]p\equiv1,7\left(mod8\right)\Longrightarrow\left(\frac{2}{p}\right)=1,p\equiv3,5\left(mod8\right)\Longrightarrow\left(\frac{2}{p}\right)=-1[/math][b][color=#0000ff][size=150]（平方剰余の基本法則（第２））[/size][/color][/b][br]あくまでも、これは予想である。mod4の分類では解決できないが、mod8で分類すると成り立つかもしれないね。[br][br]では、理由は？

[math]p\equiv1,7\left(mod8\right)\Longrightarrow\left(\frac{2}{p}\right)=1,p\equiv3,5\left(mod8\right)\Longrightarrow\left(\frac{2}{p}\right)=-1[/math]　（第２法則）[br]が成り立つ理由を考えるために[br]オイラー基準の成り立ち、[br]つまりフェルマーの小定理に遡って実験してみよう。[br]p= 7≡7(mod 8)のときは(2/p)=1, [br]p=11≡3(mod 8)のときは(2/p)=-1,[br]p=13≡5(mod 8)のときは(2/p)=-1,[br]p=17≡1(mod 8)のときは(2/p)=1を[br]フェルマーのときと同様に観察しよう。[br]正の剰余を1からp-1までならべる。[br]ただし、[br]ｘ＝{1,2,...,p-1}[br][b][color=#0000ff][size=150]2xをp-1以下になるようにp-1を超えたらpを引く。[br]さらに、m=(p-1)/2をこえたら、pをひいて負の数になるように[/size][/color][/b]表示してみよう。[br][b][color=#0000ff]・[/color]p= 7≡[color=#0000ff]7(mod 8)　[/color][/b]のとき[br]x={1,2,3,4,5,6}　の2xを7-1=6以下にする。[br]2x={2,4,6,8,10,12}={2,4,6,1,3,5}[br]m=(7-1)/2=3をこえたらp=7を引こう。[color=#0000ff]2xがm=3以下ならそのまま。[/color][br]2x(mod p)={2,4-7,6-7,1,3,5-7}={2,-3,-1,1,3,-2}[br]符号は除外すると、前半で絶対値が1,2,3が出揃い、後半で線対称で異符号に配置されたね。[br]そこで、ｘも２ｘも前半半分だけで比較しよう。[br]x={1,2,3}, 2x(mod p)=[b][color=#0000ff][size=150]{2,-3,-1}[/size][/color][/b][br]これの積はマイナスが２個あるので、３！で等しくなるね。[br]剰余なしならxの方の積は3!で、2x(mod p)の方の積は2[sup]3[/sup]3!だ。[br]だから、2[sup]3[/sup]3!≡3!(mod 7)となる。この２の3乗の３こそがm=(p-1)/3だ。しかも3!で約せる。[br]2[sup]3[/sup]≡1(mod 7)こうして、半分だけ調べることと、mをこえたらp引くことで、[br]オイラー基準の形につなげられたね。こうして、2はmod 7で平方剰余だね。[br][br][b][color=#0000ff]・[/color][color=#444444]p=11≡[/color][color=#0000ff]3(mod 8)　[/color][/b]のとき[br][color=#0000ff][b]m=(11-1)/2=5までの剰余[/b][/color]で調べよう。[br]x={1,2,3,4,5} の2xを11-1=10以下にする。[br]2x={2,4,6,8,10}={2,4,6,8,10}[br]m=5をこえたらp=11をひこう。[color=#0000ff]2xがm=5以下ならそのまま。[/color][br]2x(mod p)={2,4,6-11,8-11,10-11}=[color=#0000ff][b][size=150]{2,4,-5,-3,-1}[/size][/b][/color][br]x={1,2,3,4,5}これの積は5！になり、2x(mod p)の積はマイナスが3個あるので、-5！に等しくなるね。[br]剰余なしならxの方の積は5!で、2xの方の積は2[sup]5[/sup]5!だ。[br]だから、2[sup]5[/sup]5!≡-5!(mod 11)となる。5!で約せる。[br]2[sup]5[/sup]≡-1(mod 11)こうして、オイラー基準から２はmod 11で平方非剰余となるね。[br][br][b][color=#0000ff]・[/color]p=13≡[color=#0000ff]5(mod 8)　[/color][/b]のとき[br][color=#0000ff][b]m=(13-1)/2=6までの剰余[/b][/color]で調べよう。[br]x={1,2,3,4,5,6} の2xを13-1=12以下にする。[br]2x={2,4,6,8,10,12}={2,4,6,8,10,12}[br]m=6をこえたらp=13をひこう。[color=#0000ff]2xがm=6以下ならそのまま。[/color][br]2x(mod p)={2,4,6,8-13,10-13,12-13}=[color=#0000ff][b][size=150]{2,4,6,-5,-3,-1}[/size][/b][/color][br]x={1,2,3,4,5,6}これの積は6！になり、2x(mod p)の積はマイナスが3個あるので、-6！に等しくなるね。[br]剰余なしならxの方の積は6!で、2xの方の積は2[sup]6[/sup]6!だ。[br]だから、2[sup]6[/sup]6!≡-6!(mod 13)となる。6!で約せる。[br]2[sup]6[/sup]≡-1(mod 13)こうして、オイラー基準から２はmod 13で平方非剰余となるね。[br][br][b][color=#0000ff]・[/color]p=17≡[color=#0000ff]1(mod 8)　[/color][/b]のとき[br][color=#0000ff][b]m=(17-1)/2=8までの剰余[/b][/color]で調べよう。[br]x={1,2,3,4,5,6,7,8}の2xを17-1=16以下にする。[br]2x={2,4,6,8,10,12,14,16}={2,4,6,8,10,12,14,16}[br]m=8をこえたらp=17をひこう。[color=#0000ff]2xがm=8以下ならそのまま。[/color][br]2x(mod p)={2,4,6,8,10-17,12-17,14-17,16-17}=[b][size=150][color=#0000ff]{2,4,6,8,-7,-5,-3,-1}[/color][/size][/b][br]x={1,2,3,4,5,6,7,8}これの積は8！になり、2x(mod p)の積はマイナスが4個あるので、8！に等しくなるね。[br]剰余なしならxの方の積は8!で、2xの方の積は2[sup]8[/sup]8!だ。[br]だから、2[sup]8[/sup]8!≡8!(mod 17)となる。8!で約せる。[br]2[sup]8[/sup]≡1(mod 17)こうして、オイラー基準から２はmod 17で平方剰余となるね。[br][br][color=#0000ff][b]（一般化に向けて）[br]p＝2m+1(mod 8)のとき、[br]m=(p-1)/2までの剰余で調べる。[br][/b][/color]x={1,2,...,m}の2xをp-1=2m以下にする。[br]2x={2,3,4,......,2m}までは共通だ。[br]mをこえたときにpを引いた結果は[br][color=#0000ff][b][size=150]2x(mod p)={2,4,...,-3,-1}のように[br]2からの偶数の数列のあとに、-奇数の数列が-1までならぶ。[br]2x(mod p)も積の符号は負の数の個数で決まる。[br][/size][/b][/color]それを次に詳しくみよう。[br][color=#0000ff][b][size=150]（一般化）[/size][/b][/color][br][color=#0000ff][b][size=150][u]・p=8k+2n+1 (n=0,1,2,3) とする。[br][/u][/size][size=150]m=(p-1)/2=4k+n={4k, 4k+1, 4k+2, 4k+3}までの剰余で調べる。[/size][/b][/color][br]mod pの剰余はちょうど中央までで、x={1,2,.....,m}となる。だから、2x={2,4,......,2m}[br]2xがm＝4k+n (n=0,1,2,3)以下なら２ｘはそのまま。[br]xはm/2=(4k+n)/2=2k+n/2={2k, 2k+0.5, 2k+1,2k+1.5} 以下の整数剰余で、[br][color=#0000ff][b][size=150]ｓ={2k、2k, 2k+1, 2k+1 }[/size][/b][/color]以下が[b]正の剰余[/b]の個数。[br][color=#0000ff][b][size=150]p=8k+{[u]1[/u],3,5,[u]7[/u]}のときに対応する、[br][/size]負の剰余の個数[/b][/color]は、m-s={4k-2k, (4k+1)-2k, (4k+2)-(2k+1),(4k+3)-(2k+1)}[br]=[b][color=#0000ff][size=150]{[u]2k[/u], 2k+1, 2k+1,[u]2k+2[/u]}個。[/size][/color][/b][br]負の剰余が偶数になるときに、オイラー基準が１だから平方剰余、[br]負の剰余が奇数の場合は、オイラー基準が−１だから平方非剰余となる。[br]だから、p≡1,7(mod 8)なら(2/p)は平方剰余、p≡3,5(mod 8)なら(2/p)は平方非剰余。[br][br][br]ちなみに, t=[math]\frac{p^2-1}{8}[/math] とおくと、p≡r(mod 8)のとき、[br]r=1,7＝±1を代入すると、t=0で偶数になる。[br]r=3,5＝±3を代入すると、t=1で奇数になる。[br]だから、平方剰余の基本法則（第２）は[br][math]t=\frac{p^2-1}{8},\left(\frac{2}{p}\right)=\left(-1\right)^t[/math] ともかけるね。

[b][size=150]＜オイラー基準の思い起こし＞[br][/size][/b][br]オイラー基準で法と剰余を入れ替えてみよう。[br][math]\left(\frac{q}{p}\right)=q^{\frac{p-1}{2}}\equiv\pm1\left(modp\right)[/math][br][math]\left(\frac{p}{q}\right)=p^{\frac{q-1}{2}}\equiv\pm1\left(modq\right)[/math][br][br]法と剰余を入れ替えたとしても、[br]ルジャンドルの記号の計算を[b][size=150]別々に実行[/size][/b]し、[br]剰余の中央での剰余が１か−１で判断するものだった。[br]相互関係はないものとして計算してきましたね。[br][br]それに対して、相互関係を主張するのが相互法則です。[br]相互法則とは[br][math]\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=\left(-1\right)^{\frac{p-1}{2}\frac{q-1}{2}}[/math][br]のように、法と剰余を入れ替えたルジャンドル値が連動するというものです。[br][br][color=#0000ff][size=150][b]法ごと剰余の半分の指数[/b][/size][/color]が[b][size=150][color=#0000ff]両方奇数のときだけ値は別符号で−１[/color][/size][/b]、１つでも偶数があれば、[b][size=150][color=#0000ff]値は同符号の＋１[/color][/size][/b]と判定できる。[br][br]たとえば(23/3)と(3/23)はm=(3-1)/2=1、n=(23-1)/2=11で両方奇数だから、異符号となる。[br](23/3)の確認は23≡2≡-1(mod 3) 、23[sup]m[/sup]≡23[sup]1[/sup]=-1（mod3)ですぐできるね。[br]だから、(3/23）は-1と異符号だから、1となる。[br]