２章　Pell方程式と連分数展開

不定方程式 x²−ｍy²＝±１を Pell方程式 と呼ぶ。
これは、ｍが２乗数でないとき、ｘ＝±１、ｙ＝０以外の解を必ず持つ。
また、sqrt(m) を以下のように表したとき、

	1
sqrt(m) ＝ a1 ＋	------------------------
		1
	a2 ＋	------------------
			1
		a3 ＋	------------
			a4 ＋	……

sqrt(m)の連分数展開と呼ぶ。
このままでは、表記するのが大変なので（ソースを見てください）、

sqrt(m)＝a₁[a₂, a₃, a₄, ……]

と略記する。

Pell方程式の解及び連分数展開の各桁は以下の漸化式より求められる。

an	連分数展開の各桁の数
pn／qn	ｎ番目で打ち切ったときの部分和
Pn、Qn	補助変数

これらの数について第ｎ項目は、

an	a1＝int(sqrt(m)) 　…… an＝int((a1＋Pn)/Q1)
Pn	P1＝０ P2＝a1 　…… Pn＝an-1×Qn-1−Pn-1
Qn	Q1＝１ Q2＝ｍ−a12 　…… Qn＝(ｍ−Pn2)／Qn-1
pn	p1＝a1 p2＝a2×a1＋１ 　…… pn＝an×pn-1＋pn-2
qn	q1＝１ q2＝a2 　…… qn＝an×qn-1＋qn-2

Q_n＝１となるｎについて、 p_n-1、q_n-1が Pell方程式の解となる。

この漸化式をExcelの計算式で表してみる。

ｎ＝１，２，３のときは直接式を書き込む。
ｎ＝４以降は、ｎ＝３の時の行をそのままコピーすると、 行、列の index が自動的に increment される。

B1に求める値を代入し、Ｃの４行目以降に１が現れるまで、計算式をコピーする。
Ｃのｋ行目が１となったとき、

Ｅ、Ｆのｋ−１行目が Pell方程式の解
Ｄの３行目〜ｋ行目が連分数展開の各項

となる。

100以下で循環節が最も長くなるｍ＝94の場合について、サンプルを示す。

連分数展開

sqrt(94)＝9 [1, 2, 3, 1, 1, 5, 1, 8, 1, 5, 1, 1, 3, 2, 1, 18]

Pell方程式の初期解

ｘ＝2143295
ｙ＝221064

となる。