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

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

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

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

f:id:tsujimotter:20210227004642p:plain:w400

f:id:tsujimotter:20210227004708p:plain:w220

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

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

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

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

↓　↓　↓

それではいきましょう！

ペル方程式に帰着

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

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

f:id:tsujimotter:20210227005837p:plain:w220

また「兵士たちが正方形に並んでいる。これを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}}}}}}}}}}}}}}}}}}}}}$