1.整数論の基礎知識               戻る

(1) ガウスの整数

  中学・高校で、 ・・・、−2、−1、0、1、2、・・・ を整数と言ってきたが、ここでは、有
理整数と言い換え、

      複素数 a+b・i   (a、b は有理整数 、i は虚数単位)

の形の数を、整数(ガウスの整数)と呼ぶことにする。

 この整数は、和・差・積の演算について閉じているが、商については閉じていない。

2つの整数 z 、w (w≠0)について、ある整数 α が存在して、

      z=α・w

が成り立つとき、 z は、w の倍数(w は、z の約数)または、z は w で割り切れるという。

例  0=0・w なので、0 は全ての整数の倍数である。
   (1+2・i)・(3+4・i)=−5+10・i なので、−5+10・i は、3+4・i の倍数

 複素数では、絶対値 a+b・i が大活躍するが、整数論では、

      N(a+b・i)=(a+b・i)・(a−b・i)=a2+b2

が用いられる。これを、整数 a+b・i のノルム(Norm)という。

 z=a+b・i の共役を、 =a−b・i で表せば、 N(z)=z・ =|z|2 なので、ノルム
は、絶対値とほぼ同じ概念といえる。

  ノルムN(z)は、0以上の整数で、  N(zw)=N(z)・N(w)

                        N(z/w)=N(z)/N(w)

 整数論で絶対値を用いない理由は、多分、根号が煩わしいからだろう。(個人的予想!)

根号を使わないので、

  整数 z のノルム N(z)は、整数 z の倍数

であることが分かる。

 このノルムを用いて、最大公約数、最小公倍数が定義される。

 最大公約数 ・・・・・ 公約数のうちで、ノルムが最大のもの

 最小公倍数 ・・・・・ 公倍数のうちで、ノルムが最小のもの

例 2 と 2i の最大公約数・最小公倍数を求めよ。

  2=(1+i)・(1−i) 、2i =(1+i)2 なので、
 最大公約数は、 1+i で、最小公倍数は、 (1+i)2・(1−i)=2+2・i

 ノルムと同様にして、シュプール(Spur)(または、トレース(trace))が定義される。

      S(z)=z+

  シュプールS(z)は、偶数で、  S(z+w)=S(z)+S(w)

例  z=3+2i のノルム N(z)=(3+2i)・(3−2i)=13
          シュプール S(z)=(3+2i)+(3−2i)=6

 有理整数では、「1」という数が重要であった。有理整数の群としては単位元であったし、
数直線では、数0と数1の間の長さを単位として、他の数の配置を求めたりもした。

 また、有理整数 1 は、全ての有理整数の約数という性質も持っていた。ここでは、この
性質に注目して、単数という概念が理解される。

   全ての整数の約数となる整数を、単数という。

 1=1+0・i も整数なので、明らかに、単数 ε は、1 の約数である。よって、ある整数 δ
が存在して、
         1=ε・δ
が成り立つ。
 よって、 N(ε・δ)=N(ε)・N(δ)=N(1)=1 より、 N(ε)=1
したがって、 ε=a+b・i とおくと、 a2+b2=1 なので、
       (a , b)=(1 , 0)、(−1 , 0)、(0 , 1)、(0 , −1)
以上から、ガウスの整数における単数は、

       1 、 −1 、 i 、 −i

の4個であることが分かる。

 これらは丁度、ガウス平面において、原点中心、半径 1 の円と各軸との交点である。

 有理整数では、素数という概念が重要であった。素因数分解により、有理整数の構造・
性質が明らかとなった。ガウスの整数においても、同様の議論が可能である。そのため
に、ガウスの整数における素数を定義しなければならない。

 整数 z に対して、単数 1、−1、i、−i および、z、−z、iz、−iz は、自明な約数で、有理
整数における、1と−1 と同様に因数としては、度外視して考えるものとする。

例 6=1・6 とは普通考えない。 6=2・3 と因数に分解する方が自然であろう。

 整数 z に対して、自明でない約数を、真の約数という。

 このとき、整数 z が、0でも単数でもなく、かつ、真の約数を持たないとき、素数であると
いう。

例 2 は素数でない。 実際に、2=(1+i)・(1−i) で、真の約数 1+i 、1−i を持つ。

 3 は素数である。 実際に、3 が素数でないとすると、真の約数 z 、w が存在して、
              3=z・w と書ける。このとき、N(3)=N(z)N(w) より、
              N(z)N(w)=9 である。N(z)、N(w)>1 なので、
              N(z)=N(w)=3 となる。ところが、この式を満たす整数 z は存在
              しない。もし、z=a+b・i (a、b は有理整数)が存在するとすると、
              a2+b2=3 とならなければならないが、それは不可能。
               なぜなら、 a2+b2≡3 (mod 4) において、左辺は、0,1,2
              の場合しかないので、矛盾である。
               よって、3 は素数である。

 有理整数の世界で素数であったものが、素数だったり、そうでなかったりと、ガウスの整
数の世界は、今までの有理整数の世界とは若干違うようである。そこがまた数学の面白さ
なのだろう。

 整数が素数かどうかを判断する公式として、次の定理が知られている。

定理  整数 z のノルム N(z) が素数ならば、整数 z は素数である。

(証) 整数 z が素数でないとすると、真の約数 α 、β が存在して、z=α・β と書ける。
   このとき、N(z)=N(α)N(β) が素数なので、N(α) または N(β) の何れかが 1 であ
   る。しかるに、α 、β は、真の約数なので、N(z)、N(w)>1 でなければならない。
   これは矛盾である。よって、整数 z は素数である。

(注) N(3)=9 が素数でないのに、3が素数であるように、上記の定理の逆は成立しない。

 ガウスの整数で、素数といわれるものをいくつか調べておこう。

例 1+i ・・・ N(1+i)=2 は素数より。

     1−i は、 1−i =(−i)・(1+i) により得られる。

  一般に、 単数 ε を用いて、 z=ε・w と書けるとき、z と w は同伴数であるという。
 整除の問題(割り切れる・割り切れない)において、整数を同伴数に置き換えても何ら影
響はないので、同伴数を同一の因数とみなしてもよい。
  したがって、 2=(1+i)・(1−i)=(−i)・(1+i)2 において、2 という数は、2つの方
 法で素因数分解できるように見えるが、この約束により、2 という数は、素数 1+i の2乗
 に素因数分解されることが分かる。

  a 、b>0 のとき、

 a−b・i =(−i)・(b+a・i) 、−a+b・i =i・(b+a・i) 、−a−b・i =(−1)・(a+b・i)

なので、以下では、 a+b・i (a 、b>0) の形の整数について調べることにする。

例 2+i ・・・ N(2+i)=5 は素数より。

例 3+2・i ・・・ N(3+2・i)=13 は素数より。

     3+i は素数でない。実際に、3+i =(1+i)・(2−i)より。

例 4+i ・・・ N(4+i)=17 は素数より。

     4+2・i は素数でない。実際に、4+2・i =2・(2+i)より。
     4+3・i は素数でない。実際に、4+3・i =(1+2・i)・(2−i)より。

例 5+2・i ・・・ N(5+2・i)=29 は素数より。

     5+i は素数でない。実際に、5+i =(1+i)・(3−2・i)より。
     5+3・i は素数でない。実際に、5+3・i =(1+i)・(4−i)より。

例 5+4・i ・・・ N(5+4・i)=41 は素数より。

 素数の分布の様子を図示すれば下図のようになる。(同色は、同伴数)

      

 (参考) 西山 豊 著 人とヒトデとサッカーボール (三省堂)の197頁に、この素数の
     分布の様子を表した図が掲載されている。上図では分かりにくいが、きれいな幾
     何学模様で、1988年ハンガリーで開催されたICME(国際数学教育研究会)で、
     イギリスのグループが素数の分布を表す模様のスカーフを展示したそうである。

 整数 z に対して、素数 α 、β 、・・・ があって、 z=α×β×・・・ と積の形にかけるとき、
整数 z は、素因数に分解されるという。

 ここで、
       素因数は有限個しかない。

     実際に、整数 N(α)、N(β)、・・・ は、1 より大きい整数で、N(z) は有限の値より
         明らか。

 今までの話から、整数 z がいくつかの素因数に必ず分解できるということは理解できるだ
ろう。しかし、素因数分解において、大切なことは、その分解の一意性にある。もし、一意性
が成立すれば、有理整数における性質が、ガウスの整数においても同様に成り立つことに
なる。

 一意性を証明するためには、いくつかの準備が必要となる。まずは、整除の定理から。

定理  任意の整数 z 、w (w≠0) に対して、

         z = w・α+β  ( N(β)<N(w) )

    を満たす整数 α 、β が存在する。


(証明) 任意の整数 z 、w (w≠0) に対して、複素数 ξ=z/w が定義される。

   ガウス平面(複素数平面)において、左図からも明らかなよう

  に、ある整数 α が存在して、 N(ξ−α)<1 とできる。

  そこで、 β=z−w・α とおくと、β は整数で、

   N(β)=N(z−w・α)
       =N(w・(ξ−α))
       =N(w)・N(ξ−α)
       <N(w)

  以上から、 z = w・α+β ( N(β)<N(w) ) を満たす整数 α 、β が存在する。(証終)

 この定理により、ガウスの整数においても、ユークリッドの互除法を行うことができる。

 任意の整数 z 、w (w≠0) に対して、 z = w・α+β  ( N(β)<N(w) )を満たす整数

α 、β が存在する。 もし、β = 0 なら、z は、w で割り切れる。

β ≠ 0 のとき、 w = β・γ’+γ  ( N(γ)<N(β) )を満たす整数 γ 、γ’ が存在する。

 このような操作を続けると、ノルムは、0 以上の整数なので、結局最後は、  δ = ε・ζ’

を満たす整数 ζ’ が存在する。(つまり、ζ=0 で最後は割り切れる!)

 このとき、ε は、整数 z 、w の公約数である。逆に、整数 z 、w の公約数は、ε の約数で

もあるので、ε は、整数 z 、w の最大公約数であるといえる。

 通常、最大公約数 ε は、整数 z 、w を用いて、 ε = ( z , w ) と書かれる。


 以上の話を整理すると、有理整数の場合と同様に、次の定理が成り立つ。

定理  任意の整数 z 、w (w≠0) に対して、 α・z + β・w = ( z , w )

    を満たす整数 α 、β が存在する。


(証明) ユークリッドの互除法から明らか。(証終)

例 2つの整数 7+4・i 、9+2・i の最大公約数を求めてみよう。

   9+2・i = (7+4・i)・1+2−2・i
   7+4・i = (2−2・i)・(1+3・i)−1
   2−2・i = (−1)・(−2+2・i)
   よって、最大公約数は、−1 である。

 このように、単数が最大公約数であるとき、2つの整数は、互いに素であるという。

例 2つの整数 3−i 、4−3・i の最大公約数を求めてみよう。

   4−3・i = (3−i)・1+1−2・i
   3−i = (1−2・i)・(1+i)
   よって、最大公約数は、1−2・i である。

  このとき、 1・[ 4−3・i ]+(−1)・[ 3−i ] = 1−2・i  が成り立つ。


 いよいよ、素因数分解の一意性を証明する準備ができたようだ。

補題  整数 z 、w が互いに素であるとき、

    z・α が w で割り切れれば、α は、w で割り切れる。


(証明) 整数 z 、w が互いに素なので、
     x・z + y・w = ε (ε は単数) となる整数 x 、y が存在する。
    このとき、 ε・α = x・z・α + y・w・α は、w で割り切れる。
    すなわち、 α は、w で割り切れる。 (証終)

定理  任意の整数 z は、一意に素因数分解される。

(証明) 整数 z が、2通りに素因数分解されるものと仮定する。
        z = α1×α2× ・・・=β1×β2× ・・・
    このとき、補題により、単数 ε1 、ε2 、・・・ として、
        α1×α2× ・・・ = (ε1×ε2×・・・)・(β1×β2× ・・・)
    と書ける。
     よって、2通りの素因数分解は、単数の差しかないので、一意であるとしてよい。
                                                  (証終)


 上記で、ガウスの整数における素数の例をいくつか挙げたが、一般に、素数は、どのよう
な形をしているのだろうか?これも、大いに興味のあるところである。

 以下で、ガウスの整数における素数と区別するために、有理整数における素数を、有理
素数
と呼ぶことにする。

 いま、整数 z を素数として、その性質を見ていこう。

 z で割り切れる正の有理整数のうちで最小のものを、p とする。このような p は必ず存在
する。(例えば、N(z)は、z で割り切れる。)

 このとき、 p は、有理素数である。

 実際に、 z は素数で単数ではないから、p > 1 で、p が有理素数でないとすると、

             p = α・β ( p>α>1 、p>β>1 )

       となる有理整数 α 、β が存在し、α または β は、z で割り切れる。

       これは、p の最小性に矛盾する。 よって、 p は、有理素数である。

 したがって、素数 z は、有理素数 p の約数となる。そこで、 p = z・γ とおける。

このとき、 N(p)=N(z)・N(γ) で、N(p)=p2 なので、

       N(z)=p  または  N(z)=p2

となる。 N(z)=p のとき、 z=a+b・i とおくと、 a2+b2=p より、 p=z・

     N(z)=p2 のとき、 N(γ)=1 で、γ は単数で、z は、p と同伴数となる。

       このとき、p は、ガウスの整数としても素数となり、N(z)=p のときのような p

      の分解は不可能である。

 以上から、

 素数 z=a+b・i と有理素数 p について、

  N(z)=p のとき、 p は素数でなく、 p=z=a2+b2 と分解される。
(→参考

  N(z)=p2 のとき、 p は素数で、a2+b2=p を満たす a 、b は存在しない。



 したがって、有理素数 p について、方程式 2+y2=p の解を吟味することにより、素
数が求められる。

例 p=2 のとき、 方程式 x2+y2 = 2 の解は、

     ( x , y )=( 1 , 1 )( 1 , −1 )( −1 , 1 )( −1 , −1 )

  よって、 p=2 は素数でなく、素数 z は、1+i 、1−i 、−1+i 、−1−i となる。

  このうち、1−i 、−1+i 、−1−i は、すべて 1+i の同伴数である。

   実際に、 1−i = (−i)・(1+i)、−1+i = i ・(1+i)、−1−i = (−1)・(1+i)


 方程式 x2+y2 = p (p≠2)の解があるとする。 p は、奇数なので、x または y のうち
一方は偶数、他方は奇数である。このとき、p は、4で割って、1余る数である。

 このことは、4で割って、3余る有理素数 p に対して、a2+b2=p を満たす a、b が存在
しないことを意味し、

     4で割って、3余る有理素数 p は、ガウスの整数としても素数

となる。

例 有理素数 3 は、素数である。(→ 参考

例 有理素数 7 は、素数である。

例 有理素数 11 は、素数である。


 p が、4で割って、1余る数のとき、方程式 x2+y2 = p は、どのような解を持つのだろう
か?(→ Legendre の記号、指数等について既に理解されている方は、こちらへジャンプ)

 ここで、整数論では大切な記号 Legendre の記号を復習しておこう。

例 方程式 X2≡1 (mod 3) は、X=3n±1 (n は整数)という形の解を持つが、
  方程式 X2≡2 (mod 3) は、決して解を持たない。

 一般に、p を2以外の素数として、

    方程式 X2≡a (mod p) が
                         解を持つとき、 a を p の平方剰余

                         解を持たないとき、a を p の平方非剰余

という。

例 3で割った余りは、0、1、2 であるが、その余りを平方したものを3で割った余りは、
  0、1 の場合しか起こらない。
   このとき、0 と 1 は、3 の平方剰余となり、2 は、3 の平方非剰余となる。

例 7で割った余りは、0、1、2、3、4、5、6 であるが、その余りを平方したものを7で割っ
  た余りは、0、1、2、4 の場合しか起こらない。
   このとき、0 と 1 と 2 と 4 は、7 の平方剰余となり、3 と 5 と 6 は、7 の平方非剰余
  となる。

   02≡0 (mod 7) 、12≡62≡1 (mod 7) 、32≡42≡2 (mod 7)、

   22≡52≡4 (mod 7)


 a が、p で割り切れないとき、a が平方剰余であるか、平方非剰余であるかを次のような
記号を使って表す。

平方剰余のときは、 =1 平方非剰余のときは、 =−1

 この記号を、Legendre の記号という。

 紙面の都合上、以下では、Legendre の記号を、(a/p) で表すことにする。

例  (1/3)=1 、 (2/3)=−1


 GAI さんからのコメントです。(平成24年3月8日付け)

 平方剰余の法則と言って、なにやら直感では何を言おうとしているのか掴み難い式で表現
されているのを見ることがあり、よく分からないと言うのが実感です。ある本で、この法則を次
のような表現で解説してある文章があったので、メモしていました。このことと、なにか関係が
ありますか?

表現: pとqが奇素数で、どちらでも 4k-1 という形でなければ、q≡y2 (mod p) が解を持
    つときに限って、方程式 p≡x2 (mod p) は解を持つ。
    また、pとqのどちらかが、4k-1という形であれば、どちらか一方の方程式は解を持ち、
    もう一方の方程式は解を持たない。

 これでもややこしい解説ではあるのですが、ただ数式で書いてあるよりはイメージが取り易
い気はします。平方剰余の解釈として、これでいいのでしょうか?


 空舟さんからのコメントです。(平成24年3月8日付け)

 まさにそれです。個人的には「平方剰余の相互法則」のバニラとチョコレートの解説がすご
く具体的だと思います。

 ただし、その表現だとちょっと違いますね。どちらかがバニラ4N+1型のとき、解を持つかど
うか一致、両方がチョコレート4N+3型の時、不一致 です。


 さて、指数という概念を理解するために、フェルマーの定理を確認しておく。

フェルマーの定理  p が有理素数で、a が p とは互いに素な自然数とするとき、

                   p−1 ≡ 1 (mod p)

(証明) 2項定理より、 (m+n)≡m+n (mod p) は明らかであろう。

   これを一般化して、 (m+・・・+n)≡m+・・・+n (mod p) が成り立つ。

   m=・・・=n=1 (a 個)とすれば、 a≡a (mod p) である。

   ここで、 a は p とは互いに素な自然数なので、 ap−1≡1 (mod p) (証終)


   (追記) 平成22年3月22日付け

      2010年度入試の大阪大学 後期 理系 で、上記のフェルマーの定理の証明を
     問う問題が出題された。

      p は素数、r は正の整数とする。以下の問いに答えよ。

     (1) x1、x2、・・・、x についての式 (x1+x2+・・・+x を展開したときの単項

       式 x1122・・・x の係数を求めよ。ここで、p1、p2、・・・、p は、0または

       正の整数で、p1+p2+・・・+p=p を満たすとする。

     (2) x1、x2、・・・、x が正の整数のとき、

          (x1+x2+・・・+x−(x1+x2+・・・+x

       は、p で割り切れることを示せ。

     (3) r は、p で割り切れないとする。このとき、 rp-1−1 は、p で割り切れること

       を示せ。


    (コメント) (1)(2)については、多項定理から明らかだろう。上記の証明に倣う形で
          小問(1)(2)が配置されている。したがって、(3)については、上記の証明
          と同様に、 x1=x2=・・・=x=1 とすればよい。


 フェルマーの定理より、方程式 a≡1 (mod p)を満たす自然数解が存在するので、

そのうちの最小の自然数解を、e とすると、 p−1 は、e で割り切れる。

 さらに、e の最小性から、 a0 、a1 、a2 、・・・、ae−1 は、p を法として合同にはなり
えない。

 特に、e=p−1 のとき、 a を p を法としての原始根(または、p の原始根)という。


例 p=7 のとき、 1 に対する e = 1 、2 に対する e = 3 、3 に対する e = 6 、

             4 に対する e = 3 、5 に対する e = 6 、6 に対する e = 2

  以上から、7の原始根は、2個あり、 3 と 5 である。


 ここで、自然数 1、2、3、・・・、n の中で、n と互いに素な数の個数は、φ(n)で表される。

この関数を、オイラーの関数という。

例 φ(1)=1、φ(2)=1、φ(3)=2、φ(4)=2、φ(5)=4、φ(6)=2、φ(7)=6

 オイラーの関数について、次の性質が成り立つ。

  (1) 有理素数 p に対して、 φ(p)=p−1  特に、φ(p)=p−pn−1

  (2) a と b が互いに素ならば、 φ(ab)=φ(a)φ(b)

 (証明) (1)は、明らかであろう。

     (2)は、次のように示される。

      a より小さい数で、a と互いに素な数は、φ(a)個あり、その一つを、α とおく。

     このとき、 b 個の数 α、α+a、α+2a、・・・、α+(b−1)a を考える。

     これらは、何れも b を法として合同でない。

     したがって、 ab と互いに素な数は全部で、φ(a)×φ(b)個あるので、

             φ(ab)=φ(a)φ(b)

     が成り立つ。(証終)

例 φ(2)=2−1=1 、φ(3)=3−1=2 、φ(4)=φ(22)=4−2=2、
  φ(6)=φ(2)φ(3)=1×2=2


 オイラーの関数 φ(n) を用いると、上記で述べたことは、次のようにも言い換えることが
できる。

 p が有理素数で、a が p とは互いに素な自然数とするとき、

        aφ(p) ≡ 1 (mod p)

この合同式を満たすφ(n)が最小のものであるとき、a を、p の原始根という。

 もし、原始根が存在すれば、それは、φ(p−1)個存在する。

原始根の一つを、g (g≠1)とすれば、

      1、g、g2、g3、・・・、gp−2

は、互いに合同でない p−1 個の数で、いずれも p では割り切れない。



 いま、a を p とは互いに素な任意の自然数とするとき、上記のことから、

       g ≡ a (mod p)

となる e (0≦ e <p−1 )がただ一つ存在する。このとき、

       e = ind(a)

で表し、原始根 g を底とする a の指数(index)という。

(注) g≡ a (mod p)、g ≡ a (mod p)ならば、ge−f ≡ 1 (mod p)

   よって、e−f  は、p−1で割り切れるので、 e ≡ f (mod p−1)

   したがって、上記では、0≦ e <p−1 と限定したが、p−1 を法として考えれば、

  a の指数は、一定であるといえる。

   故に、
        a ≡ b (mod p) ⇔ ind(a) ≡ ind(b) (mod p−1)

  が成り立つ。

例 7 の原始根の一つ 3 について、3 を底とする指数表を作ってみよう。

  30 ≡ 1 (mod 7)、31 ≡ 3 (mod 7)、32 ≡ 2 (mod 7)、

  33 ≡ 6 (mod 7)、34 ≡ 4 (mod 7)、35 ≡ 5 (mod 7)

 以上から、

指数

 また、上記指数表を眺めていると、

  a の値における「 2 かける 3 = 6 」が、指数では、「 2+1 = 6」が対応し、

  a の値における「 4 かける 5 = 20 」が、指数では、「 4+5 ≡ 3(mod 6)」が対応

していることが分かる。

 このことから、指数には、対数に似た性質があることに気づかされる。すなわち、

    p−1 を法として、  ind(a×b) ≡ ind(a) + ind(b)

                  ind(a) ≡ n×ind(a)

 証明は、明らかであろう。

 上記の指数表を用いて、いろいろ計算してみよう。

 (1) 指数計算・・・・・ 20 ≡ 6 (mod 7) なので、
               ind3(20) ≡ ind3(6) = 3 (mod 6)

 (2) 指数方程式・・・・・ ind3(X)≡ 2 (mod 6) とすれば、上記表より、
               ind3(X) ≡ ind3(2) (mod 6)
               よって、 X ≡ 2 (mod 7)

 (3) 1次方程式・・・・・・ 4X ≡ 3 (mod 7) において、
               ind3(4X) ≡ ind3(3) (mod 6) より、
               ind3(4) + ind3(X) ≡ ind3(3) (mod 6)
               よって、 4 + ind3(X) ≡ 1 (mod 6) なので、
                ind3(X) ≡ −3 ≡ 3 (mod 6)
               したがって、 X ≡ 6 (mod 7)

 (4) 方程式・・・・・・ X3 ≡ 4 (mod 7)において、ind3(X3) ≡ ind3(4) (mod 6)
              よって、 3×ind3(X) ≡ 4 (mod 6)
              上式を満たす ind3(X) の値はないので、解なし。

 上記の(4)に関連して、次の定理が知られている。

定理A  p は有理素数とし、a は p で割り切れないものとする。

  X ≡ a (mod p) が解を持つための必要十分条件は、

    (n ,p−1)=d として、 ind(a) ≡ 0 (mod d)


(証明) ind(X) ≡ ind(a) (mod p−1) より、

     n × ind(X) ≡ ind(a) (mod p−1)

     この式を言い換えれば、解 ind(X) が存在するためには、不定方程式

       n × M + (p−1) × N = ind(a)

     を満たす整数 M(= ind(X))、N が存在することが必要十分である。

     そのためには、互除法の理論により、 n と p−1 の最大公約数 d により

      ind(a) が割り切れることが必要十分である。 

      よって、ind(a) ≡ 0 (mod d) でなければならない。(証終)

(コメント: 上記の定理に照らせば、(4)では、ind3(4) = 4 で、(3 ,6)=3 から
       ind3(4) ≡ 0 (mod 3)が成り立たないので、解は存在し得ないことが分か
       る。・・・空舟さんより誤りの指摘を受け、修正済み(H24.2.29)

 (5) 2次方程式・・・・・ 2X2−3X+5 ≡ 0 (mod 7)において、両辺を4倍して、
                8X2−12X+20 ≡ 0 (mod 7) すなわち、
                   X2+2X−1 ≡ 0 (mod 7) となる。
                このとき、 (X+1)2 ≡ 2 (mod 7)
                ここで、 (2 ,6)=2 で、ind3(2) ≡ 0 (mod 2)なので、
                解が存在する。
                  ind3((X+1)2) ≡ ind3(2) (mod 6) より、
                 2・ind3(X+1) ≡ 2 (mod 6)
                上式を満たす ind3(X+1) の値は、
                    ind3(X+1) ≡ 1 、4 (mod 6)
              したがって、 X+1 ≡ 3 、4 (mod 7) すなわち、
                    X ≡ 2 、3 (mod 7)

 (6) 累乗計算・・・・・ X ≡ 3100 (mod 7)において、
               ind3(X) ≡ ind3(3100
                     ≡ 100×ind3(3) ≡ 100 ≡ 4 (mod 6)
                よって、 X ≡ 4 (mod 7)

 (7) 指数方程式・・・・・ 4 ≡ 3 (mod 7)において、
                 ind3(4) ≡ ind3(3) (mod 6) すなわち、
                    X・ind3(4) ≡ ind3(3) (mod 6) より、
                       4・X ≡ 1 (mod 6)
                 ところが、(4 ,6)=2 で、1を割れないから、この方程式、す
                 なわち元の方程式には解は存在しない。

                 4 ≡ 1 (mod 7)において、
                 ind3(4) ≡ ind3(1) (mod 6) すなわち、
                    X・ind3(4) ≡ ind3(1) (mod 6) より、
                       4・X ≡ 0 (mod 6)
                 よって、 X ≡ 3 (mod 6)

                (この2つの例からも分かるように、指数方程式は解を持つ場合
                 と持たない場合があるので要注意である。)

 指数に関して、次の事実が知られている。

定理   有理素数 p は、p≠2 とする。このとき、任意の原始根 g に対して、

         ind(−1) ≡ (p−1)/2 (mod p−1)


(証明) 原始根 g の定義より、 gp−1 ≡ 1 (mod p) が成り立つ。このとき、

       gp−1−1 ≡ (g(p−1)/2−1)(g(p−1)/2+1) ≡ 0 (mod p) において、

     g(p−1)/2−1 ≡ 0 (mod p)とはなり得ないので、

        g(p−1)/2+1 ≡ 0 (mod p) より、 g(p−1)/2 ≡ −1 (mod p)

     したがって、 ind(−1) ≡ (p−1)/2 (mod p−1) が成り立つ。(証終)

例 指数表で、ind3(6) ≡ 3 (mod 6) であるが、6 ≡ −1 (mod 7)なので、
  確かに、 ind3(−1) ≡ (7−1)/2 (mod 6) が成り立っている。

 この定理を用いると、次の定理が得られる。

定理(ウィルソン)  有理素数 p に対して、 (p−1)!≡ −1 (mod p)

(証明) p=2 のときは、明らかに成り立つので、以下では、p>2 とする。

      原始根 g を用いて、(p−1)! ≡ g0+1+2+・・・+(p-2) ≡ g(p-2)(p-1)/2 (mod p)

     と書ける。上記の定理より、 g(p−1)/2 ≡ −1 (mod p) なので、p>2 より、

           (p−1)! ≡ (−1)(p-2)≡ (−1)p≡ −1 (mod p)  (証終)

 単に、この定理を証明するだけだったら、次のようにした方が分かりやすいだろう。
                    (平成18年12月29日付け 加俊さんに質問されて見直しました!

(別証) 素数 p が 2 の場合は、明らかに成り立つ。

    奇素数 p に対して、フェルマーの定理より、1≦k≦p−1となる任意の整数 k に対

   して、 kp−1≡1 (mod p) が成り立つ。

    したがって、多項式F(X)=Xp−1−1 において、

        F(1)≡0 、 F(2)≡0 、・・・、 F(p−1)≡0  (mod p)

   よって、

        F(X)≡(X−1)(X−2)・・・(X−p+1)  (mod p) と因数分解される。

   そこで、X=0 を代入すると、  (−1)p−1・(p−1)!≡−1 (mod p)

    p は奇数なので、  (−1)p−1=1

     よって、(p−1)!≡−1 (mod p) が成り立つ。 (別証終)


(コメント) ウィルソンの定理は逆も成り立つ。 すなわち、

        (p−1)! ≡ −1  (mod p) ならば、 p は有理素数

(証明) p が有理素数でないとすると、2つの自然数 m 、n (2 ≦ m 、n < p)を用いて、

    p = mn と書ける。このとき、m は(p−1)! の約数で、(p−1)! +1 の約数に

    はなり得ないので、p は、(p−1)! +1 の約数になり得ない。

     これは、条件に矛盾する。 よって、p は素数でなければならない。 (証終)

例 p=7 のとき、 (p−1)!=6!=720 =103×7−1 ≡ −1 (mod 7)


定理(ライプニッツ)  有理素数 p に対して、 (p−2)!≡ 1 (mod p)

(証明) ウィルソンの定理より、

    (p−1)! ≡ (p−1)(p−2)!≡−(p−2)!≡−1  (mod p)

   なので、 (p−2)!≡ 1  (mod p) が成り立つ。 (証終)

 先の定理A において、合同式が解を持つための条件を提示したが、原始根を用いてい
る点が気持ちが悪い。

 定理Aは、次のように言い換えることが出来る。

定理B p は有理素数とし、a は p で割り切れないものとする。

  X ≡ a (mod p) が解を持つための必要十分条件は、

    (n ,p−1)=d、(p−1)/d=f として、 a ≡ 1 (mod p)


(証明) 定理A より、 解を持つための必要十分条件は、ind(a) ≡ 0 (mod d)

     よって、 ind(a) =dk (k は自然数) と書ける。 このとき、定義より、

        gdk ≡ a (mod p) となる。

     ここで、両辺を f 乗すれば、 a ≡ g(p-1)k ≡ 1 (mod p)

     逆に、a ≡ 1 (mod p)が成り立つとすると、原始根を g として、

         ind(a) ≡ ind(1) (mod p−1)

      すなわち、  f ×ind(a) ≡ 0 (mod p−1)

     ここで、 (n ,p−1)=d なので、 p−1=dh とおくと、

             h×ind(a) ≡ 0 (mod dh)

      よって、   ind(a) ≡ 0 (mod d) が得られる。 (証終)


    方程式 X≡a (mod p) が
                         解を持つとき、 a を p の n 巾剰余

                         解を持たないとき、a を p の n 巾非剰余

という。 特に、n=2 のとき、平方剰余または平方非剰余といわれる。
           (あっ!、やっと、これで前に述べた Legendre の記号 と話がつながった!)

以上の話をまとめると、方程式 X≡a (mod p) 、(n ,p−1)=d において、

 a が p で割り切れないとき、

   d=1 ならば、 a は必ず、n 巾剰余

   d>1 ならば、 ind(a) が d で割り切れる a は、n 巾剰余で、その個数は、

       (p−1)/d 個ある。

 素数 p と互いに素な自然数の個数は、オイラーの関数 φ(n) で表されるが、上記の
事実は、
       φ(n) 個のうち丁度 1/d が、n 巾剰余になる

ことを示している。特に、n=2 のときは、d=2 なので、丁度半分ということになる。


 空舟さんからのコメントです。(平成24年2月29日付け)

 素数pに対する原始根を求めるのは、私の認識では、適当な数aをとって、a、a2、・・・を計
算してみて、もし原始根でなければ、そこに現れない他の数bで試して・・・という風にしらみつ
ぶしするしかないと認識しています。

 砧文夫『初等代数学』(1993)によると、原始根を具体的に求める一般的な方法はないとの
ことで、ただ、1つさえ見つかれば、それを s として、p-1 と素な数qに対して、sq も原始根と
いう風に残りは得られます。


 空舟さんからのコメントです。(平成24年2月29日付け)

 「適当な数aをとって、a、a2、・・・を計算してみて・・・」と書きましたが、法997では、位数は
996の約数になるので、aが、997の原始根であることを確かめるには、996=2・2・3・83 に注
意して、a498≠1、a332≠1、a12≠1 かどうかを調べれば十分。a249≠±1、a166≠±1、
6≠±1でも良い。

 具体的な計算としては、a6、a83を計算して、それらに±1があれば終了。(a83)2、(a83)3
計算して、それらも±1でなければ、aは原始根。という風にすればだいぶ労力は減るでしょ
う。

 せっかくなので、違う数 2・2・3・41+1=493 の原始根を考えてみます。493は実は素数で
はないことが判明し、17・29 ということは、493は原始根を持たないので、考察終わり。


 さて、話を、もとの Legendre の記号 (a/p) に戻そう。

 有理素数 p (p≠2)と、p で割り切れない整数 a において、上記の事実から、

=(−1)ind(a)

が成り立つ。

例 p=7 のとき、

指数

なので、

(1/7)=1 、(2/7)=1 、(3/7)=−1 、(4/7)=1 、(5/7)=−1 、(6/7)=−1

より、 1 、2 、4 が平方剰余、 3 、5 、7 が平方非剰余である。

 または、上記の公式を用いないで、

    12≡1 (mod 7) 、 32≡2 (mod 7) 、 52≡4 (mod 7)

からも分かる。

 Legendre の記号 (a/p) の性質

(1) a ≡ b (mod p) ならば、 (a/p)≡(b/p)

   (証明)  a ≡ b (mod p) ⇔ ind(a) ≡ ind(b) (mod p−1) と

= (−1)ind(a)

       の2つの事実から明らかであろう。(証終)

(2) (abc・・・/p)=(a/p)(b/p)(c/p)・・・

   (証明)  ind(a×b) ≡ ind(a) + ind(b) (mod p−1) と

= (−1)ind(a)

       の2つの事実から明らかであろう。(証終)

定理(Euler の規準)

≡ a(p-1)/2   (mod p)

(証明) 上記で示した定理Bにより、X2 ≡ a (mod p) が解を持つための必要十分条
    件は、
             a(p - 1)/2 ≡ 1 (mod p)
    なので、
           (a/p)=1  ならば、  a(p - 1)/2 ≡ 1 (mod p)

     また、  (a/p)=−1  ならば、  ap - 1 ≡ 1 (mod p) において、

    a(p - 1)/2 −1 は、p で割り切れないので、a(p - 1)/2 +1 が、p で割り切れる。

    すなわち、 (a/p)=−1  ならば、  a(p - 1)/2 ≡ −1 (mod p)

     以上から、定理が成り立つ。(証終)

例  前述の例で、

(1/7)=1 、(2/7)=1 、(3/7)=−1 、(4/7)=1 、(5/7)=−1 、(6/7)=−1

であることを、指数表を活用して求めたが、上記の定理によれば、次のようにしても求める
ことが出来る。

   13 ≡ 1 (mod 7)、 23 ≡ 1 (mod 7)、 33 ≡ −1 (mod 7)

   43 ≡ 1 (mod 7)、 53 ≡ −1 (mod 7)、 63 ≡ −1 (mod 7)

(コメント) 7 で割った余りは、0、1、2、3、4、5、6 で、その平方を7で割った余りは、そ
      れぞれ 0、1、4、2、2、4、1 となるので、0、1、2、4 の場合のみが平方剰余
      となる。指数というものを用いて、(a/p)を考えてきたが、何やら遠回りをしている
      ような...?多分もっと素晴らしい応用があるのだろう。それを信じて先に進もう!

 さて、当面の問題:

 有理素数 p が、4で割って1余る数のとき、方程式 x2+y2 = p は、どのような解を持つ
のか?


に、ここで話を戻そう。

例 4で割って1余る有理素数 p としては、p=5、13、17、29、37、41、53、・・・

  これらに対しては、

      5=12+22 、13=22+32 、17=12+42 、29=22+52 、37=12+62

     41=42+52 、53=22+72 、・・・

 などと表され、取りあえずは解をもつことが予想される。

 実は、次の定理が成り立つ。

定理(フェルマー・オイラーの素数定理)

  有理素数 p が、4で割って1余る数のとき、方程式 x2+y2 = p は、有理整数
 解を必ず持つ。


(この事実を初めて発見したのはフェルマー(1660年)だが、証明はオイラーが初めて(?)
 与えたらしい。)

 この定理から、4で割って1余る有理素数は、ガウスの整数としては、合成数となる。

(証明) Euler の規準から、 (−1/p)= (−1)(p-1)/2

    ここで、p は4で割って1余る数なので、 (p−1)/2 は偶数。

    よって、  (−1/p)=1  となり、 −1 は p の平方剰余となる。

    したがって、 方程式 X2≡−1 (mod p) は有理整数解を持つ。

    このとき、 X2+1=( X+ i )( X− i ) は、p で割り切れる。( i は、虚数単位)

    ここで、 X− i と p の最大公約数を ε とおくと、ε は、p の約数なので、

         ε = 1  または  ε = p  または  ε = z  (ただし、p=z・

    の何れかが成り立つ。

     ε = 1 のとき、

        X+ i 、 X− i ともに p と互いに素、すなわち、X2+1 は p と互いに素

       これは、X2+1 が、p で割り切れることに矛盾。

     ε = p のとき、X− i が p で割り切れることになり、矛盾。

    したがって、 ε = z = a+b・i で、このとき、p=z・ でなければならない。

    ここで、p≠0 なので、 a≠±b より、 z と は互いに同伴数にはなり得ない。

    以上から、

      4で割って1余る有理素数は、ガウスの整数として、2つの異なる互いに共役な
     素数の積として表される。
                                                 (証終)

 上記証明で用いられた事実をさらに深めて、整数論の基本定理(平方剰余の相互法則)
が得られる。

定理
    (1) 平方剰余の相互法則
                       

    (2) 第一補充法則
                       

    (3) 第二補充法則
                       

 この相互法則の最初の完全なる証明は、Gauss によるといわれる。



  以下、工事中