Pellsche Gleichung

Als Pellsche Gleichung (nach John Pell, 1611–1685) bezeichnet man eine diophantische Gleichung der Form

${\displaystyle x^{2}-n\cdot y^{2}=1}$

mit positiv ganzzahligem ${\displaystyle n\in \mathbb {N} \setminus \{0\}}$.

Ist ${\displaystyle n=k^{2}}$ eine Quadratzahl einer natürlichen Zahl ${\displaystyle k\in \mathbb {N} ^{+}}$, so besitzt die Gleichung offensichtlich nur die beiden trivialen Lösungen ${\displaystyle (\pm 1,\ 0)}$. Andernfalls gibt es unendlich viele Lösungen, die man mit Hilfe der Kettenbruchentwicklung von ${\displaystyle {\sqrt {n}}}$ bestimmen kann. Die verwandten Gleichungen ${\displaystyle x^{2}-n\cdot y^{2}=-1\,}$ bezeichnet man oft als negative Pellsche Gleichungen und ${\displaystyle x^{2}-n\cdot y^{2}=d\,}$ mit beliebigem ganzzahligen ${\displaystyle d\in \mathbb {Z} \setminus \{0\}}$ als verallgemeinerte Pellsche Gleichungen.

Die Gleichung wird John Pell fälschlicherweise zugeschrieben. Korrekter wäre die Bezeichnung Fermatsche Gleichung.^[1][2]

Die Gleichung war in Indien schon Brahmagupta im 7. und Bhaskara II. im 12. Jahrhundert bekannt. In Europa tauchte die Gleichung erst im 17. Jahrhundert auf. Die Lösung dieser Gleichung war als Problem von Pierre de Fermat in einem Brief an Bernard Frénicle de Bessy gestellt worden und 1657 als Problem veröffentlicht. Pell befasste sich nie mit der Lösung der Gleichung. Brouncker fand einige Lösungen (veröffentlicht im Commercium epistolicum of John Wallis 1658). Leonhard Euler stieß auf die Lösung von Brouncker in der lateinischen Ausgabe des Treatise of Algebra von John Wallis und benannte die Gleichung fälschlich nach Pell.^[3][4] Euler veröffentlichte zuerst 1732 über die Pell-Gleichung und fand später die Verbindung mit Kettenbrüchen (veröffentlicht 1765), die im Grunde schon hinter der Lösung von Brouncker steckt. Joseph-Louis Lagrange befasste sich nach Euler ausführlich mit der Gleichung und gab als Erster einen Beweis, dass es für jedes ${\displaystyle n}$ eine Lösung gibt, wobei Fermat möglicherweise auch einen Beweis hatte.^[5]

Das Auffinden aller Lösungen ist für spezielle ${\displaystyle n}$ äquivalent dazu, die Einheiten des Ganzheitsrings des reellquadratischen Zahlkörpers ${\displaystyle \mathbb {Q} ({\sqrt {n}})}$ zu finden. Nach dem Dirichletschen Einheitensatz hat die Einheitengruppe den Rang 1, d. h., es gibt eine Fundamentaleinheit (oder auch Grundeinheit) ${\displaystyle \varepsilon =x_{0}+y_{0}\cdot {\sqrt {n}},}$ mit der sich alle Lösungen als ${\displaystyle \pm \varepsilon ^{k},k\in \mathbb {N} }$ darstellen lassen.

Beispielsweise ist für ${\displaystyle n=2}$ die Einheit ${\displaystyle 1+1\cdot {\sqrt {2}}}$ eine Fundamentaleinheit und man kann die anderen Lösungen

${\displaystyle 3+2\cdot {\sqrt {2}},\ 7+5\cdot {\sqrt {2}},\ 17+12\cdot {\sqrt {2}},\ \ldots ,\ (1+1\cdot {\sqrt {2}})^{k}}$

aus ihr erzeugen.

Es sind folgende Eigenschaften der Lösungen erkennbar:

• Für alle ${\displaystyle n}$ ist existiert immer die triviale Lösung ${\displaystyle (1,\ 0)}$.
• Für ${\displaystyle n=0}$ gibt sind alle Paare ${\displaystyle (1,\ k)}$ weitere triviale Lösungen.
• Für ${\displaystyle n=k^{2}}$ mit ${\displaystyle k>0}$ existieren keine weiteren Lösungen.
  • Das Verhältnis ${\displaystyle {x_{i}}/{y_{i}}}$ konvergiert gegen ${\displaystyle {\sqrt {n}}}$.
  • Der Grenzwert des Wachstumskoeffizienten ${\displaystyle q=\lim _{i\rightarrow \infty }{x_{i+1}}/{x_{i}}}$ liegt knapp unter einer ganzen Zahl. Der „Fehler“ liegt auffällig in der Nähe von ${\displaystyle 1/q}$.
  • Die Summe ${\displaystyle q+1/q}$ ergibt eine ganze, gerade Zahl.
  • Diese Eigenschaften und „auffällige“ Nachkommastellen weisen darauf hin, dass sich ${\displaystyle q}$ in der Form ${\displaystyle a+b\cdot {\sqrt {n}}}$ darstellen lässt.

Die Kettenbruchentwicklung einer quadratisch irrationalen Zahl ${\displaystyle {\sqrt {n}}}$ ist unendlich und periodisch. ${\displaystyle {\sqrt {n}}}$ hat die Kettenbruchentwicklung ${\displaystyle {\sqrt {n}}=[b_{0};\ {\overline {b_{1},\dotsc ,b_{m}}}]}$ (siehe Periodische Kettenbrüche). Sei

${\displaystyle {\frac {x}{y}}=[b_{0};\ b_{1},\dotsc ,b_{m-1}]}$

mit ganzzahligen ${\displaystyle x,\ y}$, dann ist ${\displaystyle x,\ y}$ die kleinste Lösung der verallgemeinerten Pellschen Gleichung ${\displaystyle x^{2}-n\cdot y^{2}={(-1)}^{m}}$. Die anderen Lösungen lassen sich wie erwähnt daraus konstruieren.^[6] Auch alle weiteren

${\displaystyle {\frac {x_{k}}{y_{k}}}=[b_{0};\ b_{1},\dotsc ,b_{km-1}]}$

mit ${\displaystyle k\in \mathbb {N} }$ lösen ${\displaystyle x^{2}-n\cdot y^{2}={(-1)}^{km}}$.

Die negative Pellsche Gleichung ${\displaystyle x^{2}-n\cdot y^{2}=-1}$ hat genau dann

• eine Serie von Lösungen, wenn die Kettenbruchentwicklung von ${\displaystyle {\sqrt {n}}}$ eine ungerade Periode hat.
  • Das sind keinesfalls Zahlen der Form ${\displaystyle (k+1)^{2}-1=k^{2}+2k}$, deren Kettenbruchentwicklung ${\displaystyle [k;\ {\overline {1,2k}}]\;}$ lautet (offensichtlich Periode 2).
  • Das sind keinesfalls Zahlen der Form ${\displaystyle k^{2}}$, deren Kettenbruchentwicklung ${\displaystyle [k]\;}$ lautet (offensichtlich keine bzw. Periode 0).
  • Das sind u. A. alle Zahlen der Form ${\displaystyle k^{2}+1}$, deren Kettenbruchentwicklung ${\displaystyle [k;\ {\overline {2k}}]}$ lautet (offensichtlich Periode 1).
  • Das sind weiterhin die Zahlen ${\displaystyle 5,\ 13,\ 29,\ 41,\ 53,\ 58,\ 61,\ 73,\ 74,\ 85,\ 89,\ 97,\ldots }$
• genau die eine Lösung ${\displaystyle (0,\ 1)}$, wenn ${\displaystyle n=1}$ ist, da nur die Differenz der Quadratzahlen ${\displaystyle 0^{2}}$ und ${\displaystyle 1^{2}}$ die Differenz ${\displaystyle -1}$ ergibt.  ∎ 

Liste der Kettenbruchentwicklungen

${\displaystyle {\sqrt {0}}=[0]}$

${\displaystyle \color {SeaGreen}{\sqrt {1}}=[1]}$

${\displaystyle {\sqrt {2}}=[1;\ {\overline {\color {Red}2}}]}$

${\displaystyle {\sqrt {3}}=[1;\ {\overline {1,2}}]}$

${\displaystyle {\sqrt {4}}=[2]}$

${\displaystyle {\sqrt {5}}=[2;\ {\overline {\color {Red}4}}]}$

${\displaystyle {\sqrt {6}}=[2;\ {\overline {2,4}}]}$

${\displaystyle {\sqrt {7}}=[2;\ {\overline {1,1,1,4}}]\;}$

${\displaystyle {\sqrt {8}}=[2;\ {\overline {1,4}}]}$

${\displaystyle {\sqrt {9}}=[3]}$

${\displaystyle {\sqrt {10}}=[3;\ {\overline {\color {Red}6}}]}$

${\displaystyle {\sqrt {11}}=[3;\ {\overline {3,6}}]}$

${\displaystyle {\sqrt {12}}=[3;\ {\overline {2,6}}]}$

${\displaystyle {\sqrt {13}}=[3;\ {\overline {\color {Red}1,1,1,1,6}}]}$

${\displaystyle {\sqrt {14}}=[3;\ {\overline {1,2,1,6}}]}$

${\displaystyle {\sqrt {15}}=[3;\ {\overline {1,6}}]}$

${\displaystyle {\sqrt {16}}=[4]}$

${\displaystyle {\sqrt {17}}=[4;\ {\overline {\color {Red}8}}]}$

${\displaystyle {\sqrt {18}}=[4;\ {\overline {4,8}}]}$

${\displaystyle {\sqrt {19}}=[4;\ {\overline {2,1,3,1,2,8}}]\;}$

${\displaystyle {\sqrt {20}}=[4;\ {\overline {2,8}}]}$

${\displaystyle {\sqrt {21}}=[4;\ {\overline {1,1,2,1,1,8}}]\;}$

${\displaystyle {\sqrt {22}}=[4;\ {\overline {1,2,4,2,1}}]}$

${\displaystyle {\sqrt {23}}=[4;\ {\overline {1,3,1,8}}]}$

${\displaystyle {\sqrt {24}}=[4;\ {\overline {1,8}}]}$

${\displaystyle {\sqrt {25}}=[5]}$

${\displaystyle {\sqrt {26}}=[5;\ {\overline {\color {Red}10}}]}$

${\displaystyle {\sqrt {27}}=[5;\ {\overline {5,10}}]}$

${\displaystyle {\sqrt {28}}=[5;\ {\overline {3,2,3,10}}]}$

${\displaystyle {\sqrt {29}}=[5;\ {\overline {\color {Red}2,1,1,2,10}}]}$

${\displaystyle {\sqrt {30}}=[5;\ {\overline {2,10}}]}$

${\displaystyle {\sqrt {31}}=[5;\ {\overline {1,1,3,5,3,1,1,10}}]}$

${\displaystyle {\sqrt {32}}=[5;\ {\overline {1,1,1,10}}]}$

${\displaystyle {\sqrt {33}}=[5;\ {\overline {1,2,1,10}}]}$

${\displaystyle {\sqrt {34}}=[5;\ {\overline {1,4,1,10}}]}$

${\displaystyle {\sqrt {35}}=[5;\ {\overline {1,10}}]}$

${\displaystyle {\sqrt {36}}=[6]}$

${\displaystyle {\sqrt {37}}=[6;\ {\overline {\color {Red}12}}]}$

${\displaystyle {\sqrt {38}}=[6;\ {\overline {6,12}}]}$

${\displaystyle {\sqrt {39}}=[6;\ {\overline {4,12}}]}$

${\displaystyle {\sqrt {40}}=[6;\ {\overline {3,12}}]}$

${\displaystyle {\sqrt {41}}=[6;\ {\overline {\color {Red}2,2,12}}]}$

${\displaystyle {\sqrt {42}}=[6;\ {\overline {2,12}}]}$

${\displaystyle {\sqrt {43}}=[6;\ {\overline {1,1,3,1,5,1,3,1,1,12}}]\;}$

${\displaystyle {\sqrt {44}}=[6;\ {\overline {1,1,1,2,1,1,1}}]}$

${\displaystyle {\sqrt {45}}=[6;\ {\overline {1,2,2,2,1,12}}]}$

${\displaystyle {\sqrt {46}}=[6;\ {\overline {1,3,1,1,2,6,2,1,1,3,1,12}}]}$

${\displaystyle {\sqrt {47}}=[6;\ {\overline {1,5,1,12}}]}$

${\displaystyle {\sqrt {48}}=[6;\ {\overline {1,12}}]}$

${\displaystyle {\sqrt {49}}=[7]}$

${\displaystyle {\sqrt {50}}=[7;\ \color {Red}{\overline {14}}]}$

${\displaystyle {\sqrt {51}}=[7;\ {\overline {7,14}}]}$

${\displaystyle {\sqrt {52}}=[7;\ {\overline {4,1,2,1,4,14}}]}$

${\displaystyle {\sqrt {53}}=[7;\ \color {Red}{\overline {3,1,1,3,14}}]\;}$

${\displaystyle {\sqrt {54}}=[7;\ {\overline {2,1,6,1,2,14}}]}$

${\displaystyle {\sqrt {55}}=[7;\ {\overline {2,2,2,14}}]}$

${\displaystyle {\sqrt {56}}=[7;\ {\overline {2,14}}]}$

${\displaystyle {\sqrt {57}}=[7;\ {\overline {1,1,4,1,1,14}}]}$

${\displaystyle {\sqrt {58}}=[7;\ \color {Red}{\overline {1,1,1,1,1,1,14}}]}$

${\displaystyle {\sqrt {59}}=[7;\ {\overline {1,2,7,2,1,14}}]}$

Das ist für 1, 2, 5, 10, 13, 17, 26, 29, 37, 41, 50, 53, 58, 61, 65, 73, 74, 82, 85, 89, 97, ... der Fall (siehe Folge A031396 in OEIS, außer die 1).

Eine notwendige, aber nicht hinreichende Bedingung (z. B. ${\displaystyle 34=5^{2}+3^{2}}$ hat keine Lösung) dafür ist, dass ${\displaystyle n}$ die Summe von zwei Quadratzahlen ist.^[7]

Wir wollen die Gleichung

${\displaystyle x^{2}-13\cdot y^{2}=+1}$

lösen, d. h. ${\displaystyle x^{2}-n\cdot y^{2}=+1\,}$ für ${\displaystyle n=13}$.

All erstes benötigen wir die Kettenbruchentwicklung für ${\displaystyle {\sqrt {n}}\,}$. Diese berechnet sich durch rekursives Anwenden folgender Schritte:

• Berechnung von ${\displaystyle a_{k}}$: Dies ist der Wert, den wir zur genauen Darstellung von ${\displaystyle {\sqrt {n}}}$ durch einen hier abgebrochenen Kettenbruch benötigen würden.

Im ersten Schritt ist ${\displaystyle a_{0}}$ der Ausgangsterm ${\displaystyle {\sqrt {n}}}$, in den folgenden ist ${\displaystyle a_{k}}$ der Restterm ${\displaystyle {\tfrac {1}{x_{k-1}}}}$.

Der Nenner der Form ${\displaystyle {\sqrt {r}}-s}$ wird durch Multiplikation mit der konjugierten Wurzel ${\displaystyle {\sqrt {r}}+s}$ ganzzahlig gemacht, anschließend wird, wenn möglich, gekürzt.

• Berechnung von ${\displaystyle b_{k}}$: Dies ist der ganzzahlige Teil (Vorkommastellen) von ${\displaystyle a_{k}}$. Durch Einsetzen von ${\displaystyle \lfloor {\sqrt {n}}\rfloor }$ für ${\displaystyle {\sqrt {n}}}$ kann man das Abrunden von ${\displaystyle a_{k}}$ unter Umgehung von irrationalen Zahlen durchführen.
• Berechnung von ${\displaystyle x_{k}}$: Dies ist der Rest (Nachkommastellen) von ${\displaystyle a_{k}}$ und berechnet sich zu ${\displaystyle x_{k}=a_{k}-b_{k}}$.

Erhalten wir hierbei ein schon mal vorgekommenes ${\displaystyle x_{j}}$, können wird die Entwicklung hier abbrechen, die Kettenbruchentwicklung ist ab hier periodisch.

• Die Kettenbruchentwicklung entsteht aus den Werten für ${\displaystyle b}$ und lautet ${\displaystyle [b_{0};\ b_{1},b_{2},b_{3},b_{4},b_{5},\ldots ]}$.
• Die Rechnung verläuft dann so:

${\displaystyle {\begin{array}{llllll}a_{0}={\sqrt {n}}={\sqrt {13}}=&={\frac {{\sqrt {13}}+0}{1}}&=3{,}60\ldots ,&b_{0}=\lfloor a_{0}\rfloor =\left\lfloor {\tfrac {3+0}{1}}\right\rfloor =\mathbf {3} ,&x_{0}=a_{0}-b_{0}={\frac {{\sqrt {13}}+0}{1}}-3&={\frac {{\sqrt {13}}-3}{1}}\\a_{1}={\frac {1}{x_{0}}}={\frac {1}{{\sqrt {13}}-3}}={\frac {{\sqrt {13}}+3}{({\sqrt {13}}-3)({\sqrt {13}}+3)}}&={\frac {{\sqrt {13}}+3}{4}}&=1{,}65\ldots ,&b_{1}=\lfloor a_{1}\rfloor =\left\lfloor {\tfrac {3+3}{4}}\right\rfloor =\mathbf {1} ,&x_{1}=a_{1}-b_{1}={\frac {{\sqrt {13}}+3}{4}}-1&={\frac {{\sqrt {13}}-1}{4}}\\a_{2}={\frac {1}{x_{1}}}={\frac {4}{{\sqrt {13}}-1}}={\frac {4({\sqrt {13}}+1)}{({\sqrt {13}}-1)({\sqrt {13}}+1)}}={\frac {4({\sqrt {13}}+1)}{12}}&={\frac {{\sqrt {13}}+1}{3}}&=1{,}53\ldots ,&b_{2}=\lfloor a_{2}\rfloor =\left\lfloor {\tfrac {3+1}{3}}\right\rfloor =\mathbf {1} ,&x_{2}=a_{2}-b_{2}={\frac {{\sqrt {13}}+1}{3}}-1&={\frac {{\sqrt {13}}-2}{3}}\\a_{3}={\frac {1}{x_{2}}}={\frac {3}{{\sqrt {13}}-2}}={\frac {3({\sqrt {13}}+2)}{({\sqrt {13}}-2)({\sqrt {13}}+2)}}={\frac {3({\sqrt {13}}+2)}{9}}&={\frac {{\sqrt {13}}+2}{3}}&=1{,}86\ldots ,&b_{3}=\lfloor a_{3}\rfloor =\left\lfloor {\tfrac {3+2}{3}}\right\rfloor =\mathbf {1} ,&x_{3}=a_{3}-b_{3}={\frac {{\sqrt {13}}+2}{3}}-1&={\frac {{\sqrt {13}}-1}{3}}\\a_{4}={\frac {1}{x_{3}}}={\frac {3}{{\sqrt {13}}-1}}={\frac {3({\sqrt {13}}+1)}{({\sqrt {13}}-1)({\sqrt {13}}+1)}}={\frac {3({\sqrt {13}}+1)}{12}}&={\frac {{\sqrt {13}}+1}{4}}&=1{,}15\ldots ,&b_{4}=\lfloor a_{4}\rfloor =\left\lfloor {\tfrac {3+1}{4}}\right\rfloor =\mathbf {1} ,&x_{4}=a_{4}-b_{4}={\frac {{\sqrt {13}}+1}{4}}-1&={\frac {{\sqrt {13}}-3}{4}}\\a_{5}={\frac {1}{x_{4}}}={\frac {4}{{\sqrt {13}}-3}}={\frac {4({\sqrt {13}}+3)}{({\sqrt {13}}-3)({\sqrt {13}}+3)}}={\frac {4({\sqrt {13}}+3)}{4}}&={\frac {{\sqrt {13}}+3}{1}}&=6{,}60\ldots ,&b_{5}=\lfloor a_{5}\rfloor =\left\lfloor {\tfrac {3+3}{1}}\right\rfloor =\mathbf {6} ,&x_{5}=a_{5}-b_{5}={\frac {{\sqrt {13}}+3}{1}}-6&=\underbrace {\frac {{\sqrt {13}}-3}{1}} _{=\;x_{0}}\\a_{6}={\frac {1}{x_{5}}}={\frac {1}{x_{0}}}=a_{1}&&&b_{6}=\lfloor a_{1}\rfloor =\qquad \qquad \mathbf {1} ,&x_{6}=a_{6}-b_{6}=\quad a_{1}-b_{1}&=x_{1}\\\ldots \end{array}}}$

Da ${\displaystyle x_{5}=x_{0}}$ ist, wiederholen sich ab hier die Werte periodisch und wir können die Entwicklung abbrechen.

Die Kettenbruchentwicklung für ${\displaystyle {\sqrt {13}}}$ ist daher

${\displaystyle {\sqrt {13}}\;=\;[3;\ 1,1,1,1,6,1,1,1,1,6,\ldots ]\;=\;[3;\ {\overline {1,1,1,1,6}}]}$

und hat die Periode ${\displaystyle l=5}$.

Die Näherungsbrüche der Kettenbruchentwicklung erhalten wir durch Einsetzen der Kettenbruchentwicklung in die Bildungsvorschrift. Die Näherungsbrüche bei Abbruch nach ${\displaystyle k}$ Stellen lauten:

${\displaystyle {\sqrt {13}}\;\approx \;\mathbf {3} ,\ \mathbf {3} +{\tfrac {1}{\mathbf {1} }},\ \mathbf {3} +{\tfrac {1}{\mathbf {1} +{\tfrac {1}{\mathbf {1} }}}},\ \mathbf {3} +{\tfrac {1}{\mathbf {1} +{\tfrac {1}{\mathbf {1} +{\tfrac {1}{\mathbf {1} }}}}}},\ \mathbf {3} +{\tfrac {1}{\mathbf {1} +{\tfrac {1}{\mathbf {1} +{\tfrac {1}{\mathbf {1} +{\tfrac {1}{\mathbf {1} }}}}}}}},\ \mathbf {3} +{\tfrac {1}{\mathbf {1} +{\tfrac {1}{\mathbf {1} +{\tfrac {1}{\mathbf {1} +{\tfrac {1}{\mathbf {1} +{\tfrac {1}{\mathbf {6} }}}}}}}}}},\ \ldots }$

Nach Umwandlung in gewöhnliche Brüche interessieren jetzt die Werte nach Abbruch nach einem ganzzahligen Vielfachen von ${\displaystyle l}$:

${\displaystyle {\sqrt {13}}\;\approx \;\underbrace {{{} \atop {}}0,} _{k=0}{\frac {3}{1}},\ {\frac {4}{1}},\ {\frac {7}{2}},\ {\frac {11}{3}},\underbrace {\ {\frac {18}{5}},} _{k=5=l}\ {\frac {119}{33}},\ {\frac {137}{38}},\ {\frac {256}{71}},\ {\frac {393}{109}},\underbrace {\ {\frac {649}{180}},} _{k=10=2l}\ {\frac {4287}{1189}},\ {\frac {4936}{1369}},\ {\frac {9223}{2558}},\ {\frac {14159}{3927}},\ \underbrace {\frac {23382}{6485}} _{k=15=2l},\ {\frac {154451}{42837}},\ {\frac {177833}{49322}},\ \dots }$

und findet an den Stellen ${\displaystyle k=0}$, ${\displaystyle \;k=5}$, ${\displaystyle \;k=10}$ und ${\displaystyle k=15\,}$

${\displaystyle x_{0}}$	${\displaystyle =}$	${\displaystyle 1,}$	${\displaystyle y_{0}}$	${\displaystyle =}$	${\displaystyle 0}$	die Triviallösung von ${\displaystyle x^{2}-13\cdot y^{2}=+1}$
${\displaystyle x_{1,(-1)}}$	${\displaystyle =}$	${\displaystyle 18,}$	${\displaystyle y_{1,(-1)}}$	${\displaystyle =}$	${\displaystyle 5}$	die erste Lösung der negativen Pellschen Gleichung ${\displaystyle x^{2}-13\cdot y^{2}=-1}$
${\displaystyle x_{1}}$	${\displaystyle =}$	${\displaystyle 649,}$	${\displaystyle y_{0}}$	${\displaystyle =}$	${\displaystyle 180}$	die erste (nicht triviale) Lösung von ${\displaystyle x^{2}-13\cdot y^{2}=+1}$
${\displaystyle x_{2,(-1)}}$	${\displaystyle =}$	${\displaystyle 23382,\;}$	${\displaystyle y_{2,(-1)}}$	${\displaystyle =}$	${\displaystyle 6485\;}$	die zweite Lösung der negativen Pellschen Gleichung von ${\displaystyle x^{2}-13\cdot y^{2}=-1}$

Weiter stellt man fest, dass für ${\displaystyle n=13}$ jedes Element der abgebrochenen Kettenbruchentwicklung der Länge ${\displaystyle k=5l,\ l\in \mathbb {N} }$ eine Lösung einer Pellschen Gleichung mit rechter Seite ${\displaystyle d=\pm 1}$ ist.

Die Näherungsbrüche dazwischen stellen einige (aber nicht alle!) Lösungen der verallgemeinerten Pellschen Gleichung mit rechter Seite ${\displaystyle d=\pm 3}$ und ${\displaystyle \pm 4}$ dar.

k	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
Bruch bzw. (x, y)	${\displaystyle {\frac {3}{1}}}$	${\displaystyle {\frac {4}{1}}}$	${\displaystyle {\frac {7}{2}}}$	${\displaystyle {\frac {11}{3}}}$	${\displaystyle {\frac {18}{5}}}$	${\displaystyle {\frac {119}{33}}}$	${\displaystyle {\frac {137}{38}}}$	${\displaystyle {\frac {256}{71}}}$	${\displaystyle {\frac {393}{109}}}$	${\displaystyle {\frac {649}{180}}}$	${\displaystyle {\frac {4287}{1189}}}$	${\displaystyle {\frac {4936}{1369}}}$	${\displaystyle {\frac {9223}{2558}}}$	${\displaystyle {\frac {14159}{3927}}}$	${\displaystyle {\frac {23382}{6485}}}$	${\displaystyle {\frac {154451}{42837}}}$	${\displaystyle {\frac {177833}{49322}}}$
Lösung für d =	(x₀, y₀) −4	(x₀, y₀) +3	(x₀, y₀) −3	(x₀, y₀) +4	(x₀, y₀) −1	(x₁, y₁) +4	(x₁, y₁) −3	(x₁, y₁) +3	(x₂, y₂) −4	(x₀, y₀) +1	(x₃, y₃) −4	(x₂, y₂) +3	(x₃, y₃) −3	(x₄, y₄) +4	(x₁, y₁) −1	(x₅, y₅) +4	(x₄, y₄) −3

#include <stdio.h>
#include <stdarg.h>
#include <cmath>
#include <vector>
#include <cstdint>
#include <stdexcept>
#include <utility>

using namespace std;
using i64 = int64_t;
using u64 = uint64_t;

static void log (const char* format, ...)
{
    if (1)
    {
        va_list  args;
        va_start(args, format);
        vprintf (format, args);
        va_end  (args);
    }
}

vector<u64> const Fahrradkettenbruch (u64 const n)
{
    log ("Kettenbruch-Entwicklung von sqrt %llu\n\n", n);

    u64 const   b0 = (u64)sqrt(n);
    u64         b  = b0;
    u64         m  = 0;
    u64         d  = 1;
    vector<u64> cfs;

    cfs.push_back (b);

    log ("  b%-2d =%3lld = (sqrt %lld +%4lld) / %lld\n", 0, b, n, m, d);

    for (int i = 1; ; i++)
    {
        m = d * b - m;
        d = (n - m * m) / d;
        if (d == 0)
            break;           // Abbruch, falls d = 0 (n ist ein Quadrat)
        b = (b0 + m) / d;
        cfs.push_back (b);

        log ("  b%-2d =%3lld = (sqrt %lld +%4lld) / %lld\n", i, b, n, m, d);

        if (b == 2*b0) break;  // Periodenende erkennen
    }
    return cfs;
}

pair <u64, u64> SolvePell (u64 const n, i64 const d)  // Funktion zur Berechnung der Lösung der Pellschen Gleichung
{
    auto cfs = Fahrradkettenbruch (n);
    u64  p0  = 1     , q0 = 0;
    u64  p1  = cfs[0], q1 = 1;

    log ("\nBerechnung der Naeherungsbrueche\n");
    log (                "  p%-2d = %lld\n  q%-2d = %lld\n\n",            0, p0, 0, q0);
    log ("  b%-2d = %lld\n  p%-2d = %lld\n  q%-2d = %lld\n\n", 0, cfs[0], 1, p1, 1, q1);

    for (int i = 1; ; i++)
    {
        u64 const b = cfs [(i-1) % (cfs.size()-1) + 1];
        u64 const p = b*p1 + p0;
        u64 const q = b*q1 + q0;
        if (1.0*b*p1 + p0 > 0xFFFFFFFFFFFFFFFF || 1.0*b*q1 + q0 > 0xFFFFFFFFFFFFFFFF)
        {
            log ("\n\nOverflow u64\n");
            return { 0, 0 };
        }

        log ("  b%-2d = %lld\n  p%-2d = %lld*%lld + %lld = %lld\n  q%-2d = %lld*%lld + %lld = %lld\n", i, b, i, b, p1, p0, p, i, b, q1, q0, q);

        p0 = p1;
        q0 = q1;
        p1 = p;
        q1 = q;

        i64 const dd = p1 * p1 - n * q1 * q1;
        log ("    -->%+4lld = %llu^2 - %llu * %llu^2\n", dd, p1, n, q1);

        if (dd == d) return { p1, q1 };
    }
}

void SolveAndPrint (u64 const n, i64 const d)
{
    log ("\n=== Berechnung fuer x^2 - %llu y^2 = %lld ===\n", n, d);
    auto const [x, y] = SolvePell (n, d);
    if (d == x*x - n * y*y)
        printf ("\nDie kleinste Loesung der Pellschen Gleichung x^2 - %lld y^2 = %+lld ist\n"
                "  x = %llu\n  y = %llu\n", n, d, x, y);
}

int main (int argc, char** argv)
{
    SolveAndPrint (argc < 2 ? 13 : ::atoll (argv[1]),   // n, default ist 13
                   argc < 3 ? +1 : ::atoll (argv[2]));  // d, default ist +1
    return 0;
}

Ist die kleinste nichttriviale Lösung ${\displaystyle (x_{0},\ y_{0})}$ bekannt, so lassen sich daraus alle weiteren nichttrivialen Lösungen bestimmen.^[8]

Die dahinterliegende Bildungsvorschrift (zum Beweis) lautet:

${\displaystyle c_{k}=x_{k}+y_{k}\cdot {\sqrt {n}}\ =\ (x_{0}+y_{0}\cdot {\sqrt {n}})^{k}}$.

Zum einen besteht, da die rechte Seite eine Potenz ist, die Möglichkeit einer rekursiven Bildungsvorschrift über ${\displaystyle z^{k+1}=z^{k}\cdot z^{1}}$, was

${\displaystyle {\begin{array}{rcl}x_{k+1}+y_{k+1}\cdot {\sqrt {n}}&=&(x_{k}+y_{k}\cdot {\sqrt {n}})\cdot (x_{0}+y_{0}\cdot {\sqrt {n}})\\x_{k+1}+y_{k+1}\cdot {\sqrt {n}}&=&(x_{0}\cdot x_{k}+{\sqrt {n}}\cdot {\sqrt {n}}\cdot y_{0}\cdot y_{k})\ +\ (y_{0}\cdot x_{k}+x_{0}\cdot y_{k})\cdot {\sqrt {n}}\\&=&(x_{0}\cdot x_{k}+n\cdot y_{0}\cdot y_{k})\ +\ (y_{0}\cdot x_{k}+x_{0}\cdot y_{k})\cdot {\sqrt {n}}\end{array}}}$

ergibt und sich durch Koeffizientenvergleich in die zwei Gleichungen aufspalten lässt:

${\displaystyle {\begin{array}{rcl}x_{k+1}&=&x_{0}\cdot x_{k}\ +\ n\cdot y_{0}\cdot y_{k}\\y_{k+1}&=&y_{0}\cdot x_{k}\ +\ \;\;x_{0}\;\;\ \cdot y_{k}\\\end{array}}}$

auch darstellbar als Matrizenmultiplikation

${\displaystyle {\begin{pmatrix}x_{k+1}\\y_{k+1}\\\end{pmatrix}}={\begin{pmatrix}x_{0}&n\cdot y_{0}\\y_{0}&x_{0}\\\end{pmatrix}}\cdot {\begin{pmatrix}x_{k}\\y_{k}\\\end{pmatrix}}}$.

Die Lösungen können auch explizit mit folgenden Formeln berechnet werden:^[9]

${\displaystyle {\begin{aligned}x_{k}={\frac {1}{2}}\qquad \!&\cdot {\Big (}(x_{0}\!+\!y_{0}\!\cdot \!{\sqrt {n}})^{k}\ +\ (x_{0}\!-\!y_{0}\!\cdot \!{\sqrt {n}})^{k}{\Big )}\\y_{k}={\frac {1}{2\!\cdot \!{\sqrt {n}}}}&\cdot {\Big (}(x_{0}\!+\!y_{0}\!\cdot \!{\sqrt {n}})^{k}\ -\ (x_{0}\!-\!y_{0}\!\cdot \!{\sqrt {n}})^{k}{\Big )}\\\end{aligned}}}$

Hierbei wird für die Separation der Fundamentaleinheit ${\displaystyle \varepsilon =x+y\cdot {\sqrt {n}}\ }$ folgendes ausgenutzt:

• Der erste Term in der großen Klammer sammelt alle ganzzahligen Koeffizienten zweimal auf, die Vielfachen von ${\displaystyle {\sqrt {n}}}$ kürzen sich raus,

der zweite Term in der großen Klammer sammelt alle Vielfachen von ${\displaystyle {\sqrt {n}}}$ zweimal auf, die ganzzahligen kürzen sich raus.

• ${\displaystyle x_{k}+y_{k}\cdot {\sqrt {n}}\;}$ ergibt wieder ${\displaystyle \;c_{k}=(x_{0}+y_{0}\cdot {\sqrt {n}})^{k}}$: