人気ブログランキング | 話題のタグを見る
ペル方程式を解く
春らしい陽気の連休は、ペル方程式を解くに限る。
ペル方程式は、ディオファントス方程式のひとつで、不定方程式である。
求めたのは、

  X^2 - 1141*Y^2 = 1 を満たす自然数 X,Y

結果を先に書くと、
最小解は、
X=1036782394157223963237125215
Y=30693385322765657197397208 

2番目に小さい解は、
X=2149835465668770620046057429573836642230564915177592449
Y=63644723039454352911420468435537730368888828774799440

3番目に小さい解は、
X=4457823122280356933416781142655978994728046537252754363537864855269973556065877855
Y=131971456656637832121231141123756847385482339109584803556899725319840790386361992

こんな計算をしたのは、読んでいた本に思わせぶりな一節があったから。
「X^2 - 1141*Y^2 = 1 を満たす自然数は無数に存在するが、
 その値は大きく、最も小さい解でも Y の値は26桁になる」と。
そこまで書いておきながら、肝心の解答が記載されていない。
気になるではないか。

そこで、計算してみた。
手間はかかるが、解法は難しくない。
1141の平方根を求め、それを連分数展開すればよい。
それだけである。

例によって貰いものの計算ソフトを使い、C言語もどきのプログラムを作成した。

まず、1141の平方根を小数点以下2000桁くらいまで求めた。
そこまでやる必要はないとは思うが、
連分数展開したときの循環節がどれくらいの大きさになるかわからなかったので、
景気よく2000桁くらい算出しておけば後悔しないだろう、と。
ニュートン法で近似した。

続いて、求めた小数を暫定的な分数になおす。
たとえば、
1141の平方根が
33.7786915081090729925734828301610697335153052076004076912373 であれば、
分子を
337786915081090729925734828301610697335153052076004076912373
分母を
10000000000000000000000000000000000000000000000000000000000 とする。
実際に計算で使った値は、分子が2002桁、分母は2001桁(1のあとに0が2000個)。

この暫定的な分数を、ユークリッドの互除法で連分数展開すればよい。
1000回くらい割り算をした結果を眺めたら、循環節は58だった。

[33,1,3,1,1,12,1,21,1,1,2,5,4,3,7,5,16,1,2,3,1,1,1,2,1,2,1,4,1,8,
 1,4,1,2,1,2,1,1,1,3,2,1,16,5,7,3,4,5,2,1,1,21,1,12,1,1,3,1,66] である。

最後からふたつ目までを連分数で表現すると、
33+(1/(1+(1/(3+(1/(1+(1/(1+(1/(12+(1/(1+(1/(21+(1/(1+(1/(1+(1/(2+(1/(5+
(1/(4+(1/(3+(1/(7+(1/(5+(1/(16+(1/(1+(1/(2+(1/(3+(1/(1+(1/(1+(1/(1+(1/(2+
(1/(1+(1/(2+(1/(1+(1/(4+(1/(1+(1/(8+(1/(1+(1/(4+(1/(1+(1/(2+(1/(1+(1/(2+
(1/(1+(1/(1+(1/(1+(1/(3+(1/(2+(1/(1+(1/(16+(1/(5+(1/(7+(1/(3+(1/(4+(1/(5+
(1/(2+(1/(1+(1/(1+(1/(21+(1/(1+(1/(12+(1/(1+(1/(1+(1/(3+1・・・これに続く右カッコ112個は省略

見た目に訴えるなら連分数は次のとおり。(画像をクリックすると拡大表示)
ペル方程式を解く_c0069055_23242760.jpg

これを計算すると、
分子が 1036782394157223963237125215 (これが X の最小値)
分母が 30693385322765657197397208 (これが Y の最小値)

求めた数値を X^2 - 1141*Y^2 に代入して検算すると、
1036782394157223963237125215^2 - 1141×30693385322765657197397208^2 = 1

最小解 (x, y) が判明すれば、その他の解は次々と計算できる。
(X, Y) = (2x^2 - 1, 2xy)





by hikihitomai | 2010-05-02 18:10
<< 今日の仔猫 今日の仔猫  生後4週間 >>