Pells ligning

Pells ligning er en andregradsligning med to ukjente. Kalles de for x og y, har den formen

x^{2}-Dy^{2}=1

hvor D er et positivt heltall. Tillatte løsninger (x,y) skal kun være heltall slik at den er en diofantisk ligning. Uavhengig av verdien til D, har den alltid de to trivielle løsningene (±1,0).

Da ligningen er kvadratisk i de to ukjente, vil en løsning være ekvivalent med tre andre løsninger hvor enten x eller y skifter fortegn eller begge to, Derfor angir man vanligvis bare løsninger der x og y begge er postive.

Når konstanten D ikke er et kvadrattall, har ligningen uendelig mange løsninger. De kan alle bli funnet fra en minste løsning ved direkte multiplikasjon.

Historie rediger

Matematiske problem som tilsvarer løsning av Pell-ligningen, kan føres helt tilbake til hellenistisk tid og Diofant. Han viste at i det spesielle tilfellet der D = m² + 1, har ligningen løsningen x = 2m² + 1 med y = 4m som lett verifiseres ved innsetting.^[1]

Grunnlaget for en systematisk fremgangsmåte ble oppdaget av den indiske matematiker Brahmagupta på 600-tallet. Hans landsmann Bhaskara fant fem hundre år senere eksplisitte løsninger for D = 8, 11, 32, 61 og 67. For eksempel når D = 61, så er

x=1\,766\,319\,049,\;\;y=226\,153\,980

en løsning. Dette resultatet er opplagt en stor bragd. Men da Fermat i 1657 utfordret sine matematiske kollegaer til å finne slike løsninger for D = 151 og 313, syntes ikke disse indiske resultatene å være kjente. Fra hans brev på den tiden går det frem at han mente at ligningen kan løses for alle verdier av konstanten D. Et bevis for denne påstanden publiserte han ikke, noe som var typisk for Fermat. Denne utfordringen aksepterte John Wallis og Lord Brouncker i England. De viste hvordan kjedebrøker kan anvendes for å finne løsninger av de gitte ligningene.^[2]

Vel hundre år senere utvidet Euler denne fremgangsmåten. Det var i forbindelse med studiene av Wallis' samlede verker som kom ut noen tiår senere, at navnet til John Pell ble knyttet til ligningen. Han var en engelsk diplomat med matematiske interesser som hadde bidratt til oversettelse av en bok hvor arbeidene til Wallis og Brouncker ble omtalt. Da Goldbach i 1730 hevdet at et trekanttall ikke samtidig kan være et kvadrattall, kunne Euler svare at dette er uriktig fordi en slik mulighet eksisterer som løsning av «Pell-ligningen».^[3] Dette skyldes at hvert trekanttall kan skrives som n(n + 1)/2 og hvert kvadrattall som m² hvor n og m er heltall. Betingelsen som må oppfylles er derfor ligningen x² - 8y² = 1 der x = 2n + 1 og y = m. Den enkleste løsningen (3,1) tilsvarende m = n = 1. Omtrent like lett er det å finne den neste løsningen (17,6) som betyr at m = 6 og n = 8.

Etter denne omtalen til Euler har ligningen beholdt navnet til Pell. Han kom tilbake til den i 1767 da han publiserte et større arbeid hvor han viste at kjedebrøker gir en systematisk metode til å beregne løsninger (x,y). Når tallet y er tilstrekkelig stort, vil forholdet x/y være en god tilnærmelse til √D. Euler visste at slike kvadratrøtter kan uttrykkes ved periodiske kjedebrøker som dermed inneholder informasjon om ligningens løsninger. Basert på denne nye innsikten kunne Lagrange et par år senere vise at hver Pell-ligning har uendelig mange løsninger.^[4]

Generering av løsninger rediger

Når D er et kvadratisk tall n², tar Pell-ligningen x² - D y² = 1 formen x² - z² = 1 med z = ny. Denne tilsvarer ligningen med D = 1 som kun har de to trivielle løsningene (±1,0) og er derfor ikke av videre interesse.

Fremgangsmåten til Brahmagupta var basert på identiteten

(x_{1}^{2}-Dy_{1}^{2})(x_{2}^{2}-Dy_{2}^{2})=(x_{1}x_{2}+Dy_{1}y_{2})^{2}-D(x_{1}y_{2}+y_{1}x_{2})^{2}

som verifiseres ved direkte utregning. Den betyr at hvis (x₁,y₁) og (x₂,y₂) er løsninger av ligningen, så er

x_{3}=x_{1}x_{2}+Dy_{1}y_{2},\;\;y_{3}=x_{1}y_{2}+y_{1}x_{2}

også en løsning. På den måten kan man fra en løsning konstruere uendelig mange andre løsninger. Man kan også kombinere en løsning med seg selv. For eksempel når D = 8, er (3,1) en løsning. Den gir så en ny løsning x = 3⋅3 + 8⋅1 = 17 sammen med y = 3⋅1 + 1⋅3 = 6, det vil si (17,6). Denne kan så kombineres med den første på samme måte og dermed gi en tredje løsning. Og slik kan man fortsette så lenge man vil.^[5]

Syklisk gruppe rediger

Ved å innføre kvadratroten √D kan Pell-ligningen faktoriseres,

x^{2}-Dy^{2}=(x+y{\sqrt {D}})(x-y{\sqrt {D}})=1

Her utgjør tallene med formen x + y √D der x og y er heltall, en matematisk ring på lignende vis som de gaussiske heltallene x + y √-1. Addisjon og multiplikasjon av to slike tall gir et tredje tall av samme slag. For eksempel er

(x_{1}+y_{1}{\sqrt {D}})(x_{2}+y_{2}{\sqrt {D}})=x_{1}x_{2}+Dy_{1}y_{2}+(x_{1}y_{2}+y_{1}x_{2}){\sqrt {D}}

Hvis man definerer normen av et slikt heltall α = x + y √D som

N(x+y{\sqrt {D}})=x^{2}-Dy^{2}

,

så betyr Brahmaguptas identitet at N(α₁)N(α₂) = N(α₁α₂). Løsningene til Pell-ligningen består derfor av slike utvidete heltall med norm lik én. De kan kombineres ved multiplikasjon. Hvert tall α har en invers som er α^-1 = x - y √D. Sammen utgjør de dermed en syklisk gruppe med enhetselement som tilsvarer den trivielle løsningen (1,0). Enhver slik gruppe kan genereres ved ett «fundamentalt element» α₁ = x₁ + y₁√D slik at det n-te elementet er

\alpha _{n}=x_{n}+y_{n}{\sqrt {D}}=(x_{1}+y_{1}{\sqrt {D}})^{n}

Dette er ekvivalent med den rekursive sammenhengen

{\begin{pmatrix}x_{n}\\y_{n}\end{pmatrix}}={\begin{pmatrix}x_{1}&Dy_{1}\\y_{1}&x_{1}\end{pmatrix}}{\begin{pmatrix}x_{n-1}\\y_{n-1}\end{pmatrix}}

som er enklere å benytte for praktiske beregninger da den ikke involverer potenser av ofte store tall. På denne måten kan man finne alle løsninger (x_n,y_n) av Pell-ligningen. Samtidig viser den at ligningen har uendelig mange slike løsninger, noe som Lagrange viste rundt 1770. Problemet er derfor redusert til å finne den minste eller fundamentale løsningen.^[1]

Periodiske kjedebrøker rediger

Kvadratroten til et tall D kan fremstilles som en periodisk kjedebrøk √D = [a₀;P ] hvor linjen over perioden P betyr at den gjentas i det uendelige. Her er heltallet a₀ den laveste approksimasjon til kvadratroten, mens perioden har den palindromske formen P = (a₁,a₂,...,a₂,a₁,2a₀) der nevnerne til kjedebrøken inngår. Euler innså at denne periodisiten er direkte forbundet med den sykliske strukturen av løsningene til Pell-ligningen. Jo flere perioder man tar med i kjedebrøken for å gi en approksimativ verdi x_n /y_n for √D, desto større vil (x_n,y_n) være en løsning av ligningen.^[4]

Den fundamentale eller minste løsning (x₁,y₁) fremkommer ved å bare ta med én periode. Som en illustrasjon av metoden kan man betrakte D = 3. Da er kvadratroten den periodiske kjedebrøken √7 = [2;1,1,1,4 ]. Laveste approksimasjon er kjedebrøken [2;1,1,1] der man dropper leddet 2a₀ i perioden. Nå er

[2;1,1,1]=2+{\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{1}}}}}}=2+{\frac {2}{3}}={\frac {8}{3}}

Minste løsning er derfor (8,3). Herav finnes så den neste (127,48) og så videre. Et noe mer komplisert eksempel er D = 28. Nå er √28 = [5;3,2,3,10 ] slik at minste løsning skal følge fra [5;3,2,3] = 127/24, det vil si at den er (127,24). Den genererer alle andre slik at den neste blir (32 257, 6096) og så videre med raskt økende tall.

Odde perioder rediger

I de to foregående eksemplene hadde perioden en lengde som var et liketall. Når den er et oddetall, vil den minste løsningen som fremkommer, være oppfylt av den relaterte Pell-ligningen x² - D y² = -1. Men hvis man kombinerer denne løsningen med seg selv, vil man få den minste løsning for den normale ligningen med +1 på høyre side.

Denne situasjonen oppstår for D = 29. Da er √29 = [5;2,1,1,2,10 ] slik at man må finne verdien av kjedebrøken [5;2,1,1,2] = 70/13. Ved direkte utregning følger at 70² - 29⋅13² = -1. Men fra denne løsningen genereres nå (9801,1820) som er den fundamentale løsningen for den vanlige Pell-ligningen med D = 29.

Referanser rediger

^ ^a ^b J. J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, England (2005). ISBN 0-521-61524-0.
^ C.B. Boyer, A History of Mathematics, Princeton University Press, New Jersey (1968), ISBN 0-691-02391-3.
^ A. Weil, Number Theory - An approach through history from Hammurabi to Legendre, Birkhäuser, Boston (2007). ISBN 0-8176-4565-9.
^ ^a ^b C.E. Sandifer, How Euler Did It, The Mathematical Association of America (2007). ISBN 978-0-88385-563-8 Google Book.
^ J. Stillwell, Elements of Number Theory, Springer-Verlag, New York (2003). ISBN 978-1--4419-3066-8.

Eksterne lenker rediger

E.W. Weisstein, Pell Equation, Wolfram MathWorld
MacTutor, Pell's equation, University of St. Andrews, Scotland
H.W. Lenstra Jr., Solving the Pell Equation, Notices of the American Mathematical Society, 49(2), 182-192 (2002).
E.W. Weisstein, Periodic Continued Fraction, Wolfram MathWorld

[Tattersall-1] J. J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, England (2005). ISBN 0-521-61524-0.

[Boyer-2] C.B. Boyer, A History of Mathematics, Princeton University Press, New Jersey (1968), ISBN 0-691-02391-3.

[Weil-3] A. Weil, Number Theory - An approach through history from Hammurabi to Legendre, Birkhäuser, Boston (2007). ISBN 0-8176-4565-9.

[Sandifer-4] C.E. Sandifer, How Euler Did It, The Mathematical Association of America (2007). ISBN 978-0-88385-563-8 Google Book.

[Stillwell-5] J. Stillwell, Elements of Number Theory, Springer-Verlag, New York (2003). ISBN 978-1--4419-3066-8.

[1]

[2]

[3]

[4]

[5]