■切手問題(その3)

 n=2,a1=5,a2=8のとき,27よりも小さい14の数に対しては実現可能(0,5,8,10,13,15,16,18,20,21,23,24,25,26),14の数に対しては実現不可能(1,2,3,4,6,7,9.11.12,14,17,19,22,27).

 ちょうど半数が実現可能,半数が実現不可能であるという事実は,平方剰余を想起させる.2元1次形式と1元2次形式における共通点ということであろうか.

===================================

【1】平方剰余

 pを素数として,

  x^2=a  (mod p)

を考える.左辺は0,1,4,9,・・・と続く.

 たとえば,p=11のとき,

  a=0,1,4,9,5,3,3,5,9,4,1,・・・

を繰り返す.周期は11となるが,0でない余りは1,3,4,9のみである.この5つの数を11を法とする平方剰余,2,6,7,8,10を平方非剰余という.0は平方剰余でも平方非剰余でもない.

 p=13のとき,

  a=0,1,4,9,3,12,10,10,12,3,9,4,1,・・・

を繰り返す.周期は13となるが,0でない余りは1,3,4,9,10,12のみである.この6つの数を13を法とする平方剰余,2,5,6,7,8,11を平方非剰余という.

  a=0,1,4,9,5,3,3,5,9,4,1,・・・

  a=0,1,4,9,3,12,10,10,12,3,9,4,1,・・・

はいずれも対称であるが,なぜならば

  (p−x)^2=x^2=a  (mod p)

が成り立つからである.

===================================

【2】平方剰余の相互法則

  (a/p)=+1 ←→ aがpを法とする平方剰余

           (x^2=a modpなる整数xが存在するとき)

  (a/p)=−1 ←→ 平方非剰余(そうでないとき)

と定義します.

 たとえば,整数aに対して,

  x^2=a  modp

となる整数xが存在するかどうかを考えると

  Z/pZ=Fp={0,1,・・・,p−1}

について代入してみればいいわけで,p=5の場合,

  0^2=0,1^2=1,2^2=4,3^2=9=4,4^2=16=1

ですから,a=1,4(mod5)のときは平方剰余,a=2,3(mod5)のときは平方非剰余,すなわち,

  (1/5)=(4/5)=1,(2/5)=(3/5)=−1

となります.

  (a/p)=a^{(p-1)/2} (mod p)     (オイラー規準)

  (−1/p)=(−1)^{(p-1)/2},p≠2  (第1補充法則)

  (2/p)=(−1)^{(p^2-1)/8},p≠2  (第2補充法則)

すなわち,オイラー規準において,(−1/p)に関するものが第1補充法則,(2/p)に関するものが第2補充法則と呼ばれます.

 クロネッカーの指標やディリクレの指標はルジャンドル記号の計算に還元されるのですが,オイラー規準は法pに関するa^{(p-1)/2}の剰余を求めなければならないため,pが大きいとき(a/p)を決定するのはかなり大変です.それに対して,

  (q/p)(p/q)=(−1)^{(p-1)/2}{(q-1)/2}

が有名なガウスの平方剰余の相互法則です.

 前述のように(p/5)は簡単に計算されますが,その際,(5/p)すなわちx^2=5(modp)なる整数xがあるかどうかについてもわかるというのが平方剰余の相互法則なのです.(a/p)はガウスの相互法則を用いてすばやく計算することができます.

 たとえば,(3/p)の場合,ガウスの平方剰余の相互法則において,q=3とおくと

  (3/p)(p/3)=(−1)^{(p-1)/2}

(p/3)は簡単に計算できて

  p=+1(mod3)のとき1,

  p=−1(mod3)のとき−1

一方,(−1)^{(p-1)/2}は

  p=+1(mod4)のとき1,

  p=−1(mod4)のとき−1

ですから,まとめると

  p=1または11(mod12)→  1

  p=5または7(mod12) → −1

  それ以外のとき        →  0

となることが理解されます.

===================================

【3】おまけ

[Q]257は素数641を法とする平方剰余か? すなわち

  x^2=257  (mod 641)

を満たす自然数は存在するか?

[A](257/641)=(641/257)=(127/257)=(257/127)=(3/127)=−(127/3)==(1/2)=−1.よって,平方非剰余.

[Q]282は素数1597を法とする平方剰余か?

[A](282/1597)=(2/1597)(3/1597)(47/1597)

(2/1597)=−1,(3/1597)=1,(47/1597)=−1.よって,平方剰余.

===================================