ペル方程式

PE 数学 プログラミング

ペル方程式（Pell's equation）は、フェルマーが問題を数学者たちに送りつけたという逸話が有名ですが、オイラーも研究してこのように（誤って）命名したそうです。

x2 - Dy2 = 1
Dは与えられた平方数でない自然数

この形の整数解を求める問題をペル方程式と呼びます。Project Eulerではしばしばこれに帰着される問題が出題されるので、覚えておかないといけません。


x1, y1を、

x12 - Dy12 = 1

を満たす最小の自然数解とすると、

(x1 - √Dy1)n

を展開したものを

xn - √Dyn

とすると、(xn, yn) はペル方程式の解になります。なぜなら、

xn2 - Dyn2
= (xn - √Dyn)(xn + √Dyn)
= (x1 - √Dy1)n(x1 + √Dy1)n
= (x12 - Dy12)n
= 1

となるからです。また、これで全ての解を出すことができます。例えば、D = 2 とすると最小の解は (3, 2) なので、全ての解は

(xn, yn) = (3 - 2√2)n

となります。漸化式にすると、

xn+1 = 3xn + 4yn
yn+1 = 2xn + 3yn

次は最初の10組の解を出力するコードです。



from itertools import islice
def gen_Pell_solutions():

    x, y = 3, 2

    while True:

        yield x, y

        x, y = 3 * x + 4 * y, 2 * x + 3 * y
for x, y in islice(gen_Pell_solutions(), 10):

    print x, y

最小の解は非常に大きくなることがあるのですが、これについては別記事を参照してください。

x2 - Dy2 = -1

この形は拡張ペル方程式とも呼ばれます。
例えば、D = 2 のとき、(1, 1) が解になりますが、

xn + √2yn = (1 - √2)n

とすると、

xn2 - 2yn2 = (xn - √2yn)(xn + √2yn) = (1 - √2)n(1 + √2)n = (-1)n

だから、nが奇数のときに解になります。この方程式には必ずしも解はありません。例えば、D = 3 のときは解がありません。


また、

x2 - Dy2 = ±4

も同様に拡張ペル方程式と呼ばれます。

(xn + √Dyn) / 2

について同様の考察ができるからです。これは上をn乗すると分母が必ず2以下になるためです。定数項がほかではこうはなりません。


Project Eulerに必要な用語集
http://d.hatena.ne.jp/inamori/20091225/p1