ラスクのMathematics for Everyone!

数学が得意な人もそうでない人もちょっとだけ楽しめるようなブログです。

ペル方程式の解法!ヘイスティングズの戦いにおける兵数は?

みなさまこんにちは、ラスクです。

9月も終わりを迎え、ようやく暑さも和らいできましたね。
この挨拶の部分も若干ネタ切れ感が出てきてきました。。


そんなことはどうでもいいとして、内容に入りましょう!!
今回は、ヘイスティングズの戦いという歴史的事件をもとにした、ある問題を解くことを目標にしつつ、それに関連するペル方程式の話をしていきたいと思います。

ペル方程式自体はそこそこ有名な対象なのでネットを探せば様々な記事がヒットしますが、「ヘイスティングズの戦い」について触れているものは僕の知る限りほとんどありませんでした。
なので今回、詳しく話していこうと思います。

また(特に意図があったわけではないのですが)、今までの記事の内容は私の専門である「整数論」の内容とは少し異なるものが多かったです。
しかし今回話す、ペル方程式は「代数的整数論」において非常に重要な対象として登場します。
なので、そのあたりの話も絶対に書きたい*1、と思っています。
これについては次回以降の記事になりますので、今回の記事が気に入っていただけた方は、是非そちらもアップされ次第読んでみてください!



では前置きはこれくらいにして始めていきましょう!!

ハロルド2世の軍の兵数は?

今回考える問題は次のようなものです。

問題
かつてのイングランド王ハロルド2世の軍は古来からの慣わしで、同じ大きさの13個の正方形をなすように編成されていた。
その後ハロルド2世自身が「ヘイスティングズの戦い」の戦場に現れると、兵士たちはその王を頂点に一つの巨大な正方形をなして突撃したという。

では、ハロルド2世の軍は何人だったのだろうか。

意味はお分かりいただけたでしょうか。


私はこの問題を、ノイキルヒの『代数的整数論』(非常に有名な整数論の教科書)で知りました。
この本の演習問題の一つとして上の内容が載っているのですが、普通の数学の問題が並ぶ中、明らかにこれだけ異様なオーラを放っています(笑)
というのも、この本の原文にはもっとメッセージ性の強い語調で上の問題が記されています。
今回、私は皆さんに伝わりやすいように多少文章を簡単にしていますが、なかなか数学の問題に個人の感情をのせることはないと思うので是非興味のある方は調べてみてください。


ちなみにヘイスティングズの戦いとは、ノルマンディー公ギヨーム2世とイングランド王ハロルド2世がイングランド領をめぐって争った会戦のことです。恥ずかしながら、これ以上のことはよく知らないので気になる方はWikipediaの記事をお読みください。

ja.wikipedia.org




少し余談が長くなりましたが、数学の話をしましょう。


上の問題を数式で表していきます。
王が加わってできた巨大な正方形の一辺の人数をx人、もともとの13個あった正方形の一辺の人数をy人とする。
このとき
\begin{align}
x^2=13y^2+1
\end{align}
つまり
\begin{align}
x^2-13y^2=1 \tag{1}
\end{align}
が成り立ちます。
したがって上の問題は(1)式を満たすような自然数(x,y)を求めよ、と言われていることに他なりません。
実はこの式がペル方程式と呼ばれるものの一種になっています。

定義
Dを平方数でない自然数とする。
\begin{align}
x^2-Dy^2=1 \tag{2}
\end{align}
という形の方程式をペル方程式という。

今回目標となっているのは、D=13のケースですね。

そこで次の章から、このペル方程式の整数解の求め方について詳しく見ていくことにします!

ペル方程式の解法

一般解の構造

一般にペル方程式(2)はどのようなDに対しても無数の整数解をもつことが知られています。
そして、それらの解の間には非常に簡明で美しい法則があることも知られています。まずはそちらを紹介しましょう。

ここで、以下の話の都合上(2)式の右辺を\pm 1に変えたものを考えることにし、これもペル方程式と呼んでしまうことにします。つまり次のような方程式を考えるという事です。
\begin{align}
x^2-Dy^2=\pm 1 \tag{3}
\end{align}
なぜ、こんなことをするの?考えてる問題と違うじゃん!という声が聞こえてきそうですが、ちゃんと最後には(2)式に戻りますので、ご安心を。このようにする理由については別の記事でゆっくりお話ししたいと思います。


さて、次に以下の補題を用意します。

補題
(x,y),(x',y')をペル方程式x^2-Dy^2=\pm 1の正の整数解とする。
このとき、
x < x'かつy < y'\ \Longleftrightarrow x < x'またはy < y'
が成り立つ。

この補題において右向きの矢印は当然成り立つので、非自明なのは左向きの矢印です。
証明はそこまで難しくないので、省略しますが、左向きの矢印の言っていることを言葉にすると
「ペアの片方が相手より小さいならば、もう片方も相手より小さい」
となります。
このことから、ペル方程式の最小解というものが以下のように定義できます。


定義
ペル方程式x^2-Dy^2=\pm 1正の整数解(x,y)のうち、
xが最小となるようなものを、その方程式の最小解という。
このとき上の補題により、yも自動的に最小になる。

一つ注意しておきます。
すべてのペル方程式は(x,y)=(1,0)という自明な解をもちます。しかしこれは、最小解ではありません。
なぜなら、最小解は正の整数解から選んでいたので、y0であるこの解は絶対に最小解にはなりえないのです。
うっかりしていると間違えてしまうので、定義はしっかり読むことが大事です。



これで、各ペル方程式に対して、その最小解が定まったので一般解の構造に関する定理を述べましょう。

定理
ペル方程式
\begin{align}
x^2-Dy^2=\pm 1 \tag{3}
\end{align}
の最小解を(x_1,y_1)とする。また、整数x_n,y_n\ (n\in\mathbb{Z})を以下の式で定める。
\begin{align}
x_n+y_n\sqrt{D}=(x_1+y_1\sqrt{D})^n \tag{4}
\end{align}
このとき、(3)の整数解の集合は
\begin{align}
\{\color{red}{\pm}(x_n,y_n)\ |\ n\in\mathbb{Z}\}
\end{align}
と一致する*2


追記
記事を投稿した時点ではペル方程式の整数解の集合に\pm(上の式で赤字にした部分)をつけるのを忘れてしました。
ペル方程式にはx,yの2乗しか現れないので、(x,y)が解となるなら当然(-x,-y)も解になります。
自然数解だけを知りたい場合にはいらないので、のちの議論にはさほど影響しません。
大変失礼いたしました。


お分かりいただけたでしょうか?
つまり何が言いたいかというと、ペル方程式の”最小解がわかれば”
無数にあるすべての解を知ることが出来る
というわけです。なかなかとんでもない定理ですよね!!


「なぜこんな定理が成り立つのか」、また「定理の中でx_n,y_n達を定めてる式はいったい何者なのか」、非常に気になると思います。
定理の証明自体は初等的にゴリゴリやることもできますが、正直なかなか大変で、意味がよく分からないというのが私の感想です。
なので、私は上の定理の代数的整数論的意味付けをぜひ紹介したいと思っています!
しかし、それを今回の記事でやるのはさすがに厳しく、またペル方程式の解法という趣旨にも反するので、別の記事に回させていただきます。こうご期待ください!!


さて、とにかくペル方程式の一般解が知りたければ、最小解を見つけ出せばいいことがわかりました。
なので、以下ではその見つけ方についてお話ししましょう。
方法のカギとなるのは「連分数展開」です!!

連分数展開

ということで、実数の連分数展開を定義します。

定義
実数aを整数\{a_n\}_{n\ge 0}を用いて
\begin{align}
a=a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3+\ddots}}}
\end{align}
の形に表すことをa(正則)連分数展開という。
このときa=[a_0;a_1,a_2,\ldots]とあらわす。

はじめに注意しておくと、任意の実数aに対して整数\{a_n\}_{n\ge 0}は一意的に定まり、すなわちその連分数展開は一意的に定まります。

初めて見る方はよくわからないかもしれないので、実際に連分数展開の仕方を見ていきましょう。

やり方としては
⓪初めに、その数の整数部分を抜き出す。
そして、あとは
①残った小数部分を(無理矢理)逆数の形にし、その分母を必要なら有理化する
②分母の整数部分を抜き出す
の繰り返しです。

例1
手始めに\sqrt{2}を連分数展開してみます。
まずは、⓪\sqrt{2}の整数部分を抜き出して\sqrt{2}=1+(\sqrt{2}-1)と表します。
①次に小数部分である\sqrt{2}-1を無理矢理\frac{1}{\frac{1}{\sqrt{2}-1}}と表し、この分母にある分数を有理化し\frac{1}{\sqrt{2}-1}=1+\sqrt{2}とします。②このとき現れた\sqrt{2}の整数部分を抜きだし、1+\sqrt{2}=2+(\sqrt{2}-1)とします。
ここまでの操作で、以下の式を得ました。
\begin{align}
\sqrt{2}=1+\frac{1}{2+(\sqrt{2}-1)}
\end{align}
この後、さらに\sqrt{2}-1に対して①をして…という風に続けていけばいいわけですが、これは先にやった操作と同じです。
したがって、以降は全く同じ操作が続くことになり、最終的に以下の展開を得ます。
\begin{align}
\sqrt{2}=1+\frac{1}{2+\frac{1}{2+\frac{1}{2+\ddots}}}
\end{align}
これを\sqrt{2}=[1;2,2,2,\ldots]と書くわけですが、巡回する節は括弧()でくくって表すことにすれば、
\begin{align}
\sqrt{2}=[1;(2)]
\end{align}
となります。納得できましたでしょうか?

例2
もう少し慣れるためと後の都合のため、\sqrt{7}についても考えてみましょう。
やることは全く同じです。
⓪①②の順に1ステップ終わらせると次のようになります。
\begin{align}
\sqrt{7}&=2+(\sqrt{7}-2)\\
&=2+\frac{1}{\frac{\sqrt{7}+2}{3}}\\
&=2+\frac{1}{1+\frac{\sqrt{7}-1}{3}}
\end{align}
そして、今度は\frac{\sqrt{7}-1}{3}に注目して同じ計算をして…という事を繰り返していきます。
以下各ステップごとの結果をどんどん書きますが、是非ご自分で計算してみてください。
おそらく一度やれば、身につくはずです。

\begin{align}
\sqrt{7}&=2+\color{red}{(\sqrt{7}-2)}\\
\sqrt{7}-2&=\frac{1}{1+\frac{\sqrt{7}-1}{3}}\\
\frac{\sqrt{7}-1}{3}&=\frac{1}{1+\frac{\sqrt{7}-1}{2}}\\
\frac{\sqrt{7}-1}{2}&=\frac{1}{1+\frac{\sqrt{7}-2}{3}}\\
\frac{\sqrt{7}-2}{3}&=\frac{1}{4+\color{red}{(\sqrt{7}-2)}}\\
\end{align}

はい。ここまで行くと、赤文字で書いた\sqrt{7}-2が巡回しましたので以下同じように展開が続くことがわかります。
したがって、連分数展開が
\begin{align}
\sqrt{7}=[2;(1,1,1,4)]
\end{align}
と求まりました。皆様答えは合いましたでしょうか?

ペル方程式の最小解

では、このことをペル方程式の最小解と関連付けていきます。

今、無理数\sqrt{D}(Dは平方数でない自然数) に対して、その連分数展開は必ず
\begin{align}
\sqrt{D}=[a_0;(a_1,a_2,\ldots,a_k)]
\end{align}
という形になります。
このとき、k\sqrt{D}の連分数展開の周期といいます。
また、有理数
\begin{align}
\frac{P}{Q}=[a_0;a_1,a_2.\ldots,a_{{k}-1}]
\end{align}
\sqrt{D}近似分数といいます。ただし、\frac{P}{Q}は既約であるとします。

近似分数の定義において、周期の最後の項a_kを除いていることに注意してください。
このような定義の下で次の定理が成り立ちます。

定理
ペル方程式
\begin{align}
x^2-Dy^2=\pm1
\end{align}
に対して、\sqrt{D}の連分数展開を[a_0;(a_1,a_2,\ldots,a_k)]、その近似分数を\frac{P}{Q}とする。このとき、
(1)周期kが奇数ならば、
\begin{align}
(x_1,y_1)=(P,Q)
\end{align}
x^2-Dy^2=-1の最小解となり、(4)式にn=2を代入して定まる
\begin{align}
(x_2,y_2)=(P^2+D{Q}^2,2PQ)
\end{align}
x^2-Dy^2=1の最小解となる。
(2)周期kが偶数ならば、
\begin{align}
(x_1,y_1)=(P,Q)
\end{align}
x^2-Dy^2=1の最小解となり、
x^2-Dy^2=-1の整数解は存在しない。

つまり、ペル方程式を定めているD平方根の近似分数を見れば、最小解が求まってしまうという事です。
証明をやると、記事の分量が2倍(3倍?)になってしまうので、今回は事実として認めて頂きたいです。


例を見ましょう。
例3
まずx^2-2y^2=\pm1を考えましょう。
\sqrt{2}の連分数展開は例1でやったように[1;(2)]です。なのでその近似分数は、少しわかりにくいですが
\begin{align}
[1]=1=\frac{1}{1}
\end{align}
です。周期は1なので、整数部分だけ生き残るという事ですね。
今回は周期が奇数なので、定理の(1)から
x^2-2y^2=-1の最小解は(x_1,y_1)=(1,1)
x^2-2y^2=1の最小解は(x_2,y_2)=(3,2)
となります。一般解が(4)式により求まり、具体的には
(x_3,y_3)=(7,5),(x_4,y_4)=(17,12)
などとなります。

例4
もう一つのパターンの例も見ましょう。
x^2-7y^2=\pm1を考えます。\sqrt{7}=[2;(1,1,1,4)]だったので、その近似分数は
\begin{align}
[2;1,1,1]=2+\frac{1}{1+\frac{1}{1+\frac{1}{1}}}=\frac{8}{3}
\end{align}
となります。今回は周期が偶数のケースなので定理の(2)より
x^2-7y^2=1の最小解は(x_1,y_1)=(8,3)
x^2-7y^2=-1の整数解は存在しない、となります。
上と同様にいくつか他の解を求めてみると
(x_2,y_2)=(127,48),(x_3,y_3)=(2024,765)
となります。



ということでこれで、どのようなペル方程式でも一定のアルゴリズムに従って一般解を求めることが出来るようになりました。まとめておきましょう。

ペル方程式 x^2-Dy^2=\pm1の解法
(Ⅰ)\sqrt{D}の連分数展開を求める。
(Ⅱ)そこから\sqrt{D}の近似分数を求めると、その分子と分母が最小解になっている
(Ⅲ)最小解に対して(4)式を使う事ですべての解を得ることが出来る。


問題の答え

では、ペル方程式の解法がわかったところで「ヘイスティングズの戦い」の問題を解いていきましょう。
とはいっても、ここまで読んでくださった方であればもう答えを導けるはずです。なので、是非ご自分で答えを出してみて以下に書くことは答え合わせのためにお使いください





では始めます。
問題の兵数を求めるには、
\begin{align}
x^2-13y^2=1 \tag{1}
\end{align}
を解けばよいのでした。そのために(Ⅰ)\sqrt{13}の連分数展開を求めます。
\begin{align}
\sqrt{13}&=3+\color{red}{(\sqrt{13}-3)}\\
\sqrt{13}-3&=\frac{1}{1+\frac{\sqrt{13}-1}{4}}\\
\frac{\sqrt{13}-1}{4}&=\frac{1}{1+\frac{\sqrt{13}-2}{3}}\\
\frac{\sqrt{13}-2}{3}&=\frac{1}{1+\frac{\sqrt{13}-1}{3}}\\
\frac{\sqrt{13}-1}{3}&=\frac{1}{1+\frac{\sqrt{13}-3}{4}}\\
\frac{\sqrt{13}-3}{4}&=\frac{1}{6+\color{red}{(\sqrt{13}-3)}}
\end{align}
したがって\sqrt{13}=[3;(1,1,1,1,6)]。(Ⅱ)これから\sqrt{D}の近似分数を求めると
\begin{align}
[3;1,1,1,1]=3+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1}}}}=\frac{18}{5}
\end{align}
今、周期が5で奇数なことから
x^2-13y^2=-1の最小解は(x_1,y_1)=(18,5)
x^2-13y^2=1の最小解は(x_2,y_2)=(649,180)
となります。数学的には(x_4,y_4)(x_6,y_6)なども解になりますが兵数を考えていることを思い出すと、現実的な数字ではないので、最小解(x_2,y_2)のみ考えることにします。

そうすると、答えであるハロルド2世の軍の兵数が 649^2-1=421200(人)と求まりました!!
…本当でしょうか、かなり怪しいですね。。。

まあ、1000年近く前の出来事で本当にこのような慣わしがあったのかすら微妙なので、怪しい数字になるのは当たり前といえば当たり前でしょう。それでも、解を求められたのはよかったと思います。皆さんの答えは当たっていましたでしょうか?

まとめ

ということで、今回は「ヘイスティングズの戦い」の問題をもとにペル方程式の解法を紹介していきました。
いかがでしたでしょうか。
ペル方程式というのは、ディオファントス方程式という整数論の原動力ともなっているようなものの一種です。
一般にディオファントス方程式を調べるのは非常に難しく、あの有名な「フェルマーの最終定理」もこのディオファントス方程式に関する定理になります。
そんな方程式の中で、ペル方程式は非常に綺麗な解の構造を持っており、加えてその解もかなり簡単なアルゴリズムで得られることが今回の記事を読んでお分かりいただけたと思います。

しかも、最初の方でいったようにこの方程式は「代数的整数論」(特に2次体の単数群)において非常に重要な役割を果たします。
そのような重要なものが、簡単に計算できるというのはとても不思議でありがたいことだと思うわけです。

このあたりのことについては、また別の記事で…。


では最後までご覧いただきありがとうございました!!

コメントはどんなものでも絶賛受け付け中です!
気に入ってくださった方は「読者になる」ボタンやTwitterフォローもポチッとお願いします!

それではまた次回お会いいたしましょう!

f:id:rusk_mathematics:20191005174420p:plain

*1:というかむしろ、そちらを書きたいがゆえに今回の記事を書いている?

*2:ここで、最小解(x_1,y_1)が(左辺)=1の解であれば、(x_n,y_n)は全て(左辺)=1の解になります。対して最小解(x_1,y_1)が(左辺)=-1の解であれば、\pm(x_{2k},y_{2k}),(k\in\mathbb{Z})が(左辺)=1の、\pm(x_{2k+1},y_{2k+1}),(k\in\mathbb{Z})が(左辺)=-1の解全体に一致します。当然、(x_2,y_2)が(左辺)=1の最小解です。