Die Gleichung von Pell ist jede Gleichung von Diophantine der Form

:

wo n eine nichtquadratische ganze Zahl ist. Wortdiophantine meint, dass Werte der ganzen Zahl von x und y gesucht werden. Trivial lösen x = 1 und y = 0 immer diese Gleichung. Lagrange hat bewiesen, dass für jede natürliche Zahl n, der nicht ist, ein vollkommenes Quadrat dort x und y> 0 ist, die die Gleichung von Pell befriedigen. Außerdem ungeheuer bestehen viele solche Lösungen dieser Gleichung. Diese Lösungen geben gute vernünftige Annäherungen der Form x/y zur Quadratwurzel von n nach.

Der Name dieser Gleichung ist aus dem falschen Zuschreiben von Leonhard Euler seiner Studie John Pell entstanden. Euler war der Arbeit von Herrn Brouncker, dem ersten europäischen Mathematiker bewusst, um eine allgemeine Lösung der Gleichung zu finden, aber hat anscheinend Brouncker mit Pell verwirrt. Diese Gleichung wurde zuerst umfassend im alten Indien studiert, mit Brahmagupta anfangend, der die chakravala Methode entwickelt hat, die Gleichung von Pell und andere quadratische unbestimmte Gleichungen in seinem Brahma Sphuta Siddhanta in 628, ungefähr eintausend Jahre vor der Zeit von Pell zu lösen. Sein Brahma Sphuta Siddhanta wurde ins Arabisch in 773 übersetzt und wurde nachher in Latein 1126 übersetzt. Bhaskara II im 12. Jahrhundert und Narayana Pandit im 14. Jahrhundert sowohl haben allgemeine Lösungen der Gleichung von Pell als auch anderer quadratischer unbestimmter Gleichungen gefunden. Lösungen spezifischer Beispiele der Gleichung von Pell, wie die Zahlen von Pell, die aus der Gleichung mit n = 2 entstehen, waren für den viel längeren seit der Zeit von Pythagoras in Griechenland und zu einem ähnlichen Datum in Indien bekannt gewesen.

Für eine ausführlichere Diskussion von viel vom Material hier, sieh Lenstra (2002) und Barbeau (2003).

Geschichte

Die Gleichungen von Pell wurden schon in 400 v. Chr. in Indien und Griechenland studiert. Sie haben sich hauptsächlich für die Gleichung interessiert

:

wegen seiner Verbindung zur Quadratwurzel zwei. Tatsächlich, wenn x und y ganze Zahlen sind, die diese Gleichung befriedigen, dann ist x / y eine Annäherung 2. Zum Beispiel hat Baudhayana entdeckt, dass x = 17, y = 12 und x = 577, y = 408 zwei Lösungen der Gleichung von Pell sind, und sehr nahe Annäherungen an die Quadratwurzel zwei gegeben haben.

Später hat Archimedes eine ähnliche Gleichung verwendet, um der Quadratwurzel 3 näher zu kommen, und hat 1351/780 gefunden.

Ringsherum n.Chr. 250 hat Diophantus eine verschiedene Form der Gleichung von Pell geschaffen

:

Er hat diese Gleichung für = 1, und c = −1, 1, und 12 gelöst, und hat auch für = 3 und c = 9 gelöst.

Brahmagupta hat eine allgemeine Weise geschaffen, die als die chakravala Methode bekannte Gleichung von Pell zu lösen. Bhāskara habe ich eine Weise geschaffen, neue Lösungen von Gleichungen von Pell von einer Lösung zu schaffen. E. Strachey hat die Arbeit von Bhāskara I in Englisch 1813 veröffentlicht. Alkarkhi hat an ähnlichen Problemen zu Diophantus gearbeitet.

Brahmagupta hat dass entdeckt (sieh die Identität von Brahmagupta)

:

Damit ist er im Stande gewesen "zu dichten" verdreifacht sich, und die Lösungen waren, um den neuen dreifachen zu erzeugen

:

Nicht nur hat das eine Weise gegeben, ungeheuer viele Lösungen des Startens mit einer Lösung, sondern auch, durch das Teilen solch einer Zusammensetzung durch, ganze Zahl zu erzeugen, oder "fast ganze Zahl" Lösungen konnte häufig erhalten werden. Zum Beispiel, weil Brahmagupta das dreifache (seitdem) mit sich zusammengesetzt hat, um das neue dreifache zu bekommen. Das Teilen überall durch 64 hat das dreifache gegeben, das, wenn zusammengesetzt, mit sich die gewünschte Lösung der ganzen Zahl gegeben hat. Brahmagupta hat viele Gleichungen von Pell mit dieser Methode gelöst; insbesondere hat er gezeigt, wie man Lösungen erhält, die von einer Lösung der ganzen Zahl für k =±1, ±2, oder ±4 anfangen.

Die erste allgemeine Methode, für die Gleichung von Pell (für den ganzen N) zu lösen, wurde durch Bhaskara II 1150 gegeben, die Methoden von Brahmagupta erweiternd. Genannt den chakravala (zyklische) Methode, es fängt durch das Bestehen von irgendwelchem an verdreifachen sich (d. h. derjenige, der befriedigt) mit dem trivialen dreifachen, um das dreifache zu bekommen, das zu heruntergeschraubt werden kann

:

Wenn M gewählt wird, so dass (a+bm)/k eine ganze Zahl ist, auch sind die anderen zwei Zahlen im dreifachen. Unter solcher M wählt die Methode diejenige, die (M ²-n)/k minimiert, und den Prozess wiederholt. Diese Methode endet immer mit einer Lösung (bewiesen von Lagrange 1768). Bhaskara hat es verwendet, um die Lösung x=1766319049, y=226153980 des notorischen N=61 Falls zu geben.

Die allgemeine Theorie der Gleichung von Pell, die auf fortlaufenden Bruchteilen und algebraischen Manipulationen mit Zahlen der Form gestützt ist, wurde von Lagrange in 1766-1769 entwickelt.

Lösungen

Grundsätzliche Lösung über fortlaufende Bruchteile

Lassen Sie zeigen die Folge von convergents zum fortlaufenden Bruchteil dafür an. Dann befriedigt das Paar (x, y) die Gleichung von lösendem Pell und x minimierend, x = h und y = k für einige ich. Dieses Paar wird die grundsätzliche Lösung genannt. So kann die grundsätzliche Lösung durch das Durchführen der fortlaufenden Bruchteil-Vergrößerung und die Prüfung von jedem aufeinander folgend konvergent gefunden werden, bis eine Lösung der Gleichung von Pell gefunden wird.

Wie, die Zeit beschreibt für zu finden, dass die grundsätzliche Lösung mit der fortlaufenden Bruchteil-Methode, mithilfe vom Algorithmus von Schönhage-Strassen für die schnelle Multiplikation der ganzen Zahl, innerhalb eines logarithmischen Faktors der Lösungsgröße, der Zahl von Ziffern im Paar (x, y) ist. Jedoch ist das nicht ein polynomischer Zeitalgorithmus, weil die Zahl von Ziffern in der Lösung so groß sein kann wie n, viel größer, als ein Polynom in der Zahl von Ziffern im Eingang n schätzt.

Zusätzliche Lösungen von der grundsätzlichen Lösung

Sobald die grundsätzliche Lösung gefunden wird, können alle restlichen Lösungen algebraisch als berechnet werden

:

Gleichwertig können wir nachfolgende Lösungen über die Wiederauftreten-Beziehungen berechnen

::

Eine alternative Methode zum Lösen, einmal Entdeckung der ersten nichttrivialen Lösung, konnte man die ursprüngliche Gleichung und den Faktor die linke Seite als ein Unterschied von Quadraten nehmen, Einmal in dieser Form tragend, man kann einfach jede Seite der Gleichung zur kth Macht und das Wiederkombinieren der Factored-Form zu einer einzelnen Unterschied-Behauptung erziehen. Die Lösung wird der Form sein

Kurze Darstellung und schnellere Algorithmen

Obwohl, die grundsätzliche Lösung (x y) weil ausschreibend, ein Paar von Binärzahlen eine Vielzahl von Bit, es verlangen kann, wird der Mai in vielen Fällen kompakter in der Form vertreten

:

mit viel kleineren Koeffizienten a, b, und c.

Zum Beispiel kann das Viehproblem von Archimedes mit einer Gleichung von Pell behoben werden, deren grundsätzliche Lösung 206545 Ziffern, wenn ausgeschrieben, ausführlich hat. Jedoch, anstatt die Lösung als ein Paar von Zahlen zu schreiben, kann es mit der Formel geschrieben werden

:

wo

:

und und haben Sie nur 45 und 41 dezimale Ziffern beziehungsweise. Wechselweise kann man noch kürzer schreiben

:.

Methoden, die mit der quadratischen Sieb-Annäherung für die ganze Zahl factorization verbunden sind, können verwendet werden, um Beziehungen zwischen Primzahlen im numerischen Feld zu sammeln, das durch n erzeugt ist, und diese Beziehungen zu verbinden, um eine Produktdarstellung dieses Typs zu finden. Der resultierende Algorithmus, um die Gleichung von Pell zu lösen, ist effizienter als die fortlaufende Bruchteil-Methode, obwohl es noch nicht Zeit in Anspruch nimmt. Unter der Annahme der verallgemeinerten Hypothese von Riemann, wie man zeigen kann, nimmt es Zeit in Anspruch

:

wo N = n loggen, ist die Eingangsgröße ähnlich zum quadratischen Sieb.

Quant-Algorithmen

hat

gezeigt, dass ein Quant-Computer eine Produktdarstellung, wie beschrieben, oben für die Lösung der Gleichung von Pell in der polynomischen Zeit finden kann. Der Algorithmus von Hallgren, der als ein Algorithmus interpretiert werden kann, für die Gruppe von Einheiten eines echten quadratischen numerischen Feldes zu finden, wurde zu allgemeineren Feldern dadurch erweitert.

Beispiel

Als ein Beispiel, denken Sie das Beispiel der Gleichung von Pell für n = 7; das, ist

:

Die Folge von convergents für die Quadratwurzel sieben ist

:

Deshalb wird die grundsätzliche Lösung vom Paar (8, 3) gebildet. Die Verwendung der Wiederauftreten-Formel zu dieser Lösung erzeugt die unendliche Folge von Lösungen

: (8, 3); (127, 48); (2024, 765); (32257, 12192); (514088, 194307); (8193151; 3096720); (130576328, 49353213);...

Verbindungen

Die Gleichung von Pell hat Verbindungen zu mehreren anderen wichtigen Themen in der Mathematik.

Theorie der algebraischen Zahl

Die Gleichung von Pell ist nah mit der Theorie von algebraischen Zahlen, als die Formel verbunden

:

ist die Norm für den Ring und für das nah zusammenhängende quadratische Feld. So löst ein Paar von ganzen Zahlen die Gleichung von Pell, wenn, und nur wenn eine Einheit mit der Norm 1 darin ist. Der Einheitslehrsatz von Dirichlet, dass alle Einheiten dessen als Mächte einer einzelnen grundsätzlichen Einheit (und Multiplikation durch ein Zeichen) ausgedrückt werden können, ist eine algebraische Neuformulierung der Tatsache, dass alle Lösungen der Gleichung von Pell von der grundsätzlichen Lösung erzeugt werden können. Die grundsätzliche Einheit kann im Allgemeinen durch das Lösen einer Pell ähnlichen Gleichung gefunden werden, aber sie entspricht direkt zur grundsätzlichen Lösung der Gleichung von Pell selbst nicht immer.

Polynome von Tschebyscheff

Demeyer (2007) erwähnt eine Verbindung zwischen der Gleichung von Pell und den Polynomen von Tschebyscheff:

Wenn T (x) und U (x) die Polynome von Tschebyscheff der ersten und zweiten Art beziehungsweise sind, dann befriedigen diese Polynome eine Form der Gleichung von Pell in jedem polynomischen Ring R [x], mit n = x − 1:

:

So können diese Polynome durch die Standardtechnik für Gleichungen von Pell von Machtergreifungen einer grundsätzlichen Lösung erzeugt werden:

:

Es kann weiter das bemerkt werden, wenn (x, y) die Lösungen einer ganzer Zahl Gleichung von Pell, dann x = T (x) und y = yU (x) (Barbeau, Kapitel 3) sind.

Fortlaufende Bruchteile

Eine allgemeine Entwicklung von Lösungen der Gleichung von Pell in Bezug auf fortlaufende Bruchteile kann präsentiert werden, wie die Lösungen x und y sind, kommt der Quadratwurzel von n näher und sind so ein spezieller Fall von fortlaufenden Bruchteil-Annäherungen für quadratische Irrationalzahlen.

Die Beziehung zu den fortlaufenden Bruchteilen deutet an, dass die Lösungen der Gleichung von Pell eine Halbgruppenteilmenge der Modulgruppe bilden. So, zum Beispiel, wenn p und q die Gleichung von Pell, dann befriedigen

:

ist eine Matrix der Einheitsdeterminante. Produkte solchen matrices nehmen genau dieselbe Form an, und so geben alle diese Produkte Lösungen der Gleichung von Pell nach. Wie man verstehen kann, entsteht das teilweise aus der Tatsache, dass aufeinander folgende convergents eines fortlaufenden Bruchteils dasselbe Eigentum teilen: Wenn p/q und p/q zwei aufeinander folgende convergents eines fortlaufenden Bruchteils, dann die Matrix sind

:

hat Determinante (−1).

Der Lehrsatz von Størmer wendet Gleichungen von Pell an, um Paare von glatten Konsekutivzahlen zu finden. Als ein Teil dieser Theorie hat Størmer auch Teilbarkeitsbeziehungen unter Lösungen der Gleichung von Pell untersucht; insbesondere er hat gezeigt, dass jede Lösung außer der grundsätzlichen Lösung einen Hauptfaktor hat, der n nicht teilt.

Wie Lenstra (2002) beschreibt, kann die Gleichung von Pell auch verwendet werden, um das Viehproblem von Archimedes zu beheben.

Die negative Gleichung von Pell

Die negative Gleichung von Pell wird durch gegeben

: (eq.1)

Es ist auch umfassend studiert worden; es kann durch dieselbe Methode gelöst werden zu verwenden hat Bruchteile fortgesetzt und wird Lösungen haben, wenn die Periode des fortlaufenden Bruchteils sonderbare Länge hat. Jedoch wissen wir nicht, welche Wurzeln sonderbare Periode-Längen haben, so wissen wir nicht, wenn die negative Gleichung von Pell lösbar ist. Aber wir können bestimmten n beseitigen, da ein notwendiger, aber nicht genügend Bedingung für die Lösbarkeit ist, dass n durch eine Blüte der Form 4m+3 nicht teilbar ist. So, zum Beispiel, x-3py =-1 ist nie lösbar, aber x-5py =-1, kann solcher als wenn p = 1 oder 13, obwohl nicht wenn p = 41 sein.

demonstrieren Sie, dass das Verhältnis von quadratfreiem n, für den die negative Gleichung von Pell auflösbar ist, mindestens 40 % ist. Wenn es wirklich eine Lösung hat, dann kann es gezeigt werden, dass seine grundsätzliche Lösung zum grundsätzlichen für den positiven Fall durch das Quadrieren beide Seiten von eq.1, führt

:

zu kommen

:

Oder, seitdem ny = x+1 von eq.1, dann,

:

die Vertretung, dass grundsätzliche Lösungen des positiven Falls größer sind als diejenigen für den negativen Fall.

Transformationen

I. Die zusammenhängende Gleichung,

: (eq.2)

kann verwendet werden, um Lösungen der positiven Gleichung von Pell für bestimmten d zu finden. Legendre hat bewiesen, dass die ganze Blüte der Form d = 4 M + 3 einen Fall von eq.2, mit der Form 8 M + das 3 Lösen der Verneinung und 8 M + 7 für das positive löst. Ihre grundsätzliche Lösung führt dann zu demjenigen für x−dy = 1. Das kann durch das Quadrieren beide Seiten von eq gezeigt werden. 2,

:zu kommen:

Seitdem von eq.2, dann,

:

oder einfach,

:

die Vertretung, dass grundsätzliche Lösungen von eq.2 kleiner sind als eq.1. Zum Beispiel, u-3v =-2 ist {u, v} = {1,1}, so x − 3y = 1 hat {x, y} = {2,1}. Andererseits, u − 7v = 2 ist {u, v} = {3,1}, so x − 7y = 1 hat {x, y} = {8,3}.

II. Eine andere zusammenhängende Gleichung,

: (eq.3)

kann auch verwendet werden, um Lösungen von Gleichungen von Pell für bestimmten d dieses Mal für den positiven und negativen Fall zu finden. Für die folgenden Transformationen, wenn grundsätzlich {u, v} beide seltsam sind, dann führt es grundsätzlich {x, y}.

1. Wenn u − dv = −4, und {x, y} = {(u + 3) u/2, (u + 1) v/2}, dann x − dy =

−1.

Ab. Lassen Sie d = 13, dann {u, v} = {3, 1} und {x, y} = {18, 5}.

2. Wenn u − dv = 4, und {x, y} = {(u − 3) u/2, (u − 1) v/2}, dann x − dy = 1.

Ab. Lassen Sie d = 13, dann {u, v} = {11, 3} und {x, y} = {649, 180}.

3. Wenn u − dv = −4, und {x, y} = {(u + 4u + 1) (u + 2)/2, (u + 3) (u + 1) uv/2}, dann x − dy = 1.

Ab. Lassen Sie d = 61, dann {u, v} = {39, 5} und {x, y} = {1766319049, 226153980}.

Besonders für die letzte Transformation kann es gesehen werden, wie Lösungen {u, v} viel kleiner sind als {x, y}, da die Letzteren sextic und quintic Polynome in Bezug auf u sind.

Referenzen

...

• . Ursprünglich veröffentlichter 1977.

....

Links

• Die Gleichung von Pell
• IMO Kompendium-Text auf der Gleichung von Pell im Problem-Lösen.