ペル方程式

紀元前400年頃のインドとギリシャでは、数学者たちがペル方程式の n  = 2の場合から生じる数を研究していた。 $${\displaystyle x^{2}-2y^{2}=1,}$$ そして、密接に関連する方程式から $${\displaystyle x^{2}-2y^{2}=-1}$$これらの方程式が2 の平方根 と関連しているためです。^{[ 5 ]}実際、xとy がこの方程式を満たす正の整数である場合、 x / yは√2の近似値になります。これらの近似値に現れる数xとy は、辺数と直径数と呼ばれ、ピタゴラス学派に知られており、プロクロスは反対方向にこれらの数が 2 つの方程式のいずれかに従うことを観察しました。^{[ 5 ]}同様に、バウダヤーナは、x = 17、y = 12 とx = 577、y = 408 がペル方程式の 2 つの解であり、17/12 と 577/408 が 2 の平方根に非常に近い近似値であることを発見しました。^{[ 6 ]}

後にアルキメデスは、 3の平方根を有理数1351/780で近似しました。彼はその方法を説明しませんでしたが、この近似値はペル方程式の解として同じ方法で得られます。 ^{[ 5 ]} 同様に、アルキメデスの牛の問題（太陽神ヘリオスに属する牛の数を求める古代の言葉の問題）は、ペル方程式として再定式化することで解くことができます。この問題を含む写本には、それがアルキメデスによって考案され、エラトステネスへの手紙に記録されたと記されており、^{[ 7 ]}今日ではアルキメデスへの帰属が一般的に受け入れられています。^{[ 8 ] [ 9 ]}

AD 250 年頃、ディオファントスは次の方程式を考えました。 $${\displaystyle a^{2}x^{2}+c=y^{2},}$$ where a and c are fixed numbers, and x and y are the variables to be solved for. This equation is different in form from Pell's equation but equivalent to it. Diophantus solved the equation for (a, c) equal to (1, 1), (1, −1), (1, 12), and (3, 9). Al-Karaji, a 10th-century Persian mathematician, worked on similar problems to Diophantus.^[10]

In Indian mathematics, Brahmagupta discovered that $${\displaystyle (x_{1}^{2}-Ny_{1}^{2})(x_{2}^{2}-Ny_{2}^{2})=(x_{1}x_{2}+Ny_{1}y_{2})^{2}-N(x_{1}y_{2}+x_{2}y_{1})^{2},}$$ a form of what is now known as Brahmagupta's identity. Using this, he was able to "compose" triples ${\displaystyle (x_{1},y_{1},k_{1})}$ and ${\displaystyle (x_{2},y_{2},k_{2})}$ that were solutions of ${\displaystyle x^{2}-Ny^{2}=k}$, to generate the new triples

${\displaystyle (x_{1}x_{2}+Ny_{1}y_{2},x_{1}y_{2}+x_{2}y_{1},k_{1}k_{2})}$ and ${\displaystyle (x_{1}x_{2}-Ny_{1}y_{2},x_{1}y_{2}-x_{2}y_{1},k_{1}k_{2}).}$

Not only did this give a way to generate infinitely many solutions to ${\displaystyle x^{2}-Ny^{2}=1}$ starting with one solution, but also, by dividing such a composition by ${\displaystyle k_{1}k_{2}}$, integer or "nearly integer" solutions could often be obtained. For instance, for ${\displaystyle N=92}$, Brahmagupta composed the triple (10, 1, 8) (since ${\displaystyle 10^{2}-92(1^{2})=8}$) with itself to get the new triple (192, 20, 64). Dividing throughout by 64 ("8" for ${\displaystyle x}$ and ${\displaystyle y}$) gave the triple (24, 5/2, 1), which when composed with itself gave the desired integer solution (1151, 120, 1). Brahmagupta solved many Pell's equations with this method, proving that it gives solutions starting from an integer solution of ${\displaystyle x^{2}-Ny^{2}=k}$ for k = ±1, ±2, or ±4.^[11]

The first general method for solving the Pell's equation (for all N) was given by Bhāskara II in 1150, extending the methods of Brahmagupta. Called the chakravala (cyclic) method, it starts by choosing two relatively prime integers ${\displaystyle a}$ and ${\displaystyle b}$, then composing the triple ${\displaystyle (a,b,k)}$ (that is, one which satisfies ${\displaystyle a^{2}-Nb^{2}=k}$) with the trivial triple ${\displaystyle (m,1,m^{2}-N)}$ to get the triple ${\displaystyle {\big (}am+Nb,a+bm,k(m^{2}-N){\big )}}$, which can be scaled down to $${\displaystyle \left({\frac {am+Nb}{k}},{\frac {a+bm}{k}},{\frac {m^{2}-N}{k}}\right).}$$

When ${\displaystyle m}$ is chosen so that ${\displaystyle {\frac {a+bm}{k}}}$ is an integer, so are the other two numbers in the triple. Among such ${\displaystyle m}$, the method chooses one that minimizes ${\displaystyle {\frac {m^{2}-N}{k}}}$ and repeats the process. This method always terminates with a solution. Bhaskara used it to give the solution x = 1766319049, y = 226153980 to the N = 61 case.^[11]

17 世紀には、数人のヨーロッパの数学者がペル方程式の解き方を再発見しました。ピエール・ド・フェルマーは方程式の解き方を発見し、1657 年の手紙でイギリスの数学者への挑戦として発表しました。^{[ 12 ]}ケネルム・ディグビーへの手紙の中で、ベルナール・フレニクル・ド・ベシーは、フェルマーがNが150 までの場合の最小解を見つけ、ジョン・ウォリスにN = 151 または 313の場合を解くように挑戦したと述べています。ウォリスとウィリアム・ブロンカーの両方がこれらの問題の解を与えましたが、ウォリスは手紙の中で、解はブロンカーによるものだと示唆しています。^{[ 13 ]}

ジョン・ペルとこの方程式との関連は、彼がトーマス・ブランカーによるヨハン・ラーンの1659年の著書『ドイツ代数学』^{[注2 ]}の英訳^{[ 14 ]}を改訂し、ブランカーによるこの方程式の解法について論じたことにある。レオンハルト・オイラーはこの解法がペルによるものだと誤解し、その結果、この方程式をペルの名にちなんで命名した。^{[ 4 ]}

ペル方程式の一般理論は、連分数と次の形式の数を用いた代数操作に基づいている。${\displaystyle P+Q{\sqrt {a}},}$1766年から1769年にかけてラグランジュによって開発された。^{[ 15 ]}特に、ラグランジュはブロンカー・ウォリスアルゴリズムが常に終了することを証明した。

させて${\displaystyle h_{i}/k_{i}}$は、正則連分数の収束の一意な列を表す。${\displaystyle {\sqrt {n}}}$すると、正の整数のペア${\displaystyle (x_{1},y_{1})}$ペル方程式を解いてx を最小化すると、あるiに対してx ₁ = h _iおよびy ₁ = k _iが成り立つ。このペアは基本解と呼ばれる。整数の列${\displaystyle [a_{0};a_{1},a_{2},\ldots ]}$通常の連続分数では${\displaystyle {\sqrt {n}}}$は最終的に必ず周期的になる。それは次の形式で書くことができる。${\displaystyle \left[\lfloor {\sqrt {n}}\rfloor$ ;\;{\overline {a_{1},a_{2},\ldots ,a_{r-1},2\lfloor {\sqrt {n}}\rfloor }}\right]} 、ここで${\displaystyle \lfloor \,\cdot \,\rfloor }$は整数階を表し、数列は${\displaystyle a_{1},a_{2},\ldots ,a_{r-1},2\lfloor {\sqrt {n}}\rfloor }$無限に繰り返されます。さらに、タプル${\displaystyle (a_{1},a_{2},\ldots ,a_{r-1})}$回文であり、左から右、または右から左に読んでも同じです。^{[ 16 ]}

根本的な解決策は $${\displaystyle (x_{1},y_{1})={\begin{cases}(h_{r-1},k_{r-1}),&{\text{ for }}r{\text{ even}}\\(h_{2r-1},k_{2r-1}),&{\text{ for }}r{\text{ odd}}\end{cases}}}$$

連分数法を用いて基本解を求める際の計算時間は、高速整数乗算のためのSchönhage–Strassenアルゴリズムの助けを借りれば、解のサイズ（ペアの桁数）の対数係数の範囲内に収まる。${\displaystyle (x_{1},y_{1})}$しかし、これは多項式時間アルゴリズムではありません。なぜなら、解の桁数は最大で${\displaystyle {\sqrt {n}}}$入力値nの桁数に関する多項式よりもはるかに大きい。^{[ 17 ]}

基本解が見つかれば、残りのすべての解は^{[ 17 ]から代数的に計算できます。}$${\displaystyle x_{k}+y_{k}{\sqrt {n}}=(x_{1}+y_{1}{\sqrt {n}})^{k},}$$ 右辺を展開し、係数を等しくする${\displaystyle {\sqrt {n}}}$両辺に等式を置き、両辺の他の項を等しくすると、次の漸化式が得られる。$${\displaystyle x_{k+1}=x_{1}x_{k}+ny_{1}y_{k},}$$$${\displaystyle y_{k+1}=x_{1}y_{k}+y_{1}x_{k}.}$$

基本解 ( x ₁ , y ₁ ) をバイナリ数のペアとして書き出すには多くのビットが必要になる場合があるが、多くの場合、よりコンパクトな形式で表現できる。 $${\displaystyle x_{1}+y_{1}{\sqrt {n}}=\prod _{i=1}^{t}\left(a_{i}+b_{i}{\sqrt {n}}\right)^{c_{i}}}$$ はるかに小さな整数a _i、b _i、c _iを使用します。

例えば、アルキメデスの牛の問題はペル方程式と等価である。${\displaystyle x^{2}-410\,286\,423\,278\,424\ y^{2}=1}$その根本的な解決策は明示的に書き出すと 206 545桁になります。ただし、解は次のようにも等しくなります。$${\displaystyle x_{1}+y_{1}{\sqrt {n}}=u^{2329},}$$ どこ $${\displaystyle u=x'_{1}+y'_{1}{\sqrt {4\,729\,494}}=(300\,426\,607\,914\,281\,713\,365\ {\sqrt {609}}+84\,129\,507\,677\,858\,393\,258\ {\sqrt {7766}})^{2}}$$ そして${\displaystyle x'_{1}}$そして${\displaystyle y'_{1}}$それぞれ45桁と41桁の10進数しか持たない。^{[ 17 ]}

整数因数分解のための二次篩法に関連する手法は、によって生成される数体における素数間の関係を収集するために使用できる。${\displaystyle {\sqrt {n}}}$そして、これらの関係を組み合わせて、このタイプの積表現を見つけます。結果として得られるペル方程式を解くアルゴリズムは、連分数法よりも効率的ですが、それでも多項式時間より時間がかかります。一般化リーマン予想の仮定の下では、時間がかかることが示されます。 $${\displaystyle \exp O\left({\sqrt {\log N\cdot \log \log N}}\right),}$$ ここで、N  =  log nは入力サイズであり、二次ふるいと同様である。^{[ 17 ]} 

ハルグレンは、量子コンピュータが上記のようにペル方程式の解の積表現を多項式時間で見つけることができることを示した。^{[ 18 ]}実二次数体の単元群を見つけるアルゴリズムとして解釈できるハルグレンのアルゴリズムは、シュミットとフェルマーによってより一般的な体へと拡張された。^{[ 19 ]}

ペル方程式は代数的数の理論と密接に関係しており、その式は $${\displaystyle x^{2}-ny^{2}=(x+y{\sqrt {n}})(x-y{\sqrt {n}})}$$リングの標準 は${\displaystyle \mathbb {Z} [{\sqrt {n}}]}$そして、密接に関連する二次場については${\displaystyle \mathbb {Q} ({\sqrt {n}})}$したがって、整数のペア${\displaystyle (x,y)}$ペル方程式を解くのは、${\displaystyle x+y{\sqrt {n}}}$は、ノルム1の単位です。${\displaystyle \mathbb {Z} [{\sqrt {n}}]}$[ ^{21 ]}ディリクレの単位定理、すべて^の 単位は${\displaystyle \mathbb {Z} [{\sqrt {n}}]}$は、単一の基本単位のべき乗（および符号による乗算）として表現でき、ペル方程式のすべての解は基本解から生成できるという事実の代数的な言い換えである。^{[ 22 ]}基本単位は一般にペル方程式に似た方程式を解くことによって見つけることができるが、基本単位のノルムが 1 ではなく −1 であったり、係数が整数ではなく半整数であったりするため、必ずしもペル方程式自体の基本解に直接対応するとは限らない。

デマイヤーは、ペル方程式とチェビシェフ多項式との関連性について言及している。${\displaystyle T_{i}(x)}$そして${\displaystyle U_{i}(x)}$これらがそれぞれ第1種および第2種のチェビシェフ多項式である場合、これらの多項式は任意の多項式環においてペル方程式のある形式を満たす。${\displaystyle R[x]}$、 と${\displaystyle n=x^{2}-1}$: ^{[ 23 ]}$${\displaystyle T_{i}^{2}-(x^{2}-1)U_{i-1}^{2}=1.}$$ したがって、これらの多項式は、ペル方程式の基本解のべき乗を取るという標準的な手法によって生成することができる。 $${\displaystyle T_{i}+U_{i-1}{\sqrt {x^{2}-1}}=(x+{\sqrt {x^{2}-1}})^{i}.}$$ さらに、もし${\displaystyle (x_{i},y_{i})}$任意の整数ペル方程式の解は、${\displaystyle x_{i}=T_{i}(x_{1})}$そして${\displaystyle y_{i}=y_{1}U_{i-1}(x_{1})}$[ ^{24 ]​}

ペル方程式の解の一般的な展開${\displaystyle x^{2}-ny^{2}=1}$連続分数の観点から${\displaystyle {\sqrt {n}}}$解xとy はnの平方根の近似値であり、したがって二次無理数の連分数近似の特殊なケースであるため、提示することができる。^{[ 16 ]}

連分数との関係から、ペル方程式の解はモジュラー群の半群部分集合を形成することがわかる。したがって、例えばpとq がペル方程式を満たす場合、 $${\displaystyle {\begin{pmatrix}p&q\\nq&p\end{pmatrix}}}$$は、行列 式が1の行列です。このような行列の積は全く同じ形式をとるため、このような積はすべてペル方程式の解となります。これは、連続分数の連続収束が同じ性質を持つという事実から部分的に理解できます。p k ₋₁ / q _{k −1}とp _k / q _kが連続分数の2つの連続収束である場合、行列は $${\displaystyle {\begin{pmatrix}p_{k-1}&p_{k}\\q_{k-1}&q_{k}\end{pmatrix}}}$$

行列式は (−1) ^kです。

ストーマーの定理は、ペル方程式を適用して、素因数がすべて与えられた値より小さい正の整数である連続する滑らかな数のペアを見つける。 ^{[ 25 ] [ 26 ]}この理論の一部として、ストーマーはペル方程式の解間の可除性関係も調査した。特に、基本解以外の各解は、 nを割り切れない素因数を持つことを示した。^{[ 25 ]}