Kontinuerlig brøkdel av en kvadratisk irrasjonell

I matematikk , og nærmere bestemt i aritmetikk , tilsvarer den fortsatte brøkdelen av en kvadratisk irrasjonell representasjon av dette tallet i formen

{\ displaystyle a_ {0} + {\ cfrac {1} {a_ {1} + {\ cfrac {1} {a_ {2} + {\ frac {1} {a_ {3} + \, \ cdots}} }}}} \ quad {\ text {with}} \ quad a_ {0} \ in \ mathbb {Z} \ quad {\ text {and}} \ quad \ forall i> 0 \ quad a_ {i} \ in \ mathbb {N}}

Hvis det irrasjonelle tallet som er representert er kvadratisk, dvs. hvis det er løsningen på en kvadratisk ligning med rasjonelle koeffisienter , er sekvensen av heltall ( a n ) periodisk fra en viss rang.

Interessen for studiet av den fortsatte brøkdelen av en kvadratisk irrasjonell er ikke begrenset til dette. Enkelheten i algoritmen for å bestemme fraksjonens koeffisienter gjorde det til en kvadratrotutvinningsmetode i lang tid . Å kjenne den fortsatte brøkdelen gjør det blant annet mulig å løse den berømte Diophantine-ligningen kalt Pell-Fermat : x 2 - ny 2 = ± 1.

Innledning

Introduksjon til et eksempel

Vi kan beregne den fortsatte brøkdelen av en kvadratisk irrasjonell ved å bruke den bemerkelsesverdige identiteten ( a + b ) ( a - b ) = a 2 - b 2 i hvert trinn, som i det følgende eksemplet.

{\ sqrt {13}} = 3 + (- 3 + {\ sqrt {13}}) = 3 + {\ frac {({\ sqrt {13}} - 3) ({\ sqrt {13}} + 3 )} {{\ sqrt {13}} + 3}} = 3 + {\ frac 4 {3 + {\ sqrt {13}}}} = 3 + {\ frac 1 {{\ frac {{\ sqrt {13 }} + 3} 4}}}

{\ displaystyle a_ {0} = 3, ~ x_ {1} = {\ frac {{\ sqrt {13}} + 3} {4}}}

Ved å bruke den samme algoritmen på x 1 :

{\ frac {{\ sqrt {13}} + 3} 4} = 1 + {\ frac {{\ sqrt {13}} - 1} 4} = 1 + {\ frac 1 {{\ frac {{\ sqrt {13}} + 1} 3}}} \ quad {\ text {derfor}} \ quad {\ sqrt {13}} = 3 + {\ cfrac 1 {1 + {\ cfrac 1 {{\ frac {{\ sqrt {13}} + 1} 3}}}}

og så :

a_ {1} = 1, ~ x_ {2} = {\ frac {{\ sqrt {13}} + 1} 3}

Vi beregner på samme måte : $x_ {3}$

{\ displaystyle {\ frac {{\ sqrt {13}} + 1} {3}} = 1 + {\ frac {1} {\ frac {{\ sqrt {13}} + 2} {3}}} \ quad {\ text {derfor}} \ quad {\ sqrt {13}} = 3 + {\ cfrac {1} {1 + {\ cfrac {1} {1 + {\ frac {1} {\ frac {{\ sqrt {13}} + 2} {3}}}}}} \ quad {\ text {and}} \ quad a_ {2} = 1, ~ x_ {3} = {\ frac {{\ sqrt {13 }} + 2} {3}}.}

man fortsetter slik og man beregner følgende vilkår for utviklingen til : ${\ displaystyle x_ {6}}$

{\ displaystyle x_ {3} = {\ frac {{\ sqrt {13}} + 2} {3}} = 1 + {\ frac {1} {1 + {\ frac {1} {6 + {\ frac {1} {\ frac {{\ sqrt {13}} + 3} {4}}}}}}}

endelig :

${\ displaystyle a_ {3} = 1, ~ a_ {4} = 1, ~ a_ {5} = 6, ~ x_ {6} = {\ frac {{\ sqrt {13}} + 3} {4}} .}$

Ordforrådet og notasjonene som brukes her er de som er definert i artikkelen " Kontinuerlig brøk ": den delvise kvotienten a n er hele delen av den totale kvotienten x n , og dens brøkdel er 1 / x n +1 . Den reduserte indeksen n betegner den avkortede kontinuerlige fraksjonen som inneholder n fraksjonsstenger og konstruert ved bruk av n + 1 koeffisienter; det er betegnet h n / k n . Hvis vi erstatter en n –1 med en n –1 + 1 / x n i uttrykket for reduksjon av indeks n - 1, får vi nøyaktig det opprinnelige tallet. Full kvotient x 0 er startverdien.

I det valgte eksemplet,

x_ {0} = {\ sqrt {13}} = 3 + {\ cfrac 1 {1 + {\ cfrac 1 {1 + {\ cfrac 1 {1 + {\ frac 1 {1 + {\ frac 1 {6+ \ cdots}}}}}}}}} \ quad {{\ rm {and}}} \ quad {\ frac {h_ {0}} {k_ {0}}} = {\ frac 31}, ~ { \ frac {h_ {1}} {k_ {1}}} = {\ frac 41}, ~ {\ frac {h_ {2}} {k_ {2}}} = {\ frac 72}, ~ {\ frac {h_ {3}} {k_ {3}}} = {\ frac {11} 3}, ~ {\ frac {h_ {4}} {k_ {4}}} = {\ frac {18} 5}, ~ {\ frac {h_ {5}} {k_ {5}}} = {\ frac {119} {33}}

Denne betegnelsen er litt tung, vi bruker helst følgende med samme betydning:

{\ displaystyle {\ sqrt {13}} = [3,1,1,1,1,6 \ cdots]}

Til slutt er hele kvotienten lik , noe som gjør det mulig å konkludere med at koeffisientrekkefølgen blir gjentatt fra rang 1. Vi snakker om en "periodisk sekvens fra en viss rang" og vi bruker notasjonen: ${\ displaystyle x_ {6}}$ $x_ {1}$

{\ displaystyle {\ sqrt {13}} = [3, {\ overline {1,1,1,1,6}}}}

linjen som betyr en uendelig repetisjon av den endelige serien av heltall den dekker.

Historieelementer

Fra VI th århundre , Aryabhata ( 476 - 550 ) , en matematiker indiske bruksområder fortsatte fraksjoner for rasjonelle nær kvadratrøtter av heltall. Hvis Brahmagupta ( 598 - 668 ) , en annen indisk matematiker, er interessert i ligningen til Pell og bruker en bemerkelsesverdig identitet for å løse, var det ikke før XII - tallet og Bhāskara II å se en lignende tilnærming til de fortsatte brøkene som ble brukt på dette ligning. Algoritmen, chakravala-metoden , tilsvarer den i artikkelen, med den forskjellen at et 0 ikke alltid er mindre enn tallet som skal kontaktes. Denne forskjellen blir overført til alle koeffisientene et n , som kan bli negativ. Denne spesifisiteten fremskynder søket etter løsningen litt.

Det var først senere at Europa ble interessert i en slik tilnærming. Først på XVI - tallet som Rafael Bombelli benytter seg av en forfader til fortsatte brøker for å beregne tilnærminger av kvadratroten av 13. Pietro Antonio Cataldi forstår omfanget av metoden til Bombelli og gjelder for alle kvadratrøtter, i et lite hefte på dette emnet velger han eksemplet på verdien 18. Vi finner lignende resultater med Albert Girard i 1625, deretter 1634, til å tilnærme √ 2 og √ 10 .

Etter en utfordring som Pierre de Fermat lanserte i 1657, finner William Brouncker empirisk forholdet som forbinder den fortsatte brøkdelen av en kvadratisk irrasjonell til Pell-Fermat-ligningen. Det er sannsynlig at Bernard Frénicle de Bessy også kjente denne metoden for å løse Pell-Fermat-ligningen som han fant alle løsningene for n under 150, men dette arbeidet har gått tapt; han utfordrer Brouncker til å finne en løsning på ligningen for n = 313. I svaret hans indikerer sistnevnte at det ikke tok ham "mer enn en time eller to å finne den". Dette svaret er som følger:

x = 32 \, 188 \, 120 \, 829 \, 134 \, 849 \ quad {\ text {and}} \ quad y = 1 \, 819 \, 380 \, 158 \, 564 \, 160 \;

Denne informasjonen kommer fra et intenst epistolært forhold mellom de forskjellige aktørene, som til slutt ble publisert av John Wallis i 1658.

Det neste århundret er demonstrasjonens. Leonhard Euler tar opp arbeidet til Brouncker og Wallis, og demonstrerer nøye alle de litt elementære aspektene av teorien; det viser også at hvis den fortsatte brøkrepresentasjonen av et tall er periodisk, fra en viss rang, så er dette tallet en kvadratisk irrasjonell. Vi må fremdeles vente på arbeidet til Joseph-Louis Lagrange for demonstrasjonen av en gjensidig samt årsakene til gyldigheten av Bhāskara II-metoden eller Brouncker. Egenskapene til den fortsatte fraksjonen av en kvadratisk irrasjonell blir deretter i det vesentlige belyst; Det gjenstår bare å forstå i hvilket tilfelle en fortsatt brøkdel ikke bare er periodisk fra en viss rang, men ren periodisk, som Évariste Galois oppnådde i 1828.

Periode

Enhver irrasjonell hvis kontinuerlige fraksjonsutvidelse er periodisk, er en kvadratisk irrasjonell ( a fortiori , dens fulle kvoter også).

Eksempel Det irrasjonelle er lik med .

{\ displaystyle x = [0,1,1,2,1,2,1,2, \ dots] = [0,1, {\ overline {1,2}}]}

{\ displaystyle 0 + {\ frac {1} {1 + {\ frac {1} {y}}}} = {\ frac {y} {y + 1}}}

{\ displaystyle y = [{\ overline {1,2}}] = 1 + {\ frac {1} {2 + {\ frac {1} {y}}}}}

Ved å erstatte med i denne ligningen og deretter forenkle den, finner vi .

y

{\ displaystyle {\ frac {x} {1-x}}}

{\ displaystyle 3x ^ {2} -1 = 0}

Denne implikasjonen er kjernen i interessen for forestillingen om fortsatt brøkdel for kvadratiske irrasjonelle fordi (mer enn et århundre etter oppdagelsen) Lagrange har lykkes med å demonstrere det omvendte:

Lagranges teorem - En irrasjonell er kvadratisk hvis og bare hvis dens fortsatte brøkekspansjon er periodisk fra en viss rang.

Lagrange til og med vist seg at for en kvadratisk irrasjonell av formen ( P + $\sqrt D$ ) / Q , de partielle kvotienter har jeg blir økt med 2 $\sqrt D$ og perioden 2 D . Finere argumenter, basert på divisorfunksjonen , viser at denne perioden er en stor O av $\sqrt D$ $log ( D )$ .

Rent periodisk utvikling

Den p -periodicity fra en rang r av utviklingen av en kvadratisk irrasjonell x er skrevet, med den samme notasjon som i ingressen:

{\ displaystyle x = [a_ {0}, a_ {1}, \ cdots, a_ {r-1}, a_ {r}, a_ {r + 1}, \ cdots a_ {r + p-1}, a_ {r}, a_ {r + 1} \ cdots \;] = [a_ {0}, a_ {1}, \ cdots, a_ {r-1}, {\ overline {a_ {r}, a_ {r + 1}, \ cdots a_ {r + p-1}}}}}

Noen tall har en ren periodisk utvikling, det vil si fra den første koeffisienten ( r = 0). Dette er for eksempel tilfellet med det gyldne forholdet φ. Faktisk,

{\ displaystyle \ varphi = 1 + {\ frac {1} {\ varphi}} = 1 + {\ frac {1} {1 + {\ frac {1} {\ varphi}}}} = \ cdots \ quad { \ text {et}} \ quad \ varphi = [1,1,1, \ cdots] = [{\ overline {1}}]}

Spørsmålet oppstår i hvilket tilfelle utviklingen i en fortsatt brøkdel er ren periodisk. Antallet x er nødvendigvis et kvadratisk irrasjonelt, derfor er dets minimale polynom av grad 2. Svaret - bevist av Galois (mens han fremdeles var videregående) men allerede implisitt i det forrige arbeidet til Lagrange - uttrykkes i henhold til konjugatet x c av x , som er den andre roten til dens minimale polynom:

Galois- setning - Hvis x har en ren periodisk kontinuerlig brøkutvidelse x = [ a 0 , a 1 ,…, a p –1 ], tilfredsstiller dens konjugat x c –1 / x c = [ a p –1 ,…, a 1 , a 0 ]. Spesielt er x en redusert kvadratisk irrasjonell, dvs. x > 1 og –1 < x c <0.

Motsatt er den fortsatte fraksjonsutvidelsen av enhver redusert kvadratisk irrasjonell rent periodisk.

Palindrom

Den forrige egenskapen gir en mer presis beskrivelse av den fortsatte brøkekspansjonen av en rot av en ikke- kvadratisk rasjonell :

Legendres teorem - Hvis d > 1 er en ikke-kvadratisk rasjonell, er den fortsatte brøkdelen av $\sqrt d$ av formen

{\ displaystyle {\ sqrt {d}} = [a_ {0}, {\ overline {a_ {1}, a_ {2}, a_ {3} \ cdots, a_ {3}, a_ {2}, a_ { 1}, 2a_ {0}}}]}

Omvendt er enhver irrasjonell hvis fortsatte brøkdel er av denne formen kvadratroten til en rasjonell.

Den palindrome som deretter danner periode fratatt sin siste periode to til å 0 har en median sikt hvis og bare hvis denne perioden er av jevn lengde. For eksempel √ 13 = [3, 1, 1, 1, 1, 6 ] og √ 19 = [4, 2, 1, 3, 1, 2, 8 ].

Pell-Fermat ligning

Løsningsstruktur

Den fortsatte fraksjonen er både en teoretisk og en praktisk teknikk for å løse følgende Pell-Fermat-ligning , hvis d er et ikke-kvadratisk positivt heltall:

{\ displaystyle (1) \ quad x ^ {2} -dy ^ {2} = \ pm 1}

En løsning er et par ( a , b ) av heltall slik at en 2 - db 2 er lik ± 1. Bortsett fra de trivielle løsningene (1, 0) og (–1, 0), blir alle utledet fra de som a og b er strengt positive for, ved å endre tegnet på a eller b . Tre forslag gjør det mulig å forstå hvordan løsningene er strukturert:

Ethvert par strengt positive heltalsløsning av ligning (1) er lik tellerparet og nevneren til en av reduksjonene på $\sqrt d$ .
Den reduserte i-t av $\sqrt d$ tilsvarer en løsning av ligning (1) hvis og bare i + 1 er delelig med perioden $\sqrt d$ .
Hvis denne perioden p er merkelig, er det løsninger for verdien –1: de tilsvarer indeksene i = qp - 1 for q odd, de for q gir til og med verdien 1. Hvis perioden p er jevn, er verdien –1 blir aldri nådd.

Enhetsgruppe

I algebraisk tallteori er det noen ganger viktig å kjenne gruppestrukturen til enhetene til en ring av algebraiske heltall . Denne situasjonen oppstår spesielt for ringene til kvadratiske heltall. Å forstå denne strukturen er nyttig, for eksempel for å demonstrere Fermats siste setning for n = 3 eller 5 , eller for å etablere loven om utseende av primtall i Fibonacci-sekvensen (jf. “ Ring av heltall på of ( √ 5 ) ”) .

Vi blir ledet til å lete etter de inverterbare elementene i ringen ℤ [ω] som har form a + b ω hvor ω er et kvadratisk heltall og a og b er elementer av ℤ. Vi viser at dette tilsvarer å løse en av de følgende to diofantiske ligningene, der d er et perfekt ikke-kvadratisk heltall og f et helt tall slik at 4 f + 1 ikke er et perfekt kvadrat:

{\ displaystyle (1) \; x ^ {2} -dy ^ {2} = \ pm 1 \ quad (2) \; x ^ {2} + xy-fy ^ {2} = \ pm 1}

Den første for d > 0 er allerede studert. Siden løsningene a + b $\sqrt d$ med a og b > 0 er gitt, i økende rekkefølge av a , av kreftene til den grunnleggende enheten h p –1 + k p –1 $\sqrt d$ (hvor p er perioden $\sqrt d$ ) og er også, ifølge ovenstående, h qp –1 + k qp –1 $\sqrt d$ (for q > 0), har vi h qp –1 + k qp –1 $\sqrt d$ = ( h p - 1 + k p –1 $\sqrt d$ ) q , som gir en måte å direkte beregne denne følgen av reduksjonene av $\sqrt d$ , ved hjelp av binomialformelen eller ved induksjon.

Den andre for f > 0 er veldig lik. Vi har først en analog av den første av de tre egenskapene til forrige avsnitt:

Hvis d = 4 f + 1, og hvis paret av heltall ( a , b ), med b > 0 og a + b / 2 ≥ 0, er løsning av ligning (2), så er a / b redusert av

{\ displaystyle \ alpha: = {\ frac {{\ sqrt {d}} - 1} {2}}}

. Demonstrasjon

Enten . ${\ displaystyle \ omega = {\ frac {1 + {\ sqrt {d}}} {2}}}$

(x + \ omega y) (x- \ alpha y) = \ left (x + \ tfrac y2 + \ sqrt d \ tfrac y2 \ right) \ left (x + \ tfrac y2- \ sqrt d \ tfrac y2 \ right ) = \ venstre (x + \ tfrac y2 \ høyre) ^ 2-d \ venstre (\ tfrac y2 \ høyre) ^ 2 = x ^ 2 + xy + \ frac {1-d} 4y ^ 2

derfor er ligning (2) skrevet:

{\ displaystyle \ left (x + {\ tfrac {y} {2}} \ right) ^ {2} -d \ left ({\ tfrac {y} {2}} \ right) ^ {2} = (x + \ omega y) (x- \ alpha y) = \ pm 1}

La ( a , b ) være et løsningspar slik at b ≥ 1 og a + b / 2 ≥ 0, får vi på den ene siden

\ left (\ frac ab + \ omega \ right) \ left (\ frac ab- \ alpha \ right) = \ frac {\ pm 1} {b ^ 2} \ quad \ text {derfor} \ quad \ left | \ frac ab- \ alpha \ right | = \ frac 1 {b ^ 2 \ left (\ frac ab + \ omega \ right)}

Og på den annen side

{\ displaystyle {\ tfrac {a} {b}} + \ omega = {\ tfrac {a} {b}} + {\ tfrac {1} {2}} + {\ tfrac {1} {2}} { \ sqrt {d}} \ geq {\ frac {1} {2}} \ left ({\ sqrt {d - {\ tfrac {4} {b ^ {2}}}}} + {\ sqrt {d} } \ Ikke sant)}

Den nedre grensen til høyre er generelt strengt større enn 2, og vi får deretter følgende øvre grense, som viser at a / b er redusert av α:

{\ displaystyle \ left | {\ frac {a} {b}} - \ alpha \ right | <{\ frac {1} {2b ^ {2}}}}

Det eneste unntaket oppstår når d = 5 og b = 1: ${\ frac 12} \ left ({\ sqrt {5-4}} + {\ sqrt 5} \ right) <2$ men i dette tilfellet er a lik 0 eller 1, eller 0/1 og 1/1 er faktisk reduksjoner av ( √ 5 - 1) / 2 = φ - 1 = [0, 1 ].

De to andre egenskapene kan generaliseres som følger, gjelder derfor α = $\sqrt d så vel$ som (hvis d er kongruent til 1 modulo 4) til α = ( $\sqrt d$ - 1) / 2:

La α være en kvadratisk heltall (ikke heltall) som er større enn dets konjugat, p sin periode og h i / k i sin redusert.

N ( h i - k i α) = ± 1 hvis og bare i + 1 er delelig med p ;
hvis p er oddet, er det løsninger for verdien –1: de tilsvarer indeksene i = qp - 1 for q odd, de for q gir til og med verdien 1. Hvis p er jevn, blir verdien –1 aldri nådd.

Ekstrahering av en kvadratrot

Første metode

Egenskapene til den fortsatte brøkdelen av en kvadratisk irrasjonell gjør det mulig å beregne tilnærminger av kvadratrøttene . Den første teknikken består ganske enkelt i å beregne koeffisientene til den fortsatte fraksjonen og deretter den reduserte. For eksempel :

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

Den reduksjoner h n / k n blir beregnet ved induksjon :

{\ begin {align} h _ {{- 1}} = 1, \ quad & h_ {0} = a_ {0}, \ quad & h _ {{n + 2}} = a _ {{n + 2 }} h _ {{n + 1}} + h_ {n}, \\ k _ {{- 1}} = 0, \ quad & k_ {0} = 1, \ quad & k _ {{n + 2 }} = a _ {{n + 2}} k _ {{n + 1}} + k_ {n}, \ end {justert}}

som gir følgende tilnærminger av √ 3 :

{\ begin {align} h_ {0} & = 1, & h_ {1} & = 2, & h_ {2} & = 2 \ ganger 2 + 1 = 5, & h_ {3} & = 1 \ ganger 5 + 2 = 7, & h_ {4} & = 19, & h_ {5} & = 26, & \ cdots \, h _ {{10}} & = 989 \\ k_ {0} & = 1, & k_ {1} & = 1, & k_ {2} & = 2 \ ganger 1 + 1 = 3, & k_ {3} & = 1 \ ganger 3 + 1 = 4, & k_ {4} & = 11, & k_ {5} & = 15, & \ cdots \, k _ {{10}} & = 571. \ end {justert}}

Således, ved 10 th trinnet, får vi fraksjonen 989/571, omtrent 1732 til 049, mens de første 7 s signifikante tall er 1732 051. Nøyaktigheten av algoritmen til trinn n er bedre enn 1 / k n 2 (og jevn, siden her er perioden 2, bedre enn 1 / (2 k n 2 ) hvis n er merkelig, i henhold til § "Løsningsstruktur" ovenfor). For tilnærming til indeks 10 vet vi derfor at feilen er mindre enn 1/571 2 , bedre enn 300 000 th . En styrke i denne algoritmen er "kvaliteten" på de foreslåtte løsningene, hvor en hvilken som helst brøkdel av typen a / b med b strengt mindre enn 571 nødvendigvis vil være mindre god enn den reduserte tidelen av den fortsatte brøkdelen, i betydningen ovenfor (og til og med i en finere betydning, spesifisert i artikkelen Continuous fraction and Diophantine approximation ). For eksempel, den beste desimale tilnærmingen til roten av 3 med to signifikante sifre, lik 17/10, begår en feil større enn 50 th . Denne noe ekvivalente 19/11 tilsvarer den reduserte verdien på 4 gir en tilnærming til 100 e , to ganger bedre.

Akselererende konvergens

Løsningene ( a q , b q ) = ( h qp –1 , k qp –1 ) av Pell-Fermat-ligningen gir en sekvens ekstrahert fra reduksjonssekvensen på $\sqrt n$ , som derfor konvergerer raskere enn sistnevnte. Siden en q + b q $\sqrt n$ er av formen ( a + b $\sqrt n$ ) q , kan vi videre akselerere konvergensen ved bare å beregne noen av disse kreftene, for eksempel u j + v j $\sqrt n$ = ( a + b $\sqrt n$ ) 2 d . Siden

u _ {{j + 1}} + v _ {{j + 1}} {\ sqrt n} = (u_ {j} + v_ {j} {\ sqrt n}) ^ {2},

denne konsekvensen beregnes ved induksjon av:

u_ {0} = a, \ quad v_ {0} = b, \ quad u _ {{j + 1}} = u_ {j} ^ {2} + nv_ {j} ^ {2} \ quad {\ text {and}} \ quad v _ {{j + 1}} = 2u_ {j} v_ {j}.

For eksempel for n = 3 finner vi a = h 1 = 2 og b = k 1 = 1 (jf. Forrige §) da

{\ begin {align} u_ {0} & = 2, & u_ {1} & = 2 ^ {2} +3 \ ganger 1 ^ {2} = 7, & u_ {2} & = 7 ^ {2} +3 \ ganger 4 ^ {2} = 97, & u_ {3} & = 97 ^ {2} +3 \ ganger 56 ^ {2} = 18 \, 817, & u_ {4} & = 708 \, 158 \, 977 \ \ v_ {0} & = 1, & v_ {1} & = 2 \ ganger 2 \ ganger 1 = 4, & v_ {2} & = 2 \ ganger 7 \ ganger 4 = 56, & v_ { 3} & = 2 \ ganger 97 \ ganger 56 = 10 \, 864, & v_ {4} & = 408 \, 855 \, 776 \ end {justert}}

og presisjonen på u 4 / v 4 overstiger allerede 18 desimaler.

Rasjonalsekvensen x j = u j / v j er ingen ringere enn den som produseres av Herons metode fra x 0 = a / b . I følge definisjonen av sekvensene ( u j ) og ( v j ) har vi faktisk

{\ displaystyle x_ {j + 1} = {\ frac {x_ {j} + {\ frac {n} {x_ {j}}}} {2}}}

Konvergensen er derfor kvadratisk .

Et historisk eksempel på å løse Pell Fermat-ligningen

Følgende ligning har en lang historie:

{\ displaystyle x ^ {2} -61y ^ {2} = 1}

Brahmagupta brukt som illustrasjon av en forfader til chakravala-metoden på VII - tallet. Det tas opp av Bhāskara II som perfeksjonerer metoden og gir den en algoritmisk kraft litt høyere enn den for fortsatte brøker, presentert her.

I februar 1657 (etter en annen mer kjent utfordring fra 3. januar samme år) blir eksemplet igjen tatt opp av Pierre de Fermat i et brev til Bernard Frénicle de Bessy (han foreslår også saken n = 109). Denne utfordringen er opprinnelsen til det engelske arbeidet med de fortsatte brøkene av kvadratiske irrasjonelle og deres forbindelse med Pell-Fermat-ligningen.

La oss bruke den fortsatte brøkalgoritmen for å beregne hele og delvise kvoter:

x_ {0} = {\ sqrt {61}} = 7 + {\ frac 1 {x_ {1}}}, \ quad x_ {1} = {\ frac {7 + {\ sqrt {61}}} {12 }} = 1 + {\ frac 1 {x_ {2}}}, \ quad x_ {2} = {\ frac {5 + {\ sqrt {61}}} 3} = 4 + {\ frac 1 {x_ { 3}}},

\ quad x_ {3} = {\ frac {7 + {\ sqrt {61}}} 4} = 3 + {\ frac 1 {x_ {4}}}, \ quad x_ {4} = {\ frac {5 + {\ sqrt {61}}} 9} = 1 + {\ cfrac 1 {x_ {5}}}, \ quad x_ {5} = {\ frac {4 + {\ sqrt {61}}} 5} = 2 + {\ frac 1 {x_ {6}}}, \ quad x_ {6} = {\ frac {6 + {\ sqrt {61}}} 5},

som gir de første delkvotientene: 7, 1, 4, 3, 1, 2. Det er ikke lenger nødvendig å fortsette. Faktisk er de komplette kvotientene x 5 og x 6 assosiert fordi de har samme nevner. Halvparten av palindromet er derfor allerede forklart. Ettersom dette fenomenet forekommer for to tilstøtende indekser, kan vi utlede at perioden er merkelig og lik 2 × 5 + 1. Vi kan også utlede at en 6 er lik en 5 , samt følgende termer: 2, 1, 3, 4, 1. Til slutt er den siste betegnelsen lik den doble av den første, det vil si 14. Den første løsningen er da den for indeks 10, hvis posisjon er markert med rødt i følgende uttrykk:

{\ displaystyle {\ sqrt {61}} = [7, {\ overline {1,4,3,1,2,2,1,3,4, {\ color {Red} 1}, 14}}]}

Ved gjentakelsesformlene (som i § “Første metode” ) oppnår vi:

{\ displaystyle {\ begin {align} h_ {1} & = 8, & h_ {2} & = 39, & h_ {3} & = 125, & h_ {4} & = 164, & \ cdots & \, h_ {10} & = 29 \; 718 \\ k_ {1} & = 1, & k_ {2} & = 5, & k_ {3} & = 16, & k_ {4} & = 21, & \ cdots & \, k_ {10} & = 3 \; 805. \ end {justert}}}

Vi vet, siden perioden er merkelig, at denne første løsningen gir h 10 2 - 61 k 10 2 = –1 og ikke +1. Verken Brahmagupta eller Fermat godtar denne typen løsninger. Den riktige reduksjonen er derfor 21. st . For å beregne det, kan vi enten utvide beregningen, eller bruke det samme prinsippet som for den andre metoden for å trekke ut en rot:

{\ displaystyle h_ {21} + k_ {21} {\ sqrt {61}} = (h_ {10} + k_ {10} {\ sqrt {61}}) ^ {2}}

Løsningen på Fermats utfordring er:

{\ displaystyle h_ {21} = 1 \, 766 \, 319 \, 049, \ quad k_ {21} = 226 \, 153 \, 980 \ quad {\ text {and}} \ quad h_ {21} ^ { 2} -61 \ ganger k_ {21} ^ {2} = 1}

Merknader og referanser

(fr) Denne artikkelen er delvis eller helt hentet fra den engelske Wikipedia- artikkelen med tittelen “ Periodic continu fraction ” ( se listen over forfattere ) .

Georges Ifrah , Universell tallhistorie : Mennes intelligens fortalt av tall og beregninger , Robert Laffont, 1994 ( ISBN 978-2-70284212-6 ) .
(it) MT Rivolo og A. Simi, " he calcolo delle radici quadrate e cubiche in Italia da Fibonacci Bombelli " , Arch. Hist. Nøyaktig Sci. , vol. 52, n o to1998, s. 161-193.
(it) S. Maracchia, " Estrazione di secondo Cataldi radice quadrata " , Archimede , vol. 28, n o to1976, s. 124-127.
(in) Leonard Eugene Dickson , Diophantine analysis , AMS Bookstore, 1999 ( ISBN 0821819356 ) , pp. 355-356 , forhåndsvisning på Google Bøker .
(La) John Wallis, Commercium epistolicum de quæstionibus quibusdam mathemataticis nuper habitum Oxonii: Excudebat A. Lichfield, Impensis Tho. Robinson, 1658.
(La) Leonhard Euler, Introductio in analysin infinitorum , 1748, vol. I (E101), kap. 18, § 379 [ lest online ] .
Joseph-Louis Lagrange, tillegg til avhandlingen om oppløsning av numeriske ligninger, § II. - Om måten å nærme seg den numeriske verdien av ligningens røtter , 1770, gjentatt. Joseph-Alfred Serret , Works of Lagrange , vol. II, Gauthier-Villars ,1877( les online ) , s. 593-652, mer presist: Merknad II, s. 603-622 .
Ulike resultater er publisert i Lagrange's Additions to Élémens d'Algebre av Léonard Euler, bind 2: de analyse indeterminée , 1 re éd., Bruyset and Desaint, 1774, s. 379-658 + 662-664 , og to th utg., Bruyset, 1798, s. 379-662 + 666-668 , omtrykt i: Serret 1877 , Œuvres de Lagrange , vol. VII, s. 5-180 . Se også Serret 1877 , Œuvres de Lagrange , vol. Jeg, s. 671-731, “ Løsning av et aritmetisk problem ”.
Évariste Galois , “ Demonstration of a theorem on periodic fortsatt brøk ”, Annals of pure and anvendt matematikk , vol. 19, 1828-1829, s. 294-301 ( les online )på bibnum , analysert av Norbert Verdier, Christian Gérini og Alexandre Moatti.
For en demonstrasjon, se for eksempel (de) Oskar Perron , Die Lehre von den Kettenbrüchen , Teubner,1913( les online ), § 20 ( s. 73-77 ) eller § 21 ( s. 77-79 ), eller denne øvelsen korrigert fra leksjonen "Introduksjon til tallteori" på Wikiversity .
(in) Dean R. Hickerson, " Length of single period of continue fraction expansion of $\sqrt d$ " , Pacific J. Math. , vol. 46,1973, s. 429-432 ( DOI 10.2140 / pjm.1973.46.429 ).
(in) JHE Cohn, " Lengden på perioden med den fortsatte brøkdelen av lett til 1/2 " , Pacific J. Math. , vol. 71, n o 1,1977, s. 21-32 ( les online ).
(en) EV Podsypanin, " Lengden på en kvadratisk irrasjonell periode " , Journal of Soviet Mathematics , vol. 18, n o 6,1982, s. 919-923 ( DOI 10.1007 / BF01763963 ).
(in) Harold Davenport , The Higher Arithmetic: An Introduction to Theory of Numbers , Cambridge University Press ,1999, 7 th ed. , 241 s. ( ISBN 978-0-521-63446-5 , leses online ) , s. 99.
For en demonstrasjon, se for eksempel Perron 1913 , s. 80-82, eller denne korrigerte øvelsen fra leksjonen "Introduksjon til tallteori" på Wikiversity .
Denne setningen tilskrives Legendre i (en) Kiyoshi Itō , Encyclopedic Dictionary of Mathematics , vol. 1, MIT Trykk ,1993, 2 nd ed. , 1147 s. ( ISBN 978-0-262-59020-4 , leses online ) , s. 315-316. Men AM Legendre , essay om tallteori ,1798( les online ) , s. 50-57(som Davenport 1999 , s. 104) er bare interessert i tilfelle der $d$ er heltall, og bare beviser den direkte betydningen. For en komplett demonstrasjon, se for eksempel Perron 1913 , s. 87-88, eller denne korrigerte øvelsen fra leksjonen "Introduksjon til tallteori" på Wikiversity .
(in) Eric W. Weisstein , " Periodic Continued Fraction " på MathWorld .
Perron 1913 , s. 102-104. Den første egenskapen demonstreres også i denne korrigerte øvelsen av leksjonen "Introduksjon til tallteori" på Wikiversity . De to andre vil bli generalisert og demonstrert i følgende §.
Perron 1913 , s. 104, bevis det direkte ved å bruke gjentakelsesformlene på reduksjonene og det faktum at a p = 2 a 0 .
For en demonstrasjon, se for eksempel dette leksene som er korrigert i Pell-Fermat-ligningen på Wikiversity .
Med bruk av denne ( se ovenfor ) eller ved direkte beregning, som i denne øvelsen korrigert på Wikiversity . ${\ displaystyle {\ frac {1} {\ sqrt {3}}} = [0,1, {\ overline {1,2}}]}$
(in) BL van der Waerden , " Pells ligning i gresk og hinduematematikk " , Russ. Math Surveys (in) , vol. 31, n o 5,1976, s. 210-225.
Bhāskara II , Bijaganita , 1150, ifølge (i) John J. O'Connor og Edmund F. Robertson , "Pells ligning" i MacTutor History of Mathematics archive , University of St. Andrews ( les online )..
Works of Fermat , s. 334 .

Se også

Bibliografi

(en) Alan Baker , en kort introduksjon til teorien om tall , Cambridge University Press,1985, 95 s. ( ISBN 978-0-521-28654-1 , les online )
Alain Faisant , Diophantine-ligningen av andre grad , Hermann ,1991, 237 s. ( ISBN 978-2-7056-1430-0 )
Marc Guinot, Aritmetikk for amatører. Flygning. 4: Lagrange og Legendre , Aléas, 1996 ( ISBN 978-2-908016-71-0 )
(en) GH Hardy og EM Wright , En introduksjon til teorien om tall ( 1 st ed. 1938) [ Retail Editions ]
(en) Alexandre Junod, “ En algoritme for å løse en Pell-ligning ” , General Mathematics Notes , vol. 28, n o to2015, s. 1-8 ( les online )
Pierre Samuel , algebraisk tallteori [ detalj av utgaven ]
Georges Valiron , funksjonsteori , 3- e utg., Masson , 1966 Primer på aritmetiske fortsatte fraksjoner, s. 17-24
Sabah Al Fakir , algebra og tallteori - Kryptografi: Primality , Paris, Ellipses ,2003, 276 s. ( ISBN 2-7298-1480-9 ) (kapittel 9, Diophantine approximations)

Eksterne linker

Claude Brezinski, “ Disse rare fraksjonene som aldri tar slutt ” ,Oktober 2005, lysbildefremvisning av en konferanse på IREM , University of Reunion
Marcel Couchouron, " Utvikling av en real i kontinuerlige fraksjoner " , på University of Rennes I