tsujimotterのノートブック

日曜数学者 tsujimotter の「趣味で数学」実践ノート

ペル方程式の連分数を用いた魔法の解法

数学 整数論 シリーズ：連分数とペル方程式 連分数

今回の記事は「シリーズ：連分数とペル方程式」の２日目の記事となっています。関連する記事は こちら からご覧いただけます。

今日はこんな問題を考えてみましょう。

兵士たちが正方形に並んでいる。これを1軍団とする。その軍団が「61」ある。これに王様が一人加わって、大きな正方形に並び直した。王様を含め、全体で何人になるか？

この問題は「コマネチ大学数学科」というテレビ番組で出題された問題の「改題 *1」となります。


自分で考えたいという方は、ここでストップしてぜひ一度考えてみてください。

ただし一点注意したいのですが、この問題は見かけ以上に いじわる な問題となっています。それでもよければ、という条件付きで挑戦してみてください。


「もういいや」「解説が知りたい」と言う方は、ぜひスクロールして以下の解説をみてください！



↓　↓　↓

↓　↓　↓

↓　↓　↓

↓　↓　↓

↓　↓　↓

それではいきましょう！

ペル方程式に帰着

まずは、元の問題を整理したいと思います。

求めたい全体の人数（王様含む）を N とします。このとき「大きな正方形に並び直した」という条件から、 N が平方数であることがわかります。そこで、ある正の整数 x が存在して N = x^2 と表せます。

また「兵士たちが正方形に並んでいる。これを1軍団とする。」から、1軍団の人数を y^2 とします。これが 61 個あり、 1 を足すと N に一致するということでした。そこで

x^2 = 61y^2 + 1

が成り立つということですね。

61y^2 を移項すると

x^2 - 61 y^2 = 1 \tag{1}

となります。

結局、方程式 (1) の正の整数解 (x, y) を求めよという問題に帰着されましたね。


実は、この手の方程式には ペル方程式 という名前がついています。ペル方程式の一般的な問題設定は以下の通りです：

定義（ペル方程式）
D を平方数ではない正の整数とする。このとき、 x, y を整数として

x^2 - Dy^2 = 1 \tag{2}

という形の方程式をペル方程式という。


式 (2) で D = 61 としたものが (1) の方程式ということですね。このペル方程式の正の整数解を求めよという問題だったというわけです。

ちなみに、ペル方程式には x = 1, \; y = 0 なる整数解があります。今回求めたいのは「正の整数解」なので、 y > 0 のものを求める必要があります。


いきなり D = 61 は難しいので、手始めに D = 2, 3, 5 あたりで様子をみてみましょう。

  • D = 2 のとき：

x^2 - 2y^2 = 1 の解として (x, y) = (3, 2) がある。実際、 3^2 - 2\cdot 2^2 = 1。

  • D = 3 のとき：

x^2 - 3y^2 = 1 の解として (x, y) = (2, 1) がある。実際、 2^2 - 3\cdot 1^2 = 1。

  • D = 5 のとき：

x^2 - 5y^2 = 1 の解として (x, y) = (9, 4) がある。実際、 9^2 - 5\cdot 4^2 = 1。

なるほど、片っ端から計算してみれば、手計算でもいけるかもしれない。


そう思うかもしれません。

しかし、たとえば D = 13 をやってみると・・・。

  • D = 13 のとき：

x^2 - 13y^2 = 1 の解として (x, y) = (649, 180) がある。実際、 649^2 - 13\cdot 180^2 = 1。

お、ちょっとやばそうだなという感じがしてきますね。これでも y の値が 最小の解 なのです。


一般にペル方程式の解は、係数の値に対して、解の値が大きくなる傾向があります。そのため、普通にやっていたらうまくいきそうにありません。

実は、ペル方程式の解が機械的に求まる魔法のような方法があります。それが 連分数展開 を使った方法です。


連分数を使ったペル方程式の解法

「連分数」については、一つ前の記事に書いておきましたので、知らない人は参照してください。
tsujimotter.hatenablog.com


ただし、全部読まなくても、今回の内容を理解する目的においては以下の3点を思い出してもらえれば十分です：

① \sqrt{D} が連分数
\displaystyle \sqrt{D} = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{\ddots + \cfrac{\ddots}{a_n + \cfrac{1}{\ddots}}}}} \tag{3}

の形で表せること（連分数展開）。

② \sqrt{D} の連分数展開は周期を持つこと。

③ \sqrt{D} の連分数展開は、以下のサイトで計算できること：
tsujimotter.info
（ぜひ計算に活用してください！）


それでは、上記を使ったペル方程式 x^2 - Dy^2 = 1 の解法を紹介しましょう。

上の四角枠内で書いた \sqrt{D} の連分数展開の式 (3) において、 n を連分数の周期としておきます。つまり、この先

a_{n+1} = a_1, \; a_{n+2} = a_2, \; \ldots, a_{2n} = a_{n}, \; \ldots

が成り立つということですね。


ここで、周期 -1 の n-1 項目までの項で構成された「近似分数」を計算したいと思います。すなわち

\displaystyle a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{\ddots + \cfrac{\ddots}{a_{n-1}}}}} = \frac{P}{Q} \tag{4}
　
ということです。これは有限項で打ち切られていますので、有理数になります。 P, Q は約分された形におきます。

ここで得られた P, Q を使うと

P^2 - DQ^2 = (-1)^n \tag{5}

が成り立ちます。 n が偶数のときは、なんと (x, y) = (P, Q) がペル方程式の解となっている のです。

すごい！！


n が奇数のときも、右辺が -1 となった「ペル方程式の亜種」の解となっています。この場合も、以下の手順を実行すればペル方程式の解を生成することができます。


次が成り立っているとしましょう：

P^2 - DQ^2 = -1

左辺を「 \sqrt{D} を使って因数分解」します。

(P + Q\sqrt{D}) (P - Q\sqrt{D}) = -1

両辺を 2 乗すると

(P + Q\sqrt{D})^2 (P - Q\sqrt{D})^2 = (-1)^2

となりますが、 (P + Q\sqrt{D})^2, \; (P - Q\sqrt{D})^2 をそれぞれ計算すると

(P + Q\sqrt{D})^2 = (P^2 + DQ^2) + 2PQ\sqrt{D}
(P - Q\sqrt{D})^2 = (P^2 + DQ^2) - 2PQ\sqrt{D}

となります。

X := P^2 + DQ^2, \;\; Y := 2PQ とおけば

(X + Y\sqrt{D}) (X - Y\sqrt{D}) = 1

が得られたことになりますが、左辺を展開すると

X^2 - DY^2 = 1

となり、 (x, y) = (X, Y) がペル方程式の解となりますね。



実際、 D = 3 の場合を計算してみましょう。 \sqrt{3} の連分数展開は、前回の記事で計算したように

\displaystyle \sqrt{3} = 1 + \cfrac{1}{1 + \cfrac{1}{2 + \cfrac{1}{1 + \cfrac{1}{2 + \cfrac{1}{\ddots}}}}}

であり、周期は 2 なのでした。（ 1, 2 が繰り返される。）

よって、 1 項目までの近似分数を計算すると

\displaystyle \sqrt{3} = 1 + \cfrac{1}{1} = \frac{2}{1}

が得られました。

P = 2, \; Q = 1 とすると

P^2 - 3Q^2 = (-1)^2

が成り立つということでした。すなわち、ペル方程式 x^2 - 3y^2 = 1 の解 (x, y) = (2, 1) が得られました。


まるで魔法のような解法ですね！


D = 61の場合の解法（元の問題）

そんなわけで、この魔法のような解法を D = 61 に適用しようと思います。

\sqrt{61} の連分数展開を計算すると、次のようになります（連分数展開アプリで D = 61、 n は適当に長い値を入れて計算してみましょう。）：

\displaystyle \sqrt{61} = 7 + \cfrac{1}{1 + \cfrac{1}{4 + \cfrac{1}{3 + \cfrac{1}{1 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{1 + \cfrac{1}{3 + \cfrac{1}{4 + \cfrac{1}{1 + \cfrac{1}{14 + \cfrac{1}{\ddots}}}}}}}}}}}} \tag{6}

なかなかやばいですね。計算がすごいことになりそうです。

ここで、周期に着目すると

1, 4, 3, 1, 2, 2, 1, 3, 4, 1, 14

が繰り返されることになります。つまり、周期 n = 11 です。

残念ながら周期は奇数なので、ペル方程式そのものの解は得られませんが、 10 項目までの近似分数を計算しましょう。（連分数展開アプリで D = 61、 n = 10 と入れて計算してみましょう。）

\displaystyle \sqrt{61} = 7 + \cfrac{1}{1 + \cfrac{1}{4 + \cfrac{1}{3 + \cfrac{1}{1 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{1 + \cfrac{1}{3 + \cfrac{1}{4 + \cfrac{1}{1}}}}}}}}}} = \frac{29718}{3805} \tag{7}

よって、 P = 29718, \;\; Q = 3805 とすると

P^2 - 61 Q^2 = -1 \tag{8}

が成り立つというわけですね。
（実際、そうなっているか確認してみましょう。）



さて、これだと式 (8) の右辺が -1 となっていますので、前節で紹介した方法をとります。

まず、式 (8) の因数分解を実行すると

(P + Q\sqrt{61}) (P - Q\sqrt{61}) = -1

となり、両辺を2乗するのでした。左辺の各因数を2乗すると

(P + Q\sqrt{61})^2 = P^2 + 61Q^2 + 2PQ\sqrt{61}
(P - Q\sqrt{61})^2 = P^2 + 61Q^2 - 2PQ\sqrt{61}

となり、

\begin{align*} X &:= P^2 + 61Q^2 = 29718^2 + 61\cdot 3805^2 = 1766319049 \\ Y & := 2PQ = 2\cdot 29718 \cdot 3805 = 226153980 \end{align*}

となります。

これは、元の式に代入すると

X^2 - 61Y^2 = 1

となりますので、ペル方程式の整数解

(x, y) = (1766319049, 226153980)

が得られました。


最初の問題の答えは、 N = x^2 なので

N = 3119882982860264401

が答えになります！！！


解法２：連分数展開から直接計算する方法

上では、 \sqrt{61} の連分数展開の周期が

1, 4, 3, 1, 2, 2, 1, 3, 4, 1, 14

となり、周期 11 が奇数なので、近似分数を P/Q とすると

P^2 - 61Q^2 = -1

となってしまうという話でした。右辺が -1 なので、直接的には求まらないということですね。


ここで発想をかえて、連分数展開の周期 2 つ分を 1 つの周期と考えましょう。すなわち

1, 4, 3, 1, 2, 2, 1, 3, 4, 1, 14, 1, 4, 3, 1, 2, 2, 1, 3, 4, 1, 14

を周期 22 だと考えるわけです。

これにより、 22 - 1 = 21 次の近似分数を求めると

\displaystyle \frac{1766319049}{226153980} = 7 + \cfrac{1}{1 + \cfrac{1}{4 + \cfrac{1}{3 + \cfrac{1}{1 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{1 + \cfrac{1}{3 + \cfrac{1}{4 + \cfrac{1}{1 + \cfrac{1}{14 + \cfrac{1}{1 + \cfrac{1}{4 + \cfrac{1}{3 + \cfrac{1}{1 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{1 + \cfrac{1}{3 + \cfrac{1}{4 + \cfrac{1}{1}}}}}}}}}}}}}}}}}}}}}

となります。実はこの分子と分母がそのまま解となっています。すなわち

P = 1766319049, \; Q= 226153980

として

P^2 - 61Q^2 = 1

が成り立つというわけです。

これなら連分数展開のアプリに D = 61 と n = 21 を入れてボタンを押すだけで解が求まってしまいますね！

いつペル方程式がやってきても怖くないですね！！


おわりに

みなさんは答えられましたか？（いじわるすぎましたか？）


今回の記事では、以下の２点について解説しました：

  • 冒頭に述べた問題がペル方程式 x^2 - 61y^2 = 1 に帰着できること
  • この解は \sqrt{D} の連分数展開の n-1 次の近似分数を使って求められること

なお、最後の節でやったことを延長させると、 \sqrt{D} の連分数展開の n-1 次， 2n-1 次， 3n-1 次，・・・（以下無限に続く）の近似分数は、すべてペル方程式

x^2 - Dy^2 = \pm 1

の解を与えます。この方法によって上記のペル方程式のすべての正の整数解を与えることが知られています。

特に、 n-1 次の近似分数は（右辺が \pm 1 のどちらかの）ペル方程式の 最小解 を与えることが知られています。この事実は次回使いたいと思います。

2021.03.03追記 このブロックの記述（特に最小解についての記述）を追記しました。

今回紹介した「 x^2 - 61y^2 = 1 の整数解を求めよ」という問題は、あの フェルマー がイギリスの数学者たちに向けて出した問題だと言われています。フェルマーって、結構いじわるな問題を出すんですね。


もちろん、これにはちゃんと訳があります。当時の数学の主流はニュートンやライプニッツに端を発する「微積分学」であり、それに対して「整数論」は重要視されていませんでした。フェルマーの行っていた「整数論」に関する研究が十分評価されていなかったということですね。

こうした背景もあり、「整数論って実は奥深いんだぞ」ということを知らしめるために、整数論の「深い」問題を国外の著名な数学者に送りつけたということなのだそうです。このエピソードは次の本に載っていました。

フェルマーの大定理が解けた！　オイラーからワイルズの証明まで (ブルーバックス)

フェルマーの大定理が解けた！　オイラーからワイルズの証明まで (ブルーバックス)

Amazon

ペル方程式の整数解の問題は、「普通に計算していたらとても計算できないような巨大な解」が存在することもあり、かつ連分数という「思いも掛けない道具を使って解を求めることができる」という、非常に奥深い問題だったわけですね。


そんなわけでtsujimotterも読者の皆さんに整数論に興味を持っていただけたらと思っています。この問題をきっかけとして。気持ちはフェルマーと同じです。


明日はペル方程式についての面白い応用事例を紹介したいと思います。よかったらTwitterのコメント等でどんな応用が来るか予想してみてください。笑

それでは今日はこの辺で！

*1:変えたところは「61」というところで、元の問題は「60」となっていました。 こちらの記事で番組の内容の解説がされています。 gascon.cocolog-nifty.com