Pellsche Gleichung

Die Pellsche Gleichung

    \[ X^2-DY^2=1 \]

ist eine Diophantische Gleichung 2.Ordnung und erhielt ihren Namen von Euler zu Ehren von John Pell (1611-1685).
Für D = 61 und 109 ist die Lösung extrem schwierig und wurde erstmals von Lord William Brouncker und John Wallis gefunden. Z.B. ergibt sich für D = 109:

    \[ X=158070671986249 \quad ; \quad Y = 15140424455100 \]

Kennt man eine Lösung x0 und y0, so ergeben sich weitere Lösungen mit

    \[ x_1=Cx_0-1 \quad ; \quad y_1=Cy_0 \quad mit \quad C=2x_0 \]

    \[ x_n=Cx_{n-1}-x_{n-2} \quad ; \quad y_n=Cy_{n-1}-y_{n-2} \]

Die Liste enthält die kleinsten Lösungen der Pellschen Gleichung für die ersten quadratfreien D:

D Lösungen D Lösungen D Lösungen D Lösungen
5 9 ; 4 6 5; 2 7 8 ; 3 10 19; 6
11 10 ; 3 13 649 ; 180 14 15 ; 4 15 4 ; 1
17 33 ; 8 19 170 ; 39 21 55 ; 12 22 197 ; 42

Die Lösung der Pellschen Gleichung X² – D·Y² = 1 ergibt schon für kleine D sehr große Lösungen X und Y.  Die Tabelle enthält die Werte für D, bei denen X ein neues Maximum annimmt.

D Wert für X
5 9
10 19
13 649
29 9801
46 24335
53 66249
61 1766319049
109 158070671986249
181 2469645423824185801
277 159150073798980475849
397 838721786045180184649
409 25052977273092427986049
421 3879474045914926879468217167061449
541 370745336002386702880064559966700500
661 16421658242965910275055840472270471049
1021 198723867690977573219668252231077415636351801801
1069 742925865816843150858935268959512942700219559049

Die Schlacht von Hastings
aus „Amusements in Mathematics“, von Henry Ernest Dudeney, 1917

Die Aufgabe bezieht sich auf die Schlacht bei Hastings, jenen berühmten Kampf, in dem 1066 die Normannen unter Wilhelm dem Eroberer die Sachsen unter König Harald besiegten, und fortan die Geschicke Englands bestimmten. Nach Dudeney schildert die alte Chronik:

„Haralds Mannen standen tapfer zusammen und bildeten 61 Quadrate mit gleich vielen Recken in jedem Quadrat. Als Harald sich in die Schlacht warf, bildeten die Sachsen mit ihm zusammen ein einziges, mächtiges Quadrat.“

Gesucht ist nun die minimal mögliche Anzahl der Krieger.

Lösung: Wir bezeichnen die Kantenlänge der kleinen Quadrate mit y und die vom großen Quadrat mit x, d.h.

    \[ 61y^2+1=x^2 \]

Die kleinste natürliche Lösung dieser Pellschen Gleichung ist y = 226153980, x = 1766319049.
Mit Harald zusammen wäre also etwa 3,11 Trillionen Sachsen dabei gewesen. Und da sollen die verloren haben?

Pellsche Gleichung und Quadratwurzel

Mittels Pellscher Gleichung X² – D·Y² = 1 kann eine Näherungsformel für die Quadratwurzel √D ermittelt werden.
Durch Umstellen ergibt sich mit der Lösung (x0, y0) als 1.Näherung

    \[ \sqrt D \approx \frac{x_0}{y_0} \]

Mit der Lösung (xn, yn) ist auch

    \[ x_{n+1}=x_n^2+Dy_n^2 \quad ; \quad y_{n+1}=2x_ny_n \]

Lösung der Gleichung, wobei die Quotienten xn / yn mit wachsendem n immer besser die Wurzel √D annähern.

Eine schnellere Konvergenz ergibt sich durch Abschätzen des Fehlers

    \[ \sqrt D = \frac{x_0}{y_0}-\frac{1}{2}(\frac{1}{x_0y_0}+\frac{1}{x_1y_1}+\frac{1}{x_2y_2}+...) \]

Zum Beispiel wird für D = 2: x0 = 3, y0 = 2, x1 = 9+2·4 = 17, y1 = 2·3·2 = 12, x2 = 289+2·144 = 577, y2 = 2·17·12 = 408 und somit

    \[ \sqrt 2 = \frac{3}{2}-\frac{1}{2}(\frac{1}{3\cdot 2}+\frac{1}{17\cdot 12}+\frac{1}{577\cdot 408}+...) \]

Mit den ersten 3 Summanden erhält man als Näherung 1,41421356237… (√2 = 1,41421356237310…) mit elf exakten Ziffern. Berücksichtigt man x3 = 665857, y3 = 470832 stimmt der Näherungswert auf 21 Stellen.

Umgekehrt kann mittels Kettenbruchentwicklung der Quadratwurzel auch die Pellsche Gleichung gelöst werden.
Dazu entwickelt man \sqrt D in einen Kettenbruch und wählt an, die vorletzte Zahl einer Periode. Ist die Länge der Periode ungerade, so nutzt man die vorletzte Zahl der zweiten Periode.

Ist [a1, a2, a3, …] der Kettenbruch, so ermittelt man den n.ten Näherungsbruch \frac{p_n}{q_n}. Dazu verwendet man p0 = 1, q0 = 0, p1 = a1 und q1 = 1:

    \[ p_n=a_np_{n-1}+p_{n-2} \quad ; \quad q_n=a_nq_{n-1}+q_{n-2} \]

Das Paar x = pn und y = qn ist dann eine Lösung der Gleichung.

Beispiel: x² – 7y² = 1
Die Kettenbruchentwicklung von √7 ist [2; 1, 1, 1, 4, 1, 1, 1, 4 …].
Die vorletzte Zahl der ersten Periode ist a4 = 1 und der 4.Näherungsbruch ist 8/3. x = 8 und y = 3 sind also Lösung der Gleichung, denn 8² – 7·3² = 1.
Eine weitere Lösung erhält man aus a8, der vorletzten Zahl der zweiten Periode, der 8.Näherungsbruch ist 127/48, und 127² – 7·48² = 1.

Zur Umwandlung einer Quadratwurzel in einen periodischen Kettenbruch kann folgender Algorithmus verwendet werden:

function kettenbruchwurzel(a:integer):string;
var x,a1,b1,e:integer;
    ausgabe:string;
begin
    x:=trunc(sqrt(a+0.01));
    ausgabe:=[ +inttostr(x) + ’, ;
    a1:=x;
    b1:=a1;
    e:=a-a1*a1;
    if (e>0) then begin
      while (a1<>2*x) do begin
        a1:=(x+b1) div e;
        ausgabe:= ausgabe + inttostr(a1) + ; ;
        b1:= a1*e-b1;
        e:=(a-b1*b1) div e;
      end
    end;
    result:=ausgabe +];
end;
Quelle: Khinchin, Continued fractions, Dover Publications New York 1997

Pellsche Gleichung
Statistik
167 Downloads

Download

Die Berechnung der Pellschen Gleichung ist hier auch als Einzelprogramm downloadbar.
Den Delphi-Quelltext finden Sie unter Quelltexte.

Das angehängte Programm berechnet für alle D ≤ 6938778 den Kettenbruch von √D und die kleinste Lösung der entsprechenden Pellschen Gleichung.
Für D = 6938779 überschreitet die Periode des Kettenbruchs mit einer Länge von 7616 die im Moment vorgesehenen 7500 Glieder.

John Pell

Pell befasste sich mit Diophantische Gleichungen. Die spezielle diophantische Gleichung

    \[ X^2-DY^2=1 \]

(wobei d eine ganze Zahl ist, die kein Quadrat ist) ist zwar als Pellsche Gleichung bekannt, war aber schon den mittelalterlichen, indischen Mathematikern Brahmagupta und Bhaskara II. bekannt.
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 zur allgemeinen Kenntnis veröffentlicht. Die Theorie der Gleichung erst im 18. Jahrhundert von Joseph-Louis Lagrange entwickelt.
Pells Beziehung zu dem Problem lag lediglich in der Publikation der Lösungen von John Wallis und William Brouncker in der englischen Übersetzung der Algebra von Rahn (1668).