Pellsche Gleichung

Lösungen der Pellsche Gleichung für $n=2$:
 Als diophantische Gleichung sind nur ganzzahlige Werte (Schnittpunkte von Gitterlinien) Lösungen. Davon sind hier mit (±1, 0) und (±3, ±2) die sechs kleinsten zu sehen.
Es gibt unendlich viele weitere wie (±17, ±12), (±99, ±70), (±577, ±408), (±3363, ±2378), (±19601, ±13860), ...

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

$x^2-n\cdot y^2=1$

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

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

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. 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 $n$ eine Lösung gibt, wobei Fermat möglicherweise auch einen Beweis hatte.

Algebraische Zahlentheorie

Das Auffinden aller Lösungen ist für spezielle $n$ äquivalent dazu, die Einheiten des Ganzheitsrings des reellquadratischen Zahlkörpers $\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) $\epsilon =x_0+y_0\cdot \sqrt{n},$ mit der sich alle Lösungen als $\pm {\epsilon }^k,k\in \mathbb{N}$ darstellen lassen.

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

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

aus ihr erzeugen.

Lösungen

Wichtige Vorbemerkung

Da $x^2=(-x{)}^2$ und $y^2=(-y{)}^2$ ist, treten Lösungen der Gleichung

$x^2+n\cdot y^2=d$

immer als symmetrisch zum Koordinatenursprung liegende Lösungsquadrupel $(x,y),(x,-y),(-x,y)$ und $(-x,-y)$ auf, die im Falle von $x=0$ und/oder $y=0$ auch Mehrfachlösungen sein können.
Siehe dazu die Grafik am Anfang des Artikels:  6 ganzzahlige Lösungen der Pellsche Gleichung für $n=2$

Dies wird im folgenden Text aus Gründen der Kompaktheit der Darstellung bis auf wenige Ausnahmen nicht weiter erwähnt und es werden nur die Lösungen $(x,y)$ mit $x,y\ge 0$ betrachtet.

Welche Lösungen hat die Gleichung?

Es sind folgende Eigenschaften der Lösungen erkennbar:

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

n	Anzahl der Lösungen 0 ≤ y < 1014	Trivial- Lösung	weitere Lösungen (xi, yi) für d = 1	lim xi / yi	lim xi+1 / xi = q	q + 1/q	a	b
0	1014	(1, 0)	(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (1, 10), (1, 11), (1, 12), (1,13), ...	0,000000	Vorlage:01,000000	2	1	0
1	1	(1, 0)	keine
2	19	(1, 0)	(3, 2), (17, 12), (99, 70), (577, 408), (3363, 2378), (19601, 13860), (114243, 80782), ...	1,414214	Vorlage:05,828427	6	3	2
3	26	(1, 0)	(2, 1), (7, 4), (26, 15), (97, 56), (362, 209), (1351, 780), (5042, 2911), (18817, 10864), ...	1,732051	Vorlage:03,732051	4	2	1
4	1	(1, 0)	keine
5	12	(1, 0)	(9, 4), (161, 72), (2889, 1292), (51841, 23184), (930249, 416020), (16692641, 7465176), ...	2,236068	Vorlage:017,944272	18	9	4
6	15	(1, 0)	(5, 2), (49, 20), (485, 198), (4801, 1960), (47525, 19402), (470449, 192060), ...	2,449490	Vorlage:09,898979	10	5	2
7	13	(1, 0)	(8, 3), (127, 48), (2024, 765), (32257, 12192), (514088, 194307), (8193151, 3096720), ...	2,645751	Vorlage:015,937254	16	8	3
8	20	(1, 0)	(3, 1), (17, 6), (99, 35), (577, 204), (3363, 1189), (19601, 6930), (114243, 40391), ...	2,828427	Vorlage:05,828427	6	3	1
9	1	(1, 0)	keine
10	10	(1, 0)	(19, 6), (721, 228), (27379, 8658), (1039681, 328776), (39480499, 12484830), ...	3,162278	Vorlage:037,973666	38	19	6
11	12	(1, 0)	(10, 3), (199, 60), (3970, 1197), (79201, 23880), (1580050, 476403), (31521799, 9504180), ...	3,316625	Vorlage:019,949874	20	10	3
12	13	(1, 0)	(7, 2), (97, 28), (1351, 390), (18817, 5432), (262087, 75658), (3650401, 1053780), ...	3,464102	Vorlage:013,928203	14	7	2
13	5	(1, 0)	(649, 180), (842401, 233640), (1093435849, 303264540), (1419278889601, 393637139280)	3,605551	1297,999230	1298	649	180
14	11	(1, 0)	(15, 4), (449, 120), (13455, 3596), (403201, 107760), (12082575, 3229204), ...	3,741657	Vorlage:029,966630	30	15	4
15	17	(1, 0)	(4, 1), (31, 8), (244, 63), (1921, 496), (15124, 3905), (119071, 30744), (937444, 242047), ...	3,872983	Vorlage:07,872983	8	4	1
16	1	(1, 0)	keine
17	9	(1, 0)	(33, 8), (2177, 528), (143649, 34840), (9478657, 2298912), (625447713, 151693352), ...	4,123106	Vorlage:065,984845	66	33	8
18	10	(1, 0)	(17, 4), (577, 136), (19601, 4620), (665857, 156944), (22619537, 5331476), ...	4,242641	Vorlage:033,970563	34	17	4

Lösung mit Hilfe der Kettenbruchentwicklung

Die Kettenbruchentwicklung einer quadratisch irrationalen Zahl $\sqrt{n}$ ist unendlich und periodisch. $\sqrt{n}$ hat die Kettenbruchentwicklung $\sqrt{n}=[b_0;\overline{b_1,\dots ,b_m}]$ (siehe Periodische Kettenbrüche). Sei

$\frac{x}{y}=[b_0;b_1,\dots ,b_{m-1}]$

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

$\frac{x_k}{y_k}=[b_0;b_1,\dots ,b_{km-1}]$

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

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

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

Liste der Kettenbruchentwicklungen

$\sqrt{0}=[0]$

$\sqrt{1}=[1]$

$\sqrt{2}=[1;\bar{2}]$

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

$\sqrt{4}=[2]$

$\sqrt{5}=[2;\bar{4}]$

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

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

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

$\sqrt{9}=[3]$

$\sqrt{10}=[3;\bar{6}]$

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

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

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

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

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

$\sqrt{16}=[4]$

$\sqrt{17}=[4;\bar{8}]$

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

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

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

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

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

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

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

$\sqrt{25}=[5]$

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

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

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

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

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

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

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

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

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

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

$\sqrt{36}=[6]$

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

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

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

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

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

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

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

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

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

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

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

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

$\sqrt{49}=[7]$

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

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

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

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

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

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

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

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

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

$\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 Vorlage:OEIS, außer die 1).

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

Beispiel für die Lösung mittels Kettenbruchentwicklung

Wir wollen die Gleichung

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

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

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

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

Im ersten Schritt ist $a_0$ der Ausgangsterm $\sqrt{n}$, in den folgenden ist $a_k$ der Restterm $\frac{1}{x_{k-1}}$.

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

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

Erhalten wir hierbei ein schon mal vorgekommenes $x_j$, können wird die Entwicklung hier abbrechen, die Kettenbruchentwicklung ist ab hier periodisch.

• Die Kettenbruchentwicklung entsteht aus den Werten für $b$ und lautet $[b_0;b_1,b_2,b_3,b_4,b_5,\dots ]$.
• Die Rechnung verläuft dann so:

$\begin{array}{cccccc}{a}_0=\sqrt{n}=\sqrt{13}=& =\frac{\sqrt{13}+0}{1}& =3,60\dots ,& b_0=\lfloor a_0\rfloor =\lfloor \frac{3+0}{1}\rfloor =\mathrm{𝟑},& 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\dots ,& b_1=\lfloor a_1\rfloor =\lfloor \frac{3+3}{4}\rfloor =\mathrm{𝟏},& 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\dots ,& b_2=\lfloor a_2\rfloor =\lfloor \frac{3+1}{3}\rfloor =\mathrm{𝟏},& 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\dots ,& b_3=\lfloor a_3\rfloor =\lfloor \frac{3+2}{3}\rfloor =\mathrm{𝟏},& 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\dots ,& b_4=\lfloor a_4\rfloor =\lfloor \frac{3+1}{4}\rfloor =\mathrm{𝟏},& 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\dots ,& b_5=\lfloor a_5\rfloor =\lfloor \frac{3+3}{1}\rfloor =\mathrm{𝟔},& x_5=a_5-b_5=\frac{\sqrt{13}+3}{1}-6& =\underset{=x_0}{\underbrace{\frac{\sqrt{13}-3}{1}}}\\ a_6=\frac{1}{x_5}=\frac{1}{x_0}=a_1& & & b_6=\lfloor a_1\rfloor =\mathrm{𝟏},& x_6=a_6-b_6=a_1-b_1& =x_1\\ \dots \end{array}$

Da $x_5=x_0$ ist, wiederholen sich ab hier die Werte periodisch und wir können die Entwicklung abbrechen.

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

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

und hat die Periode $l=5$.

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

$\sqrt{13}\approx \mathrm{𝟑},\mathrm{𝟑}+\frac{1}{\mathrm{𝟏}},\mathrm{𝟑}+\frac{1}{\mathrm{𝟏}+\frac{1}{\mathrm{𝟏}}},\mathrm{𝟑}+\frac{1}{\mathrm{𝟏}+\frac{1}{\mathrm{𝟏}+\frac{1}{\mathrm{𝟏}}}},\mathrm{𝟑}+\frac{1}{\mathrm{𝟏}+\frac{1}{\mathrm{𝟏}+\frac{1}{\mathrm{𝟏}+\frac{1}{\mathrm{𝟏}}}}},\mathrm{𝟑}+\frac{1}{\mathrm{𝟏}+\frac{1}{\mathrm{𝟏}+\frac{1}{\mathrm{𝟏}+\frac{1}{\mathrm{𝟏}+\frac{1}{\mathrm{𝟔}}}}}},\dots$

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

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

und findet an den Stellen $k=0$, $k=5$, $k=10$ und $k=15$

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

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

Die Näherungsbrüche dazwischen stellen einige (aber nicht alle!) Lösungen der verallgemeinerte Pellsche Gleichung mit rechter Seite $d=\pm 3$ und $\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)	$\frac{3}{1}$	$\frac{4}{1}$	$\frac{7}{2}$	$\frac{11}{3}$	$\frac{18}{5}$	$\frac{119}{33}$	$\frac{137}{38}$	$\frac{256}{71}$	$\frac{393}{109}$	$\frac{649}{180}$	$\frac{4287}{1189}$	$\frac{4936}{1369}$	$\frac{9223}{2558}$	$\frac{14159}{3927}$	$\frac{23382}{6485}$	$\frac{154451}{42837}$	$\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

Programm zur Berechnung der Lösung für der Pellschen Gleichung

#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;
}

Generieren weiterer Lösungen

Ist die kleinste nichttriviale Lösung $(x_0,y_0)$ bekannt, so lassen sich daraus alle weiteren nichttrivialen Lösungen bestimmen.

Die dahinterliegende Bildungsvorschrift (zum Beweis) lautet:

$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 $z^{k+1}=z^k\cdot z^1$, was

$\begin{array}{ccc}{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:

$\begin{array}{ccc}{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

$\left(\begin{array}{c}{x}_{k+1}\\ y_{k+1}\end{array}\right)=\left(\begin{array}{cc}{x}_0& n\cdot y_0\\ y_0& x_0\end{array}\right)\cdot \left(\begin{array}{c}{x}_k\\ y_k\end{array}\right)$.

Die Lösungen können auch explizit mit folgenden Formeln berechnet werden:

$\begin{array}{cc}{x}_k=\frac{1}{2}& \cdot ((x_0+y_0\cdot \sqrt{n}{)}^k+(x_0-y_0\cdot \sqrt{n}{)}^k)\\ y_k=\frac{1}{2\cdot \sqrt{n}}& \cdot ((x_0+y_0\cdot \sqrt{n}{)}^k-(x_0-y_0\cdot \sqrt{n}{)}^k)\\ \end{array}$

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

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

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

• $x_k+y_k\cdot \sqrt{n}$ ergibt wieder $c_k=(x_0+y_0\cdot \sqrt{n}{)}^k$:

  Ausführlicher Beweis der beiden Aussagen

 Aussage 1

Betrachten wir hierzu erst einmal die beiden je zweimal vorkommenden Terme:

$c_k=(x_0+y_0\cdot \sqrt{n}{)}^k=\sum _{i=0}^k(\genfrac{}{}{0ex}{}{k}{i})x_0^{k-i}\cdot (+y_0\cdot \sqrt{n}{)}^i=\sum _{\genfrac{}{}{0ex}{}{i=0}{i\text{ gerade}}}^k(\genfrac{}{}{0ex}{}{k}{i})x_0^{k-i}\cdot (+y_0\cdot \sqrt{n}{)}^i+\sum _{\genfrac{}{}{0ex}{}{i=0}{i\text{ ungerade}}}^k(\genfrac{}{}{0ex}{}{k}{i})x_0^{k-i}\cdot (+y_0\cdot \sqrt{n}{)}^i=\sum _{\genfrac{}{}{0ex}{}{i=0}{i\text{ gerade}}}^k(\genfrac{}{}{0ex}{}{k}{i})x_0^{k-i}\cdot y_0^i\cdot n^{\frac{i}{2}}+\sqrt{n}\cdot \sum _{\genfrac{}{}{0ex}{}{i=0}{i\text{ ungerade}}}^k(\genfrac{}{}{0ex}{}{k}{i})x_0^{k-i}\cdot y_0^i\cdot n^{\frac{i-1}{2}}$

$d_k=(x_0-y_0\cdot \sqrt{n}{)}^k=\sum _{i=0}^k(\genfrac{}{}{0ex}{}{k}{i})x_0^{k-i}\cdot (-y_0\cdot \sqrt{n}{)}^i=\sum _{\genfrac{}{}{0ex}{}{i=0}{i\text{ gerade}}}^k(\genfrac{}{}{0ex}{}{k}{i})x_0^{k-i}\cdot (+y_0\cdot \sqrt{n}{)}^i+\sum _{\genfrac{}{}{0ex}{}{i=0}{i\text{ ungerade}}}^k(\genfrac{}{}{0ex}{}{k}{i})x_0^{k-i}\cdot (-y_0\cdot \sqrt{n}{)}^i=\underset{i\text{ gerade, }\frac{i}{2}\text{ganzzahlig}}{\underbrace{\sum _{\genfrac{}{}{0ex}{}{i=0}{i\text{ gerade}}}^k(\genfrac{}{}{0ex}{}{k}{i})x_0^{k-i}\cdot y_0^i\cdot n^{\frac{i}{2}}}}-\sqrt{n}\cdot \underset{i\text{ ungerade, }\frac{i-1}{2}\text{ganzzahlig}}{\underbrace{\sum _{\genfrac{}{}{0ex}{}{i=0}{i\text{ ungerade}}}^k(\genfrac{}{}{0ex}{}{k}{i})x_0^{k-i}\cdot y_0^i\cdot n^{\frac{i-1}{2}}}}$

Die unterklammerten Ausdrücke sind ganzzahlig, da sie aus Summen von Produkten des Binomialkoeffizienten $\left(\genfrac{}{}{0ex}{}{k}{i}\right)$ mit ganzzahlig nichtnegativen Potenzen $k-i$, $i$ und $\frac{i}{2}$ bzw. $\frac{i-1}{2}$ der ganzzahligen Variablen $x$, $y$ und $n$ bestehen.

$c_k+d_k=\sum _{\genfrac{}{}{0ex}{}{i=0}{i\text{ gerade}}}^k(\genfrac{}{}{0ex}{}{k}{i})x_0^{k-i}\cdot y_0^i\cdot n^{\frac{i}{2}}\xcancel{+\sqrt{n}\cdot \sum _{\genfrac{}{}{0ex}{}{i=0}{i\text{ ungerade}}}^k(\genfrac{}{}{0ex}{}{k}{i})x_0^{k-i}\cdot y_0^i\cdot n^{\frac{i-1}{2}}}+\sum _{\genfrac{}{}{0ex}{}{i=0}{i\text{ gerade}}}^k(\genfrac{}{}{0ex}{}{k}{i})x_0^{k-i}\cdot y_0^i\cdot n^{\frac{i}{2}}\xcancel{-\sqrt{n}\cdot \sum _{\genfrac{}{}{0ex}{}{i=0}{i\text{ ungerade}}}^k(\genfrac{}{}{0ex}{}{k}{i})x_0^{k-i}\cdot y_0^i\cdot n^{\frac{i-1}{2}}}=2\cdot \sum _{\genfrac{}{}{0ex}{}{i=0}{i\text{ gerade}}}^k(\genfrac{}{}{0ex}{}{k}{i})x_0^{k-i}\cdot y_0^i\cdot n^{\frac{i}{2}}$

$c_k-d_k=\xcancel{\sum _{\genfrac{}{}{0ex}{}{i=0}{i\text{ gerade}}}^k(\genfrac{}{}{0ex}{}{k}{i})x_0^{k-i}\cdot y_0^i\cdot n^{\frac{i}{2}}}+\sqrt{n}\cdot \sum _{\genfrac{}{}{0ex}{}{i=0}{i\text{ ungerade}}}^k(\genfrac{}{}{0ex}{}{k}{i})x_0^{k-i}\cdot y_0^i\cdot n^{\frac{i-1}{2}}\xcancel{-\sum _{\genfrac{}{}{0ex}{}{i=0}{i\text{ gerade}}}^k(\genfrac{}{}{0ex}{}{k}{i})x_0^{k-i}\cdot y_0^i\cdot n^{\frac{i}{2}}}+\sqrt{n}\cdot \sum _{\genfrac{}{}{0ex}{}{i=0}{i\text{ ungerade}}}^k(\genfrac{}{}{0ex}{}{k}{i})x_0^{k-i}\cdot y_0^i\cdot n^{\frac{i-1}{2}}=2\cdot \sqrt{n}\cdot \sum _{\genfrac{}{}{0ex}{}{i=0}{i\text{ ungerade}}}^k(\genfrac{}{}{0ex}{}{k}{i})x_0^{k-i}\cdot y_0^i\cdot n^{\frac{i-1}{2}}$

$\begin{array}{cc}{x}_k=\frac{1}{2}(c_k+d_k)& =\sum _{\genfrac{}{}{0ex}{}{i=0}{i\text{ gerade}}}^k(\genfrac{}{}{0ex}{}{k}{i})x_0^{k-i}\cdot y_0^i\cdot n^{\frac{i}{2}}\\ y_k=\frac{1}{2\cdot \sqrt{n}}(c_k-d_k)& =\sum _{\genfrac{}{}{0ex}{}{i=0}{i\text{ ungerade}}}^k(\genfrac{}{}{0ex}{}{k}{i})x_0^{k-i}\cdot y_0^i\cdot n^{\frac{i-1}{2}}\\ \end{array}$

Wie man sieht, sind die letzten beiden Ausdrücke ganzzahlig.

 Aussage 2

$\begin{array}{cc}{c}_k& =\frac{1}{2}\cdot ((x_0+y_0\cdot \sqrt{n}{)}^k+(x_0-y_0\cdot \sqrt{n}{)}^k)+\frac{1}{2\cdot \sqrt{n}}\cdot ((x_0+y_0\cdot \sqrt{n}{)}^k-(x_0-y_0\cdot \sqrt{n}{)}^k)\cdot \sqrt{n}\\ & =\frac{1}{2}\cdot (x_0+y_0\cdot \sqrt{n}{)}^k\xcancel{+\frac{1}{2}\cdot (x_0-y_0\cdot \sqrt{n}{)}^k}+\frac{1}{2}\cdot (x_0+y_0\cdot \sqrt{n}{)}^k\xcancel{-\frac{1}{2}\cdot (x_0-y_0\cdot \sqrt{n}{)}^k}\\ & =(x_0+y_0\cdot \sqrt{n}{)}^k\end{array}$

Zusammengesetzt $x_k+y_k\sqrt{n}$ ergeben diese beiden ganzzahligen Werte wieder $c_k$.

Beispiele

Die Pellsche Gleichung für $n=3$ hat die kleinste nichttriviale Lösung $(x_0=2,y_0=1)$. Die sich ergebende Transformationsmatrix lautet

$M=\left(\begin{array}{cc}{x}_0& n\cdot y_0\\ y_0& x_0\end{array}\right)=\left(\begin{array}{cc}2& 3\\ 1& 2\end{array}\right)$.

Die nächsten fünf Lösungen berechnen sich dann wie folgt:

$\left(\begin{array}{c}{x}_1\\ y_1\end{array}\right)=M\cdot \left(\begin{array}{c}{x}_0\\ y_0\end{array}\right)=\left(\begin{array}{cc}2& 3\\ 1& 2\end{array}\right)\cdot \left(\begin{array}{c}2\\ 1\end{array}\right)=\left(\begin{array}{c}7\\ 4\end{array}\right)$

$\left(\begin{array}{c}{x}_2\\ y_2\end{array}\right)=M\cdot \left(\begin{array}{c}{x}_1\\ y_1\end{array}\right)=\left(\begin{array}{cc}2& 3\\ 1& 2\end{array}\right)\cdot \left(\begin{array}{c}7\\ 4\end{array}\right)=\left(\begin{array}{c}26\\ 15\end{array}\right)$

$\left(\begin{array}{c}{x}_3\\ y_3\end{array}\right)=M\cdot \left(\begin{array}{c}{x}_2\\ y_2\end{array}\right)=\left(\begin{array}{cc}2& 3\\ 1& 2\end{array}\right)\cdot \left(\begin{array}{c}26\\ 15\end{array}\right)=\left(\begin{array}{c}97\\ 56\end{array}\right)$

$\left(\begin{array}{c}{x}_4\\ y_4\end{array}\right)=M\cdot \left(\begin{array}{c}{x}_3\\ y_3\end{array}\right)=\left(\begin{array}{cc}2& 3\\ 1& 2\end{array}\right)\cdot \left(\begin{array}{c}97\\ 56\end{array}\right)=\left(\begin{array}{c}362\\ 209\end{array}\right)$

$\left(\begin{array}{c}{x}_5\\ y_5\end{array}\right)=M\cdot \left(\begin{array}{c}{x}_4\\ y_4\end{array}\right)=\left(\begin{array}{cc}2& 3\\ 1& 2\end{array}\right)\cdot \left(\begin{array}{c}362\\ 209\end{array}\right)=\left(\begin{array}{c}1351\\ 780\end{array}\right)$

Man erhält die Folge aller nichttrivialen Lösungen.

Startet man fälschlicherweise mit der (allgemeiner: einer) trivialen Lösung $(x^{\prime }=1,y^{\prime }=0)$, ist die Transformationsmatrix die Einheitsmatrix

$M=\left(\begin{array}{cc}{x}^{\prime }& n\cdot y^{\prime }\\ y^{\prime }& x^{\prime }\end{array}\right)=\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)=𝐈$

und liefert keine neuen Lösungen.

Startet man hingegen fälschlicherweise mit der zweiten nichttrivialen Lösung, die hier mal mit $(x_0^{*}=7,y_0^{*}=4)$ bezeichnet wird, erhält man als Matrix:

$M=\left(\begin{array}{cc}{x}_0^{*}& n\cdot y_0^{*}\\ y_0^{*}& x_0^{*}\end{array}\right)=\left(\begin{array}{cc}7& 12\\ 4& 7\end{array}\right)$

Die nächsten zwei Lösungen berechnen sich dann wie folgt:

$\left(\begin{array}{c}{x}_1^{*}\\ y_1^{*}\end{array}\right)=M\cdot \left(\begin{array}{c}{x}_0^{*}\\ y_0^{*}\end{array}\right)=\left(\begin{array}{cc}7& 12\\ 4& 7\end{array}\right)\cdot \left(\begin{array}{c}7\\ 4\end{array}\right)=\left(\begin{array}{c}97\\ 56\end{array}\right)$

$\left(\begin{array}{c}{x}_2^{*}\\ y_2^{*}\end{array}\right)=M\cdot \left(\begin{array}{c}{x}_1^{*}\\ y_1^{*}\end{array}\right)=\left(\begin{array}{cc}7& 12\\ 4& 7\end{array}\right)\cdot \left(\begin{array}{c}97\\ 56\end{array}\right)=\left(\begin{array}{c}1351\\ 780\end{array}\right)$

Startet man mit der zweiten Lösung $(x_1,y_1)$, erhält man nur jede zweite Lösung $(x_3,y_3,)(x_5,y_5),\dots$

Das Berechnen weiterer Lösungen als Grafik dargestellt:

Startwert	Matrix	$(x^{\prime },y^{\prime })$ $(1,0)$	$(x_0,y_0)$ $(2,1)$	$(x_1,y_1)$ $(7,4)$	$(x_2,y_2)$ $(26,15)$	$(x_3,y_3)$ $(97,56)$	$(x_4,y_4)$ $(362,209)$	$(x_5,y_5)$ $(1351,780)$	$(x_6,y_6)$ $(5042,2911)$	$(x_7,y_7)$ $(18817,10864)$	$(x_8,y_8)$ $(70226,40545)$
$(x^{\prime },y^{\prime })$ $(1,0)$	$\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)$	$(x^{\prime },y^{\prime })\curvearrowleft$
$(x_0,y_0)$ $(2,1)$	$\left(\begin{array}{cc}2& 3\\ 1& 2\end{array}\right)$		$\stackrel{(x_1,y_1)}{\to }$	$\stackrel{(x_2,y_2)}{\to }$	$\stackrel{(x_3,y_3)}{\to }$	$\stackrel{(x_4,y_4)}{\to }$	$\stackrel{(x_5,y_5)}{\to }$	$\stackrel{(x_6,y_6)}{\to }$	$\stackrel{(x_7,y_7)}{\to }$	$\stackrel{(x_8,y_8)}{\to }$	$\stackrel{(x_9,y_9)}{\to }$
$(x_1,y_1)$ $(7,4)$	$\left(\begin{array}{cc}7& 12\\ 4& 7\end{array}\right)$			$\stackrel{(x_3,y_3)}{\to }$		$\stackrel{(x_5,y_5)}{\to }$		$\stackrel{(x_7,y_7)}{\to }$		$\stackrel{(x_9,y_9)}{\to }$
$(x_2,y_2)$ $(26,15)$	$\left(\begin{array}{cc}15& 78\\ 26& 15\end{array}\right)$				$\stackrel{(x_5,y_5)}{\to }$			$\stackrel{(x_8,y_8)}{\to }$			$\stackrel{(x_{11},y_{11})}{\to }$
$(x_3,y_3)$ $(97,56)$	$\left(\begin{array}{cc}97& 168\\ 56& 97\end{array}\right)$					$\stackrel{(x_7,y_7)}{\to }$				$\stackrel{(x_{11},y_{11})}{\to }$

Spezialfälle

Für spezielle $n$ lässt sich die kleinste Lösung von $x^2-n\cdot y^2=1$ auf einfache Weise explizit bestimmen. Im Folgenden sei $a$ eine ganze Zahl mit $a\ge 2$.

$\begin{array}{cc}n=a^2-2& ⟶(a^2-1,a)\\ n=a^2-1& ⟶(a,1)\\ n=a^2+1& ⟶(2a^2+1,2a)\\ n=a^2+2& ⟶(a^2+1,a)\\ n=a^2+a& ⟶(2a+1,2)\end{array}$

Außerdem ergeben sich für folgende $n$ die kleinsten Lösungen

$\begin{array}{cc}n=(ab{)}^2-2b& ⟶(a^{2}b-1,a)\\ n=(ab{)}^2-b& ⟶(2a^{2}b-1,2a)\text{mit}b\ge 2\\ n=(ab{)}^2+b& ⟶(2a^{2}b+1,2a)\\ n=(ab{)}^2+2b& ⟶(a^{2}b+1,a)\end{array}$

Für $b=1$ erhält man (bis auf den zweiten Fall) die oberen Formeln.

Tabelle der Fundamentaleinheiten

Hier eine Tabelle der kleinsten Lösungen (Fundamentaleinheiten) von $x^2-n\cdot y^2=1$ mit $1\le n\le 160$. Ist $n$ ein Quadrat gibt es nur die trivialen Lösungen $x=\pm 1,y=0$ (da $1^2-n\cdot 0^2=1-0=1$).

Die Werte von $x$ und $y$ bilden die Folgen A002350 und A002349 in OEIS.

Legende
keine Lösung			Es gibt keinerlei Lösungen, auch keine trivialen.
keine Pellsche Gleichung	0	0	Für d = 0, ist x = 0, y = 0 immer eine Lösung (neben weiteren Lösungen für n = Quadratzahl)
Triviallösung mit y = 0	1	0	Triviallösungen für x² = d unabhängig von n. d muss dazu eine Quadratzahl (0, 1, 4, ...) sein. Für d = 0 erhält man den Fall in der Zeile darüber.
Triviallösung mit y = 1	3	1	Triviallösungen für y² = d + n, Lösungen bilden Diagonalen im Lösungsdiagramm der verallgemeinerten Pellsche Gleichung. Beispiel: 3² − 8 · 1² = 3² − 8 = 1
Triviallösung mit x = 0	0	3	Triviallösungen für y² = −d / n, −d / n muss dazu eine Quadratzahl sein. Beispiel: 0² − 1 · 3² = −9
nicht-triviale Lösung	38	12	komplexere Lösung, die die oberen Fälle nicht abdeckt. x und y können hierbei insbesondere für d = Quadratzahl sehr große Werte annehmen.

n	x	y
1	1	0
2	3	2
3	2	1
4	1	0
5	9	4
6	5	2
7	8	3
8	3	1
9	1	0
10	19	6
11	10	3
12	7	2
13	649	180
14	15	4
15	4	1
16	1	0
17	33	8
18	17	4
19	170	39
20	9	2
21	55	12
22	197	42
23	24	5
24	5	1
25	1	0
26	51	10
27	26	5
28	127	24
29	9801	1820
30	11	2
31	1520	273
32	17	3

n	x	y
33	23	4
34	35	6
35	6	1
36	1	0
37	73	12
38	37	6
39	25	4
40	19	3
41	2049	320
42	13	2
43	3482	531
44	199	30
45	161	24
46	24335	3588
47	48	7
48	7	1
49	1	0
50	99	14
51	50	7
52	649	90
53	66249	9100
54	485	66
55	89	12
56	15	2
57	151	20
58	19603	2574
59	530	69
60	31	4
61	1766319049	226153980
62	63	8
63	8	1
64	1	0

n	x	y
65	129	16
66	65	8
67	48842	5967
68	33	4
69	7775	936
70	251	30
71	3480	413
72	17	2
73	2281249	267000
74	3699	430
75	26	3
76	57799	6630
77	351	40
78	53	6
79	80	9
80	9	1
81	1	0
82	163	18
83	82	9
84	55	6
85	285769	30996
86	10405	1122
87	28	3
88	197	21
89	500001	53000
90	19	2
91	1574	165
92	1151	120
93	12151	1260
94	2143295	221064
95	39	4
96	49	5

n	x	y
97	62809633	6377352
98	99	10
99	10	1
100	1	0
101	201	20
102	101	10
103	227528	22419
104	51	5
105	41	4
106	32080051	3115890
107	962	93
108	1351	130
109	158070671986249	15140424455100
110	21	2
111	295	28
112	127	12
113	1204353	113296
114	1025	96
115	1126	105
116	9801	910
117	649	60
118	306917	28254
119	120	11
120	11	1
121	1	0
122	243	22
123	122	11
124	4620799	414960
125	930249	83204
126	449	40
127	4730624	419775
128	577	51

n	x	y
129	16855	1484
130	6499	570
131	10610	927
132	23	2
133	2588599	224460
134	145925	12606
135	244	21
136	35	3
137	6083073	519712
138	47	4
139	77563250	6578829
140	71	6
141	95	8
142	143	12
143	12	1
144	1	0
145	289	24
146	145	12
147	97	8
148	73	6
149	25801741449	2113761020
150	49	4
151	1728148040	140634693
152	37	3
153	2177	176
154	21295	1716
155	249	20
156	25	2
157	46698728731849	3726964292220
158	7743	616
159	1324	105
160	721	57

Negative Pellsche Gleichung

Eine negative Pellsche Gleichung ist eine diophantische Gleichung der Form

$x^2-n\cdot y^2=-1$

und diese wurde ebenfalls eingehend untersucht. Sie kann mit der gleichen Methode der Kettenbrüche gelöst werden und hat nur dann eine Lösung, wenn die Periode des Kettenbruchs eine ungerade Länge hat.

Die Bedingungen für eine Lösung sind:

• $n$ ist nicht durch 4 teilbar.
• $n$ ist nicht durch eine Primzahl der Form $4\cdot k+3$ mit $k\ge 0$ teilbar. Daher existieren z. B. keine Lösungen für $n=3$ und für $n=7$ und für $n=2\cdot 7=14$ und für $n=3\cdot 11=33$.
• $n$ ist keine Quadratzahl. Daher existieren z. B. keine Lösungen für $n=5^2=25$ und für $n=13^2=169$.
  • Ausnahme: Für die Quadratzahl 1 existiert genau eine triviale Lösung $(0,1)$.
• $n$ ist nicht in der heuristischen Vorlage:OEIS enthalten. Daher existieren z. B. keine Lösungen für $n=34$ und für $n=146$.

Wesentlich einfacher ist es, die Kettenbruchentwicklung (notfalls mit Papier und Bleistift) auszurechnen:

Programm zur Berechnung der Kettenbruchentwicklung für 0 ≤ n ≤ 9999

#include <cmath>
#include <cstdint>
#include <tuple>
#include <string>

using i64 = std::int64_t;

std::tuple <int, std::string> Kettenbruch (i64 const n)
{
    i64 const   sq  = (i64)::sqrt(n);
    if (n == sq*sq)
        return { 0, "[" + std::to_string(sq) + "]" };

    std::string ret = "[" + std::to_string(sq) + "; ";
    i64         b   = sq;
    i64         xd  = 1;
    i64         xa  = sq;
    int         len;

    for (len = 0; b != 2*sq ; len++) {
        i64 ad = (n - xa*xa) / xd;
        b  = (sq + xa) / ad;
        xd = ad;
        xa = b*ad - xa;
        ret += std::to_string(b) + ",";
    }
    return { len, ret + "_]" };
}

int main()
{
    for (int i = 0; i <= 9999; i++) { // Kettenbruchentwicklung bis 9999, ggf. anpassen
        auto const [len, text] = Kettenbruch(i);
        ::printf ("%s %-3u sqrt(%-6u) = %s\n", len&1 ? "#" : " ", len, i, text.c_str());
    }
    return 0;
}

Die ersten Zahlen $n$, für die eine Lösung für $x^2-n\cdot y^2=-1$ existiert, sind:

1, 2, 5, 10, 13, 17, 26, 29, 37, 41, 50, 53, 58, 61, 65, 73, 74, 82, 85, 89, 97, ... (siehe Vorlage:OEIS).

n	Anzahl der Lösungen 0 ≤ y < 1014	Lösungen (xi, yi) für d = −1	lim xi / yi	lim xi+1 / xi = q	q + 1/q	a	b
1	1	(0, 1)         trivale Lösung
2	19	(1, 1), (7, 5), (41, 29), (239, 169), (1393, 985), (8119, 5741), (47321, 33461), (275807, 195025), (1607521,1136689), ...	1,414214	Vorlage:05,828427	6	3	2
5	12	(2, 1), (38, 17), (682, 305), (12238, 5473), (219602, 98209), (3940598, 1762289), (70711162, 31622993), ...	2,236068	Vorlage:017,944272	18	9	4
10	9	(3, 1), (117, 37), (4443, 1405), (168717, 53353), (6406803, 2026009), (243289797, 76934989), ...	3,162278	Vorlage:037,973666	38	19	6
13	5	(18, 5), (23382, 6485), (30349818, 8417525), (39394040382, 10925940965), (51133434066018,14181862955045), ...	3,605551	1297,999229	1298	649	180
17	8	(4, 1), (268, 65), (17684, 4289), (1166876, 283009), (76996132, 18674305), (5080577836,1232221121), ...	4,123106	Vorlage:065,984845	66	33	8

Tabelle der Fundamentaleinheiten

Die Lösungen für die negative Pellsche Gleichung für $1\le n\le 409$, die eine Lösung haben, lauten:

n	x	y
1	0	1
2	1	1
5	2	1
10	3	1
13	18	5
17	4	1
26	5	1
29	70	13
37	6	1
41	32	5
50	7	1
53	182	25
58	99	13
61	29718	3805
65	8	1
73	1068	125
74	43	5
82	9	1

n	x	y
85	378	41
89	500	53
97	5604	569
101	10	1
106	4005	389
109	8890182	851525
113	776	73
122	11	1
125	682	61
130	57	5
137	1744	149
145	12	1
149	113582	9305
157	4832118	385645
170	13	1
173	1118	85
181	1111225770	82596761
185	68	5

n	x	y
193	1764132	126985
197	14	1
202	3141	221
218	251	17
226	15	1
229	1710	113
233	23156	1517
241	71011068	4574225
250	4443	281
257	16	1
265	6072	373
269	82	5
274	1407	85
277	8920484118	535979945
281	1063532	63445
290	17	1
293	2482	145
298	409557	23725

n	x	y
313	126862368	7170685
314	443	25
317	352618	19805
325	18	1
337	1015827336	55335641
338	239	13
346	93	5
349	9210	493
353	71264	3793
362	19	1
365	3458	181
370	327	17
373	5118	265
389	1282	65
394	395023035	19900973
397	20478302982	1027776565
401	20	1
409	111921796968	5534176685

Verallgemeinerte Pellsche Gleichung

Anzahl der Lösungen der Pellschen Gleichung (zoom to view) für (0 ≤ y ≤ 5 ⋅ 10¹³,  d = −101 ... +101  und  n = −101 ... +226):
 • oben links   (n ≤ 0, d < 0):  keine Lösungen (auch keine trivialen)  
 • oben rechts (n ≤ 0, d ≥ 0):  endlich viele triviale Lösungen
 • unten     (n > 0):    komplexeres Lösungsverhalten
  ○ n = 0, d = m²: unendlich viele triviale Lösungen (0, mk) für k ∈ ℤ  
  ○ n = 0, d ≠ m²: keine Lösungen
  ○ n = m², d = 0: unendlich viele triviale Lösungen (k, mk) für k ∈ ℤ
  ○ n ≠ m², d = 0: eine triviale Lösung (0, 0)
  ○ n = m², d ≠ 0: keine oder endlich viele triviale Lösungen
  ○ n ≠ m², d ≠ 0: keine oder unendlich viele Lösungen
  ○ n = −d ≠ m²:   unendlich viele Lösungen
  ○ ansonsten:  keine oder unendlich viele Lösungen

Eine verallgemeinerte Pellsche Gleichung ist eine diophantische Gleichung der Form

$x^2-n\cdot y^2=d$

wobei $n$ eine positive ganze Zahl, aber keine Quadratzahl und $d$ eine ganze Zahl ungleich 0 ist. Um diese Gleichung vollständig zu lösen, muss als vorbereitender Schritt eine Lösung $(x_0,y_0)$ dieser Gleichung und außerdem die kleinste nichttriviale Lösung $(p_0,q_0)$ der entsprechenden (normierten) Pellschen Gleichung $x^2-n\cdot y^2=+1$ bekannt sein. Dann kann man unendlich viele weitere Lösungen $(x_k,y_k)$ von $x^2-n\cdot y^2=d$ darstellen als

$x_k+y_k\cdot \sqrt{n}=(x_0+y_0\cdot \sqrt{n})\cdot (p_0+q_0\cdot \sqrt{n}{)}^k$

Es gelten also die rekursiven Gleichungen

$x_{k+1}=p_0\cdot x_k+n\cdot q_0\cdot y_k$

$y_{k+1}=q_0\cdot x_k+p_0\cdot y_k$

auch darstellbar als Matrixmultiplikation

$\left(\begin{array}{c}{x}_{k+1}\\ y_{k+1}\end{array}\right)=\left(\begin{array}{cc}{p}_0& n\cdot q_0\\ q_0& p_0\end{array}\right)\cdot \left(\begin{array}{c}{x}_k\\ y_k\end{array}\right)$.

Im Gegensatz zum schon betrachteten Fall mit $d=+1$ existieren für Nichtquadratzahlen $d\notin \{+k^2:k\in {\mathbb{N}}^{+}\}$ nur für einen Teil der $n$ Lösungen. Dies lässt sich oft mithilfe der Division mit Rest beweisen.

Um alle Lösungen der verallgemeinerten Pellsche Gleichung zu bestimmen, reicht es, endlich viele Lösungen $(x,y)$ in einem bestimmten Bereich zu finden und daraus mithilfe der rekursiven Gleichungen alle weiteren Lösungen zu berechnen. Für diese endlich viele Lösungen $(x,y)$ gilt

$|x|\le \frac{1}{2}\cdot \sqrt{|d|}\cdot (\sqrt{u}+\frac{1}{\sqrt{u}})$

$|y|\le \frac{1}{2\cdot \sqrt{n}}\cdot \sqrt{|d|}\cdot (\sqrt{u}+\frac{1}{\sqrt{u}})$

mit $u:=p_0+q_0\cdot \sqrt{n}$.

Lösungen

Triviale Lösungen

Ausschließlich triviale Lösungen (oder gar keine Lösungen) gibt es, falls eine der Bedingungen zutrifft:

$d=0$ oder $n\in \{\mathbb{Z}\setminus \mathbb{N}\}\cup \{m^2\mid m\in \mathbb{Z}\}$.  (Spalte mit $d=0$ und die Zeilen mit $n=-10\dots 0,1,4,9,16,25$)

Beides stellt keine Pellschen Gleichungen dar.

• gar keine Lösungen gibt es immer, falls $d<0$ und $n\le 0$ zutrifft.  (linker, oberer Quadrant)
• jeweils eine triviale Lösung lässt sich konstruieren aus:
  • $d\in \{m^2\mid m\in \mathbb{Z}\}$, dann ist $(m,0)$ immer eine Lösung.  (grüne Spalten)
  • $d+n\in \{m^2\mid m\in \mathbb{Z}\}$, dann ist $(m,1)$ immer eine Lösung.  (rote Diagonalen)
• unendlich viele triviale Lösung im Abstand von 1 lassen sich konstruieren aus:
  • $d\in \{m^2\mid m\in \mathbb{Z}\}$ und $n=0$, dann sind alle Paare $(m,k)$ mit $k\in \mathbb{Z}$ Lösungen.  (siehe Zeile mit $n=0$)
  • $d=0$ und $n\in \{m^2\mid m\in \mathbb{Z}\}$, dann sind alle Paare $(mk,k)$ mit $k\in \mathbb{Z}$ Lösungen.  (siehe Spalte mit $d=0$)
• Triviale Lösungen treten (meist) auch für $d,n$ auf, für die es nichttriviale Lösungen gibt.

Nichttriviale Lösungen

Nichttrivale Lösungen haben u. a. die Eigenschaft, dass sie eine Folge mit exponentiellem Wachstum bilden, während triviale Lösungen entweder als einzelne Lösungen aus „kleinen“ Zahlen $(3,2)$ oder eine Folge mit linearem Wachstum bilden $(2k,k)$.

Nichttrivale Lösungen kann es (muss es aber nicht) nur unter folgenden Bedingungen geben:

$d\ne 0$ und $n\in \mathbb{N}\setminus \{m^2\mid m\in \mathbb{N}\}$.

Diese Bedingungen werden in diesem Absatz im Folgenden vorausgesetzt.

• Nichttrivale Lösungen gibt es immer für $d\in \{m^2\mid m\in \mathbb{N}\}$.
• Nichttrivale Lösungen gibt es immer für $d+n\in \{m^2\mid m\in \mathbb{N}\}$.
• Nichttrivale Lösungen tauchen weiterhin sporadisch auf, z. B. für $d=8,n=7$ und $d=-7,n=14$

Lösungstabelle

Die verallgemeinerte Pellsche Gleichung $x^2-n\cdot y^2=d$ hat für $-10\le d\le 10$ und $-10\le n\le 25$ zeigt folgendes Lösungsverhalten.

n	d																					n
	-10	-9	-8	-7	-6	-5	-4	-3	-2	-1	0	1	2	3	4	5	6	7	8	9	10
-10											(0,0)	(1,0)			(2,0)					(3,0)	(0,1)	-10
-9											(0,0)	(1,0)			(2,0)					(3,0) (0,1)	(1,1)	-9
-8											(0,0)	(1,0)			(2,0)				(0,1)	(3,0) (1,1)		-8
-7											(0,0)	(1,0)			(2,0)			(0,1)	(1,1)	(3,0)		-7
-6											(0,0)	(1,0)			(2,0)		(0,1)	(1,1)		(3,0)	(2,1)	-6
-5											(0,0)	(1,0)			(2,0)	(0,1)	(1,1)			(3,0) (2,1)		-5
-4											(0,0)	(1,0)			(2,0) (0,1)	(1,1)			(2,1)	(3,0)		-4
-3											(0,0)	(1,0)		(0,1)	(2,0) (1,1)			(2,1)		(3,0)		-3
-2											(0,0)	(1,0)	(0,1)	(1,1)	(2,0)		(2,1)		(0,2)	(3,0) (1,2)		-2
-1											(0,0)	(1,0) (0,1)	(1,1)		(2,0) (0,2)	(2,1) (1,2)			(2,2)	(3,0) (0,3)	(3,1) (1,3)	-1
0											(0,k)	(1,k)			(2,k)					(3,k)		0
1		(0,3) (4,5)	(1,3)	(3,4)		(2,3)	(0,2)	(1,2)		(0,1)	(k,k)	(1,0)		(2,1)	(2,0)	(3,2)		(4,3)	(3,1)	(3,0) (5,4)		1
2		14	15	29			15		15	15	(0,0)	15	15		15			29	14	15		2
3			19					20	20		(0,0)	21			20		19			20		3
4				(3,2)			(0,1)	(1,1)			(2k,k)	(1,0)			(2,0)	(3,1)				(3,0) (5,2)		4
5		9				10	27			9	(0,0)	10			28	9				9		5
6			11		12	23			12		(0,0)	12		12	12					12	22	6
7				10	19			19			(0,0)	10	10		10				9	29		7
8			15	30			15				(0,0)	16			15				15	15		8
9		(0,1)	(1,1)			(2,1)					(3k,k)	(1,0)			(2,0)			(4,1)		(3,0)		9
10	8	22			15		7			7	(0,0)	8			8		14			22	7	10
11	17		9	18					9		(0,0)	10			9	18				9		11
12			20					10			(0,0)	11			21					10		12
13		11					11	8		4	(0,0)	4		7	12					12		13
14	15			8		16					(0,0)	9	8		8				8	8		14
15					13						(0,0)	14			13					13	13	15
16				(3,1)							(4k,k)	(1,0)			(2,0)					(3,0) (5,1)		16
17		6	13				6			7	(0,0)	7			7				13	7		17
18		15	7						8		(0,0)	8			8			15		15		18
19	9		5					9	5		(0,0)	5			5	9	9			14		19
20							9				(0,0)	10			10	9				10		20
21						11		6			(0,0)	6			18			6		6		21
22			4	9	9				5		(0,0)	5		9	5					14		22
23				14							(0,0)	8	7		7				7	7		23
24			12								(0,0)	13			12					12		24
25		(4,1)									(5k,k)	(1,0)			(2,0)					(3,0)		25
n	-10	-9	-8	-7	-6	-5	-4	-3	-2	-1	0	1	2	3	4	5	6	7	8	9	10	n
	d

Legende

leer		keine Lösungen, auch keine trivialen
Paar mit Variable k		triviale Lösungen habe das gleiche Bildungsschema (xk, yk) mit k ∈ ℕ
ein bzw. zwei Paare		explizite Angabe der einen bzw. beider trivialer Lösungen
fette Zahl		Angabe der Anzahl der Lösungen für 0 ≤ y < 1011, Mauszeiger über die Zahl zeigt die Lösungen (xi, yi) an Der erste Eintrag dieser Liste ist immer sehr klein und folgt Bildungsvorschriften wie (0, k), (1, k), (k, 0), (k, 1), (k, k), (mk, k), (k²+1, k) und zählt damit meist zu den trivialen Lösungen.

Beispiel

Gesucht sind die Lösungen der Gleichung

$x^2-7\cdot y^2=-3$

Dafür wird die kleinste Lösung der Gleichung $x^2-7\cdot y^2=1$ bestimmt. Diese lautet $(p_0=8,q_0=3)$. Also ist $n=7$, $d=-3$, $u=8+3\cdot \sqrt{7}$.

Es müssen zunächst die Lösungen mit

$|x|\le \frac{1}{2}\cdot \sqrt{|-3|}\cdot (\sqrt{8+3\cdot \sqrt{7}}+\frac{1}{\sqrt{8+3\cdot \sqrt{7}}})<4$

bestimmt werden. Das sind:

$(x_0=-2,y_0=-1)$, $(x_0=-2,y_0=1)$, $(x_0=2,y_0=-1)$ und $(x_0=2,y_0=1)$.

Daraus ergeben sich mithilfe der Rekursion alle Lösungen.

Aus $(x_0=-2,y_0=1)$ und $(x_0=2,y_0=1)$ erhält man

$(x_0=-2,y_0=1)$, $(x_1=5,y_1=2)$, $(x_2=82,y_2=31)$, $(x_3=1307,y_3=494)$, $(x_4=20830,y_4=7873)$, $\dots$

$(x_0=2,y_0=1)$, $(x_1=37,y_1=14)$, $(x_2=590,y_2=223)$, $(x_3=9403,y_3=3554)$, $(x_4=149858,y_4=56641)$, $\dots$

Aus $(x_0=2,y_0=-1)$ und $(x_0=-2,y_0=-1)$ erhält man die gleichen Lösungen mit umgekehrtem Vorzeichen.

  Ausführlicher Beweis des Berechnens weiterer Lösungen durch Rekursion

Wir starten mit mit der Lösung der (nicht verallgemeinerten) Pellschen Gleichung (mit der $1$ auf der rechten Seite).

Für unser gegebenes $n$ kennen wird $(x_0,y_0)$, so dass:

$x_0^2-n{y}_0^2=1$

gilt. Beide Seiten multiplizieren wir mit $d$:

$d(x_0^2-n{y}_0^2)=x_0^{2}d-y_0^{2}nd=d$

Das $d$ auf der linken Seite ersetzen wir durch $x_k^2-n{y}_k^2$, da $x_k^2-n{y}_k^2=d$ gelten soll:

$x_0^2(x_k^2-n{y}_k^2)-y_0^{2}n(x_k^2-n{y}_k^2)$

Durch Umsortieren der Terme erhält man

$(n^2{y}_0^2{y}_k^2-n{x}_k^2{y}_0^2)+(x_0^2{x}_k^2-n{x}_0^2{y}_k^2)=d$.

Nun fügen wir die beiden Terme $+2n{x}_0{x}_k{y}_0{y}_k$ und $-2n{x}_0{x}_k{y}_0{y}_k$ ein, die zusammen Null ergeben:

$x_0^2{x}_k^2+2n{x}_0{x}_k{y}_0{y}_k+n^2{y}_0^2{y}_k^2-n{x}_k^2{y}_0^2-2n{x}_0{y}_0{x}_k{y}_k-n{x}_0^2{y}_k^2=d$

Das kann man ausklammern:

$((x_0{x}_k{)}^2+2n{x}_0{x}_k{y}_0{y}_k+(n{y}_0{y}_k{)}^2)-n((x_k{y}_0{)}^2+2x_k{y}_0{x}_0{y}_k+(x_0{y}_k{)}^2)=d$

Die beiden Klammern stellen Quadratterme dar:

$(x_0{x}_k+n{y}_0{y}_k{)}^2-n(x_k{y}_0+x_0{y}_k{)}^2=d$

Die beiden Klammerterme stellen die Bildungsvorschriften für $x_{k+1}$ und $y_{k+1}$ dar:

$x_{k+1}=x_0{x}_k+n{y}_0{y}_k$

$y_{k+1}=x_k{y}_0+x_0{y}_k$.

Einsetzen dieser

$x_{k+1}^2-n{y}_{k+1}^2=d$

zeigt, dass auch $x_{k+1}^2$ und $y_{k+1}^2$ Lösung der verallgemeinerten Pellschen Gleichung sind, wenn ...

Beispiel für n = 5, d = 44

Für $n=5$ und $d=44$ erhält man sechs ineinanderverschachtelte Serien an Lösungen.

Zuerst berechnen wir die Transformationsmatrix $M$:

$n=5,\left(\begin{array}{c}{p}_0\\ q_0\end{array}\right)=\left(\begin{array}{c}9\\ 4\end{array}\right)⟹M=\left(\begin{array}{cc}{p}_0& n\cdot q_0\\ q_0& p_0\end{array}\right)=\left(\begin{array}{cc}9& 5\cdot 4\\ 4& 9\end{array}\right)=\left(\begin{array}{cc}9& 20\\ 4& 9\end{array}\right)$

Die Serien starten dann mit

$M\cdot \left(\begin{array}{c}{x}_0\\ y_0\end{array}\right)=M\cdot \left(\begin{array}{c}7\\ 1\end{array}\right)=\left(\begin{array}{c}83\\ 37\end{array}\right)=\left(\begin{array}{c}{x}_6\\ y_6\end{array}\right)$

$M\cdot \left(\begin{array}{c}{x}_1\\ y_1\end{array}\right)=M\cdot \left(\begin{array}{c}8\\ 2\end{array}\right)=\left(\begin{array}{c}112\\ 50\end{array}\right)=\left(\begin{array}{c}{x}_7\\ y_7\end{array}\right)$

$M\cdot \left(\begin{array}{c}{x}_2\\ y_2\end{array}\right)=M\cdot \left(\begin{array}{c}13\\ 5\end{array}\right)=\left(\begin{array}{c}217\\ 9\end{array}\right)=\left(\begin{array}{c}{x}_8\\ y_8\end{array}\right)$

$M\cdot \left(\begin{array}{c}{x}_3\\ y_3\end{array}\right)=M\cdot \left(\begin{array}{c}17\\ 7\end{array}\right)=\left(\begin{array}{c}293\\ 131\end{array}\right)=\left(\begin{array}{c}{x}_9\\ y_9\end{array}\right)$

$M\cdot \left(\begin{array}{c}{x}_4\\ y_4\end{array}\right)=M\cdot \left(\begin{array}{c}32\\ 14\end{array}\right)=\left(\begin{array}{c}568\\ 254\end{array}\right)=\left(\begin{array}{c}{x}_{10}\\ y_{10}\end{array}\right)$

$M\cdot \left(\begin{array}{c}{x}_5\\ y_5\end{array}\right)=M\cdot \left(\begin{array}{c}43\\ 19\end{array}\right)=\left(\begin{array}{c}767\\ 343\end{array}\right)=\left(\begin{array}{c}{x}_{11}\\ y_{11}\end{array}\right)$

und gehen mit

$M\cdot \left(\genfrac{}{}{0ex}{}{x_6}{y_6}\right)=\left(\genfrac{}{}{0ex}{}{x_{12}}{y_{12}}\right)$, $M\cdot \left(\genfrac{}{}{0ex}{}{x_7}{y_7}\right)=\left(\genfrac{}{}{0ex}{}{x_{13}}{y_{13}}\right)$, $\dots ,M\cdot \left(\genfrac{}{}{0ex}{}{x_k}{y_k}\right)=\left(\genfrac{}{}{0ex}{}{x_{k+6}}{y_{k+6}}\right),\dots$

weiter bis in alle Unendlichkeit.

Tabellen der Fundamentaleinheiten für die verallgemeinerte Pellsche Gleichung

Die verallgemeinerte Pellsche Gleichung $x^2-n\cdot y^2=d$ hat für $-10\le d\le 10$ und $1\le n\le 25$ folgende kleinste Lösungen (Fundamentaleinheiten):

n	d																																										n
	−10		−9		−8		−7		−6		−5		−4		−3		−2		−1		0		1		2		3		4		5		6		7		8		9		10
	x	y	x	y	x	y	x	y	x	y	x	y	x	y	x	y	x	y	x	y	x	y	x	y	x	y	x	y	x	y	x	y	x	y	x	y	x	y	x	y	x	y
1			0	3	1	3	3	4			2	3	0	2	1	2			0	1	1	1	1	0			2	1	2	0	3	2			4	3	3	1	5	4			1
2			3	3	0	2	1	2					2	2			0	1	1	1	0	0	3	2	2	1			6	4					3	1	4	2	9	6			2
3					2	2									0	1	1	1			0	0	2	1					4	2			3	1					6	3			3
4							3	2					0	1	1	1					2	1	1	0					2	0	3	1							5	2			4
5			6	3							0	1	1	1					2	1	0	0	9	4					3	1	5	2							27	12			5
6					4	2			0	1	1	1					2	1			0	0	5	2			3	1	10	4									15	6	4	1	6
7							0	1	1	1					2	1					0	0	8	3	3	1			16	6							6	2	4	1			7
8					0	1	1	1					2	1							0	0	3	1					6	2							4	1	9	3			8
9			0	1	1	1					2	1									3	1	1	0					2	0					4	1			3	0			9
10	0	1	1	1					2	1			6	2					3	1	0	0	19	6					38	12			4	1					7	2	10	3	10
11	1	1			6	2	2	1									3	1			0	0	10	3					20	6	4	1							30	9			11
12					2	1									3	1					0	0	7	2					4	1									21	6			12
13			2	1									3	1	7	2			18	5	0	0	649	180			4	1	11	3									29	8			13
14	2	1					7	2			3	1									0	0	15	4	4	1			30	8							8	2	45	12			14
15									3	1											0	0	4	1					8	2									12	3	5	1	15
16							3	1													4	1	1	0					2	0									5	1			16
17			12	3	3	1							8	2					4	1	0	0	33	8					66	16							5	1	99	24			17
18			3	1	8	2											4	1			0	0	17	4					34	8					5	1			9	2			18
19	3	1			26	6									4	1	13	3			0	0	170	39					340	78	9	2	5	1					22	5			19
20													4	1							0	0	9	2					18	4	5	1							27	6			20
21											4	1			9	2					0	0	55	12					5	1					14	3			165	36			21
22					28	6	9	2	4	1							14	3			0	0	197	42			5	1	394	84									19	4			22
23							4	1													0	0	24	5	5	1			48	10							10	2	72	15			23
24					4	1															0	0	5	1					10	2									15	3			24
25			4	1																	5	1	1	0					2	0									3	0			25
n	x	y	x	y	x	y	x	y	x	y	x	y	x	y	x	y	x	y	x	y	x	y	x	y	x	y	x	y	x	y	x	y	x	y	x	y	x	y	x	y	x	y	n
	−10		−9		−8		−7		−6		−5		−4		−3		−2		−1		0		1		2		3		4		5		6		7		8		9		10
	d

Anwendungsbeispiele

Quadratzahlen und Dreieckszahlen

16 Münzen als Quadrat gelegt

10 Münzen als Dreieck gelegt

Eine bestimmte Anzahl Münzen kann sowohl in Form eines Quadrats als auch in Form eines Dreiecks angeordnet werden. Die Bilder rechts veranschaulichen das. Für welche Anzahl von Münzen ist das möglich?

Die gesuchte Anzahl muss sowohl eine Dreieckszahl als auch eine Quadratzahl sein. Daraus erhält man die äquivalenten Gleichungen

$\begin{array}{cc}\frac{n\cdot (n+1)}{2}& =m^2\\ \frac{1}{8}\cdot ((2\cdot n+1{)}^2-1)& =m^2\\ (2\cdot n+1{)}^2-2\cdot (2\cdot m{)}^2& =1\\ \end{array}$

Die Substitutionen $x:=2\cdot n+1$ und $y:=2\cdot m$ ergeben die Pellsche Gleichung

$x^2-2\cdot y^2=1$

Die kleinste Lösung ist $(x_0=3,y_0=2)$. Aus den rekursiven Gleichungen

$x_{i+1}=x_0\cdot x_i+2\cdot y_0\cdot y_i$

$y_{i+1}=y_0\cdot x_i+x_0\cdot y_i$

erhält man die weiteren Lösungen. Die ersten vier Lösungen mit der entsprechenden Anzahl von Münzen zeigt die folgende Tabelle.

i	xi	yi	n	m	Anzahl der Münzen
0	3	2	1	1	1
2	17	12	8	6	36
4	99	70	49	35	1225
6	577	408	288	204	41616

Hausnummern

An einer Straße befinden sich $n$ Häuser mit den ungeraden Hausnummern $1,3,5,\dots ,2\cdot n-1$. Die Häuser sind von links nach rechts durchnummeriert. Eines dieser Häuser ist weiß. Die Summe der Hausnummern links vom weißen Haus ist gleich der Summe der Hausnummern rechts vom weißen Haus. Für welche Anzahl $n$ von Häusern ist das möglich? Welche Hausnummer hat dann das weiße Haus?

Hat das weiße Haus die Hausnummer $2\cdot m-1$, dann ist die Summe der Häuser links davon gleich der Summe der Häuser rechts davon:

$\begin{array}{cc}1+3+5+\cdots +(2\cdot m-3)& =(2\cdot m+1)+(2\cdot m+3)+\cdots +(2\cdot n-1)\\ 1+3+5+\cdots +(2\cdot m-3)& =(1+3+5+\cdots +(2\cdot n-1))-(1+3+5+\cdots +(2\cdot m-1))\\ \end{array}$

Jede Quadratzahl $n^2$ ist die Summe der ersten $n$ ungeraden natürlichen Zahlen. Also ist diese Gleichung äquivalent zu

$\begin{array}{cc}(m-1{)}^2& =n^2-m^2\\ 2\cdot m^2-2\cdot m+1& =n^2\\ 4\cdot m^2-4\cdot m+2& =2\cdot n^2\\ (2\cdot m-1{)}^2-2\cdot n^2=-1\\ \end{array}$

Die Substitutionen $x:=2\cdot m-1$ und $y:=n$ ergeben die negative Pellsche Gleichung

$x^2-2\cdot y^2=-1$

Die kleinste Lösung ist $(x_1=1,y_1=1)$. Aus den rekursiven Gleichungen

$x_{i+1}=x_0\cdot x_i+2\cdot y_0\cdot y_i$

$y_{i+1}=y_0\cdot x_i+x_0\cdot y_i$

erhält man die weiteren Lösungen. Die ersten vier Lösungen mit der Anzahl von Häusern, der größten Hausnummer und der Hausnummer des weiße Hauses zeigt die folgende Tabelle.

	Hausnummer weißes Haus	Anzahl der Häuser	größte Haus- nummer
i	xi = 2 · m − 1	yi = n	2 · n − 1
0	1	1	1
2	7	5	9
4	41	29	57
6	239	169	337

Das Rinderproblem des Archimedes

Bei der Lösung des Rinderproblems des Archimedes stößt man (wenn man geschickt rechnet) auf die Pellsche Gleichung $x^2-n\cdot y^2=1$ zum Parameter $n=4729494$, die als Minimallösung

$x=109931986732829734979866232821433543901088049\approx 1,099\cdot 10^{44}$

$y=50549485234315033074477819735540408986340\approx 5,055\cdot 10^{40}$

hat. Für das Rinderproblem braucht man allerdings nicht die Minimallösung, sondern die kleinste Lösung, bei der $y$ ein Vielfaches von $2\cdot 4657$ ist.

Alternativ dazu kann man für die Pellsche Gleichung mit Parameter $n=410286423278424=(2\cdot 4657{)}^2\cdot 4729494$ die Minimallösung (jetzt ohne Nebenbedingung) suchen, die von folgender Größenordnung ist:

$x\approx 3,7653\cdot 10^{103272}$

$y\approx 1,8589\cdot 10^{103265}$

Nicht zufällig ist $2\cdot 3,7653\cdot 10^{103272}\approx (2\cdot 1,0993199\cdot 10^{44}{)}^{2329}$, wodurch numerisch der Zusammenhang zwischen den Minimallösungen der beiden Pellschen Gleichungen hergestellt ist.

Für das Rinderproblem selbst ist als Zwischenergebnis die Zahl $4657\cdot 957\cdot y^2\approx 1,5401\cdot 10^{206537}$ von Belang. Das Endergebnis ist das $50389082$-Fache davon, also ca. $7,760\cdot 10^{206544}$.

Rechtwinklige Dreiecke und pythagoreische Tripel

Gesucht sind die rechtwinkligen Dreiecke mit ganzzahligen Seitenlängen, wo die Kathetenlängen eine bestimmte Differenz haben. Diese Seitenlängen sind sogenannte pythagoreische Tripel mit besonderen Eigenschaften.

Ist $k$ die Differenz der Kathetenlängen, dann sind die ganzzahligen Seitenlängen der rechtwinkligen Dreiecke die pythagoreischen Tripel der Form $(a,a+k,c)$. Nach dem Satz des Pythagoras gilt dann

$\begin{array}{cc}{a}^2+(a+k{)}^2& =c^2\\ 2\cdot a^2+2\cdot a\cdot k+k^2& =c^2\\ 4\cdot a^2+4\cdot a\cdot k+2\cdot k^2& =2\cdot c^2\\ (2\cdot a+k{)}^2-2\cdot c^2& =-k^2\\ \end{array}$

Die Substitutionen $x:=2\cdot a+k$ und $y:=c$ ergeben die verallgemeinerte Pellsche Gleichung

$x^2-2\cdot y^2=-k^2$

Die kleinste Lösung der Gleichung $x^2-2\cdot y^2=1$ ist $(p=3,q=2)$.

Für den Fall $k=1$ ist $(x_0=1,y_0=1)$ die einzige positive Basislösung der verallgemeinerten Pellschen Gleichung mit $d=2$, $n=-1$, $u=3+2\cdot \sqrt{2}$. Die weiteren Lösungen mit den entsprechenden Seitenlängen der rechtwinkligen Dreiecke sind

i	xi = 2 · a + 1	yi = c	a	a + 1
0	1	1	0	1
1	7	5	3	4
2	41	29	20	21
3	239	169	119	120

Für $(x_0=1,y_0=1)$ ist $a=0$. Daher gehört diese Lösung zu keinem Dreieck. Die Seitenlängen der gesuchten rechtwinkligen Dreiecke sind (3, 4, 5), (20, 21, 29), (119, 120, 169), ... Das sind die rechtwinkligen Dreiecke, wo die Kathetenlängen die Differenz $k=1$ haben. Für $k=2,3,4,5,6$ sind die Lösungen der verallgemeinerten Pellsche Gleichung die entsprechenden Vielfachen. Für die Differenz $k=6$ zum Beispiel ergeben sich die rechtwinkligen Dreiecke mit den Seitenlängen (18, 24, 30), (120, 126, 174), (714, 720, 1014), ...

Für $k=7$ hat die verallgemeinerte Pellsche Gleichung mehrere Basislösungen, darunter $(x_0=-1,y_0=5)$, $(x_0=1,y_0=5)$ und $(x_0=7,y_0=7)$. Daraus ergeben sich alle weiteren positiven Lösungen und, wenn alle positiv, die entsprechenden Seitenlängen der rechtwinkligen Dreiecke:

i	xi = 2 · a + 7	yi = c	a	a + 7		i	xi = 2 · a + 7	yi = c	a	a + 7		i	xi = 2 · a + 7	yi = c	a	a + 7
0	−1	5	−4	3		0	1	5	−3	4		0	7	7	0	7
1	17	13	5	12		1	23	17	8	15		1	49	35	21	28
2	103	73	48	55		2	137	97	65	72		2	287	203	140	147
3	601	425	297	304		3	799	565	396	403		3	1673	1183	833	840

Zerlegungen gleichseitiger Dreiecke

Das gleichseitige Dreieck mit der Seitenlänge a wird in zwei Dreiecke mit den ganzzahligen Seiten­längen s, t, a und a − s, a, t zerlegt. Das Dreieck mit den Seitenlängen h, k, t ist rechtwinklig.

Gesucht sind gleichseitige Dreiecke, die in zwei Teildreiecke mit ganzzahligen Seitenlängen zerlegt werden können.

Ist $a$ die Seitenlänge und $h$ die Höhe des gleichseitigen Dreiecks, ist $t$ die Länge der Strecke, die das gleichseitige Dreieck teilt, und sind $s$ und $a-s$ die Längen der geteilten Seite, dann bildet die Höhe zusammen mit der Teilungsstrecke und einer Strecke der Länge $k:=\frac{a}{2}-s$ ein rechtwinkliges Dreieck, wobei $t$ die Hypotenusenlänge ist. Die Abbildung rechts zeigt das.

Nach dem Satz des Pythagoras und wegen $h^2=\frac{3}{4}\cdot a^2$ gilt dann

$\begin{array}{cc}{h}^2+k^2& =t^2\\ \frac{3}{4}\cdot a^2+k^2& =t^2\\ t^2-3\cdot {\left(\frac{a}{2}\right)}^2& =k^2\\ \end{array}$

Die Substitutionen $x:=t$ und $y:=\frac{a}{2}$ ergeben die verallgemeinerte Pellsche Gleichung

$x^2-3\cdot y^2=k^2$

Die kleinste Lösung der Gleichung $x^2-3\cdot y^2=1$ ist $(p=2,q=1)$.

Für den Fall $k=1$ ist $(x_0=2,y_0=1)$ die einzige positive Basislösung der verallgemeinerten Pellschen Gleichung mit $d=3$, $n=1$, $u=2+\sqrt{3}$. Die weiteren Lösungen mit die entsprechenden Seitenlänge $a$ des gleichseitigen Dreiecks und die Seitenlängen $s,t,a$ und $a-s,a,t$ der zwei Teildreiecke sind

i	xi = t	yi = a/2	a	s = a/2 − 1	a − s
0	2	1	2	0	2
1	7	4	8	3	5
2	26	15	30	14	16
3	97	56	112	55	57

Für $k=2,3,4,5,6,7,8,9,10$ sind die Lösungen der verallgemeinerten Pellsche Gleichung die entsprechenden Vielfachen.

Für den Fall $k=11$ hat die verallgemeinerte Pellsche Gleichung mehrere Basislösungen, darunter $(x_0=11,y_0=0)$, $(x_0=13,y_0=4)$ und $(x_0=14,y_0=5)$. Daraus ergeben sich alle weiteren positiven Lösungen und, wenn alle positiv, die entsprechenden Seitenlängen des gleichseitigen Dreiecks und der zwei Teildreiecke:

i	xi = t	yi = a/2	a	s = a/2 − 11	a − s		i	xi = t	yi = a/2	a	s = a/2 − 11	a − s		i	xi = t	yi = a/2	a	s = a/2 − 11	a − s
0	11	0	0	−11	11		0	13	4	8	−7	15		0	14	5	10	−6	16
1	22	11	22	0	22		1	38	21	42	10	32		1	43	24	48	13	35
2	77	44	88	33	55		2	139	80	160	69	91		2	158	91	182	80	102
3	286	165	330	154	176		3	518	299	598	288	310		3	589	340	680	329	351

Literatur

• H. W. Lenstra Jr.: Solving the Pell Equation, Notices of the American Mathematical Society, Band 49, Heft 2, 2002, S. 182–192, online (PDF; 237 kB).
• M. J. Jacobson Jr., H. C. Williams: Solving the Pell Equation, CMS Books in Mathematics, Springer 2009, ISBN 978-0-387-84922-5
• Leonard Dickson: History of the theory of numbers, Washington D.C.: Carnegie Institution, 1920, Kapitel 12 (zur Geschichte der Pellschen Gleichung)

Weblinks

• Pell Equation in Wolfram’s Math World (englisch)
• Universität Bayreuth: Diophantische Gleichungen (Seite 71)
• Schweizer Mathematik-Olympiade: Zahlentheorie 3 (Seite 5)
• Technische Universität Graz: Zahlentheorie - Vorbereitungskurs zur Österreichischen Mathematischen Olympiade (Seite 39)