副豆
前の記事では\(x^2+y^2 \) の形に表せる素数は必ず4n+1型であることを知りました。
実は逆が成り立ちます。つまり4n+1型の素数は必ず \(x^2+y^2 \) の形に表すことができます。フェルマーはこの事実を彼の得意な無限降下法と呼ばれる技法を使って証明しました。無限降下法は数学的帰納法とよく似ていますが向きが逆になります。
はじめての数論 原著第3版―発見と証明の大航海‐ピタゴラスの定理から楕円曲線まで
- 作者:ジョセフ・H. シルヴァーマン
- 出版社/メーカー: ピアソンエデュケーション
- 発売日: 2007/04
- メディア: 単行本
の第２５章、第２６章を参考にしました。
証明は２段階に分かれます。
第一段階：4n+1型の素数pの適当な倍数mpが \( x^2+1 \)の形に書けることを示します。つまり \( m\,p=x^2+1 \)、あるいは \( x^2+1 \equiv 0 mod p \) .
第２段階：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を選び直しからやり直します。一発で見つかる可能性は５割あります。
以下、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 $$
