Pells ligning

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

  
    
      
        
          x
          
            2
          
        
        −
        D
        
          y
          
            2
          
        
        =
        1
      
    
    {\displaystyle 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 ==
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 = m2 + 1, har ligningen løsningen x = 2m2 + 1 med y = 4m som lett verifiseres ved innsetting.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
      
    
    {\displaystyle 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.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». Dette skyldes at hvert trekanttall kan skrives som n(n + 1)/2 og hvert kvadrattall som m2 hvor n og m er heltall. Betingelsen som må oppfylles er derfor ligningen x2  - 8y2 = 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.


== Generering av løsninger ==
Når D er et kvadratisk tall n2, tar Pell-ligningen x2  - D y2 = 1 formen x2  - z2 = 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
          
        
        −
        D
        
          y
          
            1
          
          
            2
          
        
        )
        (
        
          x
          
            2
          
          
            2
          
        
        −
        D
        
          y
          
            2
          
          
            2
          
        
        )
        =
        (
        
          x
          
            1
          
        
        
          x
          
            2
          
        
        +
        D
        
          y
          
            1
          
        
        
          y
          
            2
          
        
        
          )
          
            2
          
        
        −
        D
        (
        
          x
          
            1
          
        
        
          y
          
            2
          
        
        +
        
          y
          
            1
          
        
        
          x
          
            2
          
        
        
          )
          
            2
          
        
      
    
    {\displaystyle (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 (x1,y1) og (x2,y2) er løsninger av ligningen, så er

  
    
      
        
          x
          
            3
          
        
        =
        
          x
          
            1
          
        
        
          x
          
            2
          
        
        +
        D
        
          y
          
            1
          
        
        
          y
          
            2
          
        
        ,
        
        
        
          y
          
            3
          
        
        =
        
          x
          
            1
          
        
        
          y
          
            2
          
        
        +
        
          y
          
            1
          
        
        
          x
          
            2
          
        
      
    
    {\displaystyle 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.


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

  
    
      
        
          x
          
            2
          
        
        −
        D
        
          y
          
            2
          
        
        =
        (
        x
        +
        y
        
          
            D
          
        
        )
        (
        x
        −
        y
        
          
            D
          
        
        )
        =
        1
      
    
    {\displaystyle 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
          
        
        
          
            D
          
        
        )
        (
        
          x
          
            2
          
        
        +
        
          y
          
            2
          
        
        
          
            D
          
        
        )
        =
        
          x
          
            1
          
        
        
          x
          
            2
          
        
        +
        D
        
          y
          
            1
          
        
        
          y
          
            2
          
        
        +
        (
        
          x
          
            1
          
        
        
          y
          
            2
          
        
        +
        
          y
          
            1
          
        
        
          x
          
            2
          
        
        )
        
          
            D
          
        
      
    
    {\displaystyle (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
        
          
            D
          
        
        )
        =
        
          x
          
            2
          
        
        −
        D
        
          y
          
            2
          
        
      
    
    {\displaystyle N(x+y{\sqrt {D}})=x^{2}-Dy^{2}}
  ,så betyr Brahmaguptas identitet at N(α1)N(α2) = N(α1α2). 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» α1 =  x1 + y1√D slik at det n-te elementet er

  
    
      
        
          α
          
            n
          
        
        =
        
          x
          
            n
          
        
        +
        
          y
          
            n
          
        
        
          
            D
          
        
        =
        (
        
          x
          
            1
          
        
        +
        
          y
          
            1
          
        
        
          
            D
          
        
        
          )
          
            n
          
        
      
    
    {\displaystyle \alpha _{n}=x_{n}+y_{n}{\sqrt {D}}=(x_{1}+y_{1}{\sqrt {D}})^{n}}
  Dette er ekvivalent med den rekursive sammenhengen

  
    
      
        
          
            (
            
              
                
                  
                    x
                    
                      n
                    
                  
                
              
              
                
                  
                    y
                    
                      n
                    
                  
                
              
            
            )
          
        
        =
        
          
            (
            
              
                
                  
                    x
                    
                      1
                    
                  
                
                
                  D
                  
                    y
                    
                      1
                    
                  
                
              
              
                
                  
                    y
                    
                      1
                    
                  
                
                
                  
                    x
                    
                      1
                    
                  
                
              
            
            )
          
        
        
          
            (
            
              
                
                  
                    x
                    
                      n
                      −
                      1
                    
                  
                
              
              
                
                  
                    y
                    
                      n
                      −
                      1
                    
                  
                
              
            
            )
          
        
      
    
    {\displaystyle {\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 (xn,yn) 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.


== Periodiske kjedebrøker ==
Kvadratroten til et tall D kan fremstilles som en periodisk kjedebrøk √D = [a0;P ] hvor linjen over perioden P betyr at den gjentas i det uendelige. Her er heltallet a0 den laveste approksimasjon til kvadratroten, mens perioden har den palindromske formen P = (a1,a2,...,a2,a1,2a0) 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 xn /yn for √D, desto større vil (xn,yn) være en løsning av ligningen.Den fundamentale eller minste løsning (x1,y1) 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 2a0 i perioden. Nå er 

  
    
      
        [
        2
        ;
        1
        ,
        1
        ,
        1
        ]
        =
        2
        +
        
          
            
              
                
              
              
                
                  1
                
              
            
            
              
                
              
              
                
                  1
                  +
                  
                    
                      
                        
                          
                        
                        
                          
                            1
                          
                        
                      
                      
                        
                          
                        
                        
                          
                            1
                            +
                            
                              
                                
                                  
                                    
                                  
                                  
                                    
                                      1
                                    
                                  
                                
                                
                                  
                                    
                                  
                                  
                                    
                                      1
                                    
                                  
                                
                              
                            
                          
                        
                      
                    
                  
                
              
            
          
        
        =
        2
        +
        
          
            2
            3
          
        
        =
        
          
            8
            3
          
        
      
    
    {\displaystyle [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 ===
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 x2  - D y2 = -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 702 - 29⋅132 = -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 ==


== Eksterne lenker ==
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