読者です 読者をやめる 読者になる 読者になる

Maxima で綴る数学の旅

紙と鉛筆の代わりに、数式処理システムMaxima / Macsyma を使って、数学を楽しみましょう

2次形式で表される素数 と 節分 と

数学

f:id:jurupapa:20130203182737j:plain

副豆

にほんブログ村 科学ブログ 数学へ
にほんブログ村

前の記事では\(x^2+y^2 \) の形に表せる素数は必ず4n+1型であることを知りました。

実は逆が成り立ちます。つまり4n+1型の素数は必ず \(x^2+y^2 \) の形に表すことができます。フェルマーはこの事実を彼の得意な無限降下法と呼ばれる技法を使って証明しました。無限降下法は数学的帰納法とよく似ていますが向きが逆になります。

はじめての数論 原著第3版―発見と証明の大航海‐ピタゴラスの定理から楕円曲線まで

はじめての数論 原著第3版―発見と証明の大航海‐ピタゴラスの定理から楕円曲線まで

  • 作者: ジョセフ・H.シルヴァーマン,Joseph H. Silverman,鈴木治郎
  • 出版社/メーカー: ピアソンエデュケーション
  • 発売日: 2007/04
  • メディア: 単行本
  • 購入: 9人 クリック: 92回
  • この商品を含むブログ (17件) を見る

の第25章、第26章を参考にしました。

証明は2段階に分かれます。

第一段階:4n+1型の素数pの適当な倍数mpが \( x^2+1 \)の形に書けることを示します。つまり \( m\,p=x^2+1 \)、あるいは \( x^2+1 \equiv 0 mod p \) .

第2段階:pがあるx,y,mについて \( x^2+y^2= m\,p \) のときmより小さいm'について \( x' ^2+y' ^2= m' \,p \) となるx', y'が存在する。
mpが正であることに気をつけると、このようにmを減少させることでいつかはm'=1とできることが分かります。

 

ではまず第一段階です。4n+1型の素数pが与えられた時に\( m\,p=x^2+1 \) を満たすようなxとmを具体的に求めれば良い訳です。以下の関数f(p)はその計算を実行します。

(%i1) f(p):= block([a,x,m],

                         a:random(p),

                         x:power_mod(a,(p-1)/4,p),

                         m:(x^2+1)/p,

                         if mod(x^2,p)=p-1 then [x,m] else f(p));

このプログラムは確率的です。aを適当に選んでxとmを作ります。これが条件を満たしているかチェックします。満たしていれば[x,m]を返しますが、満たしていなければ(末尾再帰によるループで)aを選び直しからやり直します。一発で見つかる可能性は5割あります。

以下、p=13, p=61でf(p)を計算してみて、求まったx, mが条件を満たしていることを確認してみました。

(%i2) p:13;

$$ \tag{%o2} 13 $$

(%i3) [x,m]:f(p);

$$ \tag{%o3} \left[ 8 , 5 \right]  $$

(%i4) 'x^2+1=x^2+1;

$$ \tag{%o4} x^2+1=65 $$

(%i5) 'm*p=m*p;

$$ \tag{%o5} 13\,m=65 $$

(%i6) p:61;

$$ \tag{%o6} 61 $$

(%i7) [x,m]:f(p);

$$ \tag{%o7} \left[ 11 , 2 \right]  $$

(%i8) 'x^2+1=x^2+1;

$$ \tag{%o8} x^2+1=122 $$

(%i9) 'm*p=m*p;

$$ \tag{%o9} 61\,m=122 $$

 

This is a test.
天気