I matematikk og mer spesifikt i aritmetikk er chakravala- metoden en algoritme for å løse Pell-Fermat-ligningen . Denne ligningen er et eksempel på en diofantinligning , det vil si med heltallskoeffisienter og hvis heltalsløsninger blir søkt. Mer presist er det ligningen
der n er et naturlig ikke- kvadratisk tall .
Denne metoden ble utviklet i India, og dens røtter kan spores tilbake til VI - tallet med Aryabhata , etterfulgt av Brahmagupta . Initiert av Jayadeva (en) , ble den videreutviklet av Bhāskara II .
Selenius vurderer det ved: “Metoden representerer en beste tilnærmingsalgoritme av minimumslengde som på grunn av flere minimeringsegenskaper automatisk produserer [...], til lavere pris [...] og unngår store antall, minste løsninger av ligningen chakravāla- metoden gikk forut for europeiske metoder med mer enn tusen år. Men ingen europeiske forestillinger innen hele algebra , mye senere etter Bhāskara [...], har matchet den fantastiske kompleksiteten og oppfinnsomheten til chakravala . "
Det må faktisk forvente at XVII th -tallet at europeerne, som ignorerte arbeidet med indiske matematikere oppdager algoritmer - mindre effektive - løse det samme problemet.
En form for Pell-Fermat-ligning uttrykkes som følger:
der n er et naturlig ikke-kvadratisk tall. Ligningen er Diophantine som betyr at parene ( x , y ) som er søkt er par av heltall. Alle løsningene er uttrykt fra løsningen par dannet av to minimale heltall i absolutt verdi i settet med løsninger. Chakravala- metoden gjør det mulig å oppnå et par av denne naturen.
Følgende likhet er et eksempel på en løsning; Indianerne ble det kjent at VII th århundre:
Den indiske matematikken interesserte veldig tidlig regning. Aryabhata , en matematiker av det VI th århundre , etablerer baser. Han utvikler et tallsystem som viser at han sannsynligvis visste om posisjonell notasjon så vel som eksistensen av null . Han jobber med de diofantiske ligningene og for å løse identiteten til Bézout , utvikler en algoritme som tilsvarer den til Euclid som han kaller ku ṭ ṭ aka (कूटटक) og som betyr sprøyter fordi han bryter tallene i mindre heltall. Han jobber også med fortsatte brøker .
Den indiske matematikeren Brahmagupta ( 598 - 668 ) ser ut til å være den første som analyserer dette spørsmålet i dybden. Han forstår hvordan det fra to løsninger er mulig å bygge en ny. Ved å gjenta, oppnår han dermed så mange forskjellige løsninger som ønsket. Denne metoden kalles samasa av indiske matematikere. Brahmagupta trekker tre algoritmer ut av dette. Den første lar ham finne en løsning hvis han har et par heltall ( x , y ) hvis bilde av ligningen er –1. Han finner et sekund som handler om saken der bildet er 2 i absolutt verdi . Den finner en tredje som gir det samme resultatet hvis bildet er lik ± 4. Et utkast til metode blir født. Det begynner med en prøving og feiling til det finner et par som har for bilde 1, 2 eller 4 i absolutt verdi, det fortsetter med en av de tre algoritmene. Brahmagupta bruker den i 628 i sin bok Brahmasphuta siddhanta for å løse følgende ligning:
Denne tilnærmingen er ikke tilstrekkelig for å håndtere komplekse saker, det kan være vanskelig å finne et par ved prøving og feiling som gir en av de seks verdiene som tillater en konklusjon. I det XII th -tallet , Bhaskara bygger på tidligere avtaler og foreslår den endelige form av fremgangsmåten chakravala . Det tilsvarer tillegg av en syklisk algoritme, det vil si å gi en periodisk sekvens av par som nødvendigvis inneholder en løsning. Den sykliske algoritmen tilsvarer den for fortsatte brøker . Chakravala- metoden avsluttes med Brahmaguptas beregninger hvis en av verdiene –1, ± 2 og ± 4 forekommer. Bhāskara II brukte den i 1150 i sin avhandling Bijaganita for å finne en minimal løsning på følgende ligning som Brahmagupta allerede har funnet:
Løsningen par funnet er:
Det er usannsynlig at Bhaskara demonstrert at algoritmen har alltid en løsning, det vil si for noen verdi av n fordi demonstrasjonen, lang og teknisk, krever raffinement langt bedre enn matematikk XII th århundre. Nye eksempler blir behandlet senere av indiske matematikere. I XIV th århundre matematiker ved navn Narayana studere hvis n er lik 103 i sine kommentarer til boken Bijaganita av Bhaskara.
I februar 1657 (etter en annen mer kjent utfordring fra 3. januar samme år) utfordrer Pierre de Fermat Bernard Frénicle de Bessy og gjennom ham alle europeiske matematikere å løse (blant annet) problemet for n = 61. Den engelske reaksjonen er rask: William Brouncker finner en algoritme. Frénicle de Bessy foreslår deretter en tabell som inneholder alle løsningene for verdiene på n under 150, som til slutt vil gå tapt, så gjenoppdager John Wallis resultatene av Brahmagupta og demonstrerer dem grundig. Bessy's Frenicle utfordrer Brouncker med verdien n = 313; den mottar ikke bare løsningen, men påstanden om at forfatteren ikke trengte mer enn "en time eller to" for å finne.
De to underliggende teoretiske spørsmålene, nemlig om det eksisterer en løsning for et ikke-kvadratisk naturlig tall n, og hvis løsningen som finnes faktisk genererer alle de andre, blir endelig løst av Lagrange i 1767, av en algoritme som er mindre effektiv enn det - så ignorert av europeere - på grunn av Bhāskara, men korreksjonen av det er lettere å demonstrere. I 1930 hevder AA Krishnaswami Ayyangar (in) å være den første til å bevise det for chakravala .
Metodene som er foreslått her bruker kraften i den nåværende formalismen. Hvis det matematiske innholdet er analogt med Brahmagupta, gjenspeiler ikke utstillingsteknikkene og demonstrasjonene tanken til den indiske matematikeren. Følgende notasjoner brukes gjennom resten av artikkelen. Tenk på følgende Diophantine-ligning, der n er et ikke-kvadratisk naturlig tall:
La A være en ring av tall av formen en + √ n b , hvor a og b betegner to heltall, N kartleggingen som til et element av A knytter sin " normale " og fy kartleggingen som til et element av A knytter sin " konjugert ":
De funksjon N svarer til normen av A i betydning av algebraisk tallteori . Et element a + √ n b av A kalles roten til ligning (1) hvis og bare hvis normen er 1, dvs. hvis ( a , b ) er en løsning av (1).
Funksjonen has har også nyttige egenskaper. Det er en automorfisme av A :
Bøyningen φ er ufrivillig, det vil si at komponert to ganger på rad med seg selv, er lik identiteten, eller dens gjensidige sammenheng er lik seg selv:
Til slutt er produktet av to konjugerte elementer lik deres vanlige norm:
Hvis vi skriver α = a + √ n b , er dette begrunnet med følgende beregning:
Den første egenskapen som brukes er:
La α og β være to elementer av A , så:
Hvis α = a 1 + √ n a 2 og β = b 1 + √ n b 2 , skrives denne likheten:
Denne likestillingen, kjent som identiteten til Brahmagupta , ble kalt Samasa av indianerne. For å være overbevist om nøyaktigheten, er det tilstrekkelig å uttrykke N som en funksjon av automorfismen φ:
Et spesielt tilfelle tilsvarer at der β er et helt tall k , tar likheten følgende form:
La α være et element i A og k et heltall, så:
Faktisk er N (α) = N (φ (α)) = αφ (α), og hvis α er en løsning av (1) så er α k også for alle naturlige tall k (fordi normen for et produkt er lik produktet av normene), men kreftene til en annen reell enn 0, 1 og –1 er alle forskjellige.
Å forstå hvordan Brahmagupta gjør for å løse ligning (1) avhenger av tre proposisjoner:
La α være et element av A.
La oss behandle følgende eksempel på Brahmagupta med denne metoden:
La α = m + √ 83 , der heltallet m velges slik at normen N (α) = m 2 - 83 er minst mulig i absolutt verdi: m = 9, α = 9 + √ 83 , N (α) = –2. Et tidligere forslag viser at a- 2- / 2 er en løsning. Effektivt:
og
Fermat utfordringFermats utfordring løses på samme måte:
Brahmagupta gjør det på følgende måte: han merker at hvis α = 39 + 5 √ 61 så er N (α) lik –4. Åpenbart har Brahmagupta-formalismen ingenting å gjøre med den som brukes her, selv om beregningene er de samme. Beregner a 2- / 2:
Deretter beregner den α 3- / 8 og dens standard:
Løsningen er således α til 6 /64, være:
Metoden er bemerkelsesverdig økonomisk for en så gammel algoritme.
En vanskelighetsgrad med Brahmaguptas metode ligger i at det ikke alltid er lett å finne et tall α av A hvis norm er lik ± 1, ± 2 eller ± 4. Bidraget fra Bhāskara II beskrevet i Siddhanta Siroman består i å berike metoden med en algoritme som ufeilbarlig ender med å gi en "kvasi-løsning" av denne art.
Bhāskara II konstruerer ved induksjon en sekvens av elementer α j = a j + b j √ n av A som følger. Det første elementet i sekvensen er α 0 = 1, av norm k 0 = 1. La oss anta sekvensen definert i rekkefølge j . Vi konstruerer et element β j = m j + √ n . Det naturlige heltallet m j er slik at et j + m j b j er et multiplum av normen k j av α j - med andre ord slik at b j m j er kongruent til - a j modulo k j - og m j minimerer den absolutte verdien av normen m j 2 - n av β j . Elementet α j + 1 blir deretter definert av
eller
de ± som tilsvarer det tegn på N (α j ) - fordelen av å ta dette tegnet i betraktning er det derfor en j og f j er alltid positiv.
Vi vil se senere at tilstanden “ a j + m j b j multiple of k j ” tilsvarer “ m j congruent to - m j –1 modulo k j ”, som forenkler algoritmen.
La oss igjen velge n lik 61. Verdien på m 0 er lik 8 for å minimere | N (β 0 ) |. Faktisk er √ 61 mellom 7 og 8 og 8 2 - 61 = 3 <61 - 7 2 . Heltallet m 1 velges deretter blant de kongruente, modulo N (α 1 ) = N (8 + √ 61 ) = 8 2 - 61 = 3, at - m 0 = –8 derfor ved 1. Av de to påfølgende ordene 7 og 10 av denne aritmetiske sekvensen som omgir √ 61 , den som minimerer | N (β 1 ) | er m 1 = 7, som gir:
Resten av metoden er Brahmagupta . Chakravala- metoden gjør det nå mulig å løse Fermats utfordring uten prøving og feiling og med et minimum av beregning.
Narayana eksempelDette andre eksemplet er også hentet fra Siroman Siddhanta av Bhāskara II, kommentert av Narayana. For n = 103, m 0 = 10. Heltallet m 1 velges deretter for å være kongruent til –10 modulo N (α 1 ) = N (10 + √ 103 ) = 10 2 - 103 = –3. Som 8 < √ 103 <11 og 11 2 - 103 = 18 <103 - 8 2 , får vi m 1 = 11 og
Vi velger deretter m 2 kongruent til –11 modulo 6. Siden 7 < √ 103 <13 og 103 - 7 2 = 54 <13 2 - 103, får vi m 2 = 7 - merk deg ved denne anledningen at “minimer | m 2 - n | "Er ikke alltid sammenfallende med" minimer | m - √ n | "- deretter
Deretter må modulo 9, m 3 være kongruent til –7. For å minimere | N (β 3 ) |, må vi velge m 3 lik 11. Vi får
Brahmaguptas beregning lar oss konkludere: den etterspurte verdien er
Ikke-unikhetFølgende eksempel viser at tallet α j +1 definert fra α j ikke alltid er unikt: for n = 58 er α 1 lik 8 + √ 58 , av norm 6, da for m 1 kongruent til –2 modulo 6, minimum | m 1 2 - 58 | er 42, nås for de to verdiene 4 og 10 av m 1 . De to tilsvarende verdiene for α 2 er 15 + 2 √ 58 , med norm –7, og 23 + 3 √ 58 , med norm 7. For den første finner man imidlertid m 2 = 10 og for den andre, m 2 = 4 derfor for begge, α 3 = 38 + 5 √ 58 , med norm –6, deretter m 3 = 8 og α 4 = 99 + 13 √ 58 , med norm –1. Forgreningen var derfor bare midlertidig, og de to suitene gir den samme løsningen.
Et lemma beviser eksistensen av sekvensen brukt av Bhāskara II, vel vitende om at hvis k og b er primtall for hverandre, så finnes det for et heltall a , det er heltall m som a + bm kan deles med k . Faktisk, ved å løse Bézouts identitet - som indianerne allerede visste hvordan de skulle gjøre med Euclids algoritme - finner vi heltall v hvor 1 - bv er et multiplum av k , og det er tilstrekkelig å sette m = - av .
La a , b være coprime og m , n to heltall. Vi setter k = a 2 - nb 2 , c = am + bn og d = a + bm .
Hvis d er et multiplum av k, er c også, og de to heltallene c / k og d / k er coprime.
Dette lemmaet er øyeblikkelig ved å merke seg at ad - bc = k og at b er prime med k . Anvendt - med notasjonene i § “Metodens prinsipp” - til a = a j og b = b j , viser det at i hvert trinn av konstruksjonen av sekvensen (α j ), hvis m j er valgt iht. metoden som er angitt da α j β j er et multiplum av N (α j ), α j +1 er et element i A og et j +1 og b j +1 er koprime, noe som gjør det mulig å iterere konstruksjonen.
Vi kan videre merke at begrensningen (i valget av m j ) " a j + b j m delelig med N (α j )" tilsvarer " m kongruent til - m j –1 modulo N (α j )". Faktisk er b j prime med N (α j ) og a j + b j (- m j –1 ) er delelig med N (α j ) siden φ (α j ) β j –1 = ± N (α j ) φ (α j –1 ).
Når vi har vist at sekvensen (α j ) er veldefinert, la oss studere dens oppførsel. Det er "syklisk" i en viss forstand. Mer presist, ved å merke cl (α) ekvivalensklassen til α for forholdet "å bli assosiert " (det vil si multiplum av hverandre av et inverterbart element - slik at alle elementene i en klasse har den samme normen i absolutt verdi), er sekvensen ( cl (α j )) periodisk fra en viss rang. Denne eiendommen er den umiddelbare konsekvensen av tre proposisjoner:
Disse egenskapene viser bare periodisiteten fra en viss rang. Følgende avsnitt viser at denne rangeringen er 0.
Det at sekvensen er periodisk, indikerer ikke a priori at den når et normpunkt som er lik 1 i absolutt verdi. Dette er imidlertid fremdeles tilfelle:
La B være mengden av elementene a + b √ n av A som a og b er primære for hverandre, og ψ være funksjonen fra B til B definert av: til et element α av B forbinder vi et element β av form m + √ n med m naturlig heltall slik at βα er et multiplum av normen for α, av minimal norm (vi så ovenfor at det kunne være to: vi kan for eksempel velge systematisk i dette tilfellet den som tilsvarer den minste av de to verdiene til m ), så setter vi ψ (α) = αβ / | N (α) |. Lemmaet og forrige avsnitt viser at kartet ψ er godt definert og det
Denne funksjonen har en symmetri med hensyn til funksjonen φ:
Mer presist: ψ (φ (γ)) = ε 1 ε 2 φ (α), hvor ε 1 (resp. Ε 2 ) betegner tegnet på normen for α (resp. Γ).
Faktisk, hvis α har for bilde av ψ verdien γ, eksisterer det et unikt element β av formen m + √ n med m naturlig heltall slik at
Elementet β er på formen m + √ n med m naturlig heltall slik at βφ (γ) er et multiplum av den standard φ (γ) fordi φ (α) hører til A . La β 'være et element som tilfredsstiller disse egenskapene, og med en norm som er mindre enn β, viser likheten γ = αβ' / N (β ') at β' har en norm som er større enn β . Vi utleder at normene for β og β 'er like, og dets minimale karakter er verifisert. Likhet (1) viser da at ε 1 ε 2 φ (α) faktisk er bildet av φ (γ) av ψ. Proposisjonen er demonstrert.
Vi utlede at funksjonen ψ er en Bijeksjon B i B .
I følge forrige § “Syklisk karakter” eksisterer det to indekser 0 ≤ k <k + j slik at cl (α k + j ) = cl (α k ). Ved bijektiviteten til ψ vist ovenfor , trekker vi frem at cl (α j ) = cl (α 0 ), det vil si at N (α j ) = ± 1. Dessuten, som b j > 0, er løsningen som er funnet ikke triviell .
Fra cl (ψ (α j –1 )) = cl (φ (α 0 )) trekker vi ved induksjon, av egenskapen til ψ vist ovenfor , at cl (ψ (α j –1– k )) = cl (φ (α k )).
Chakravala- metoden er veldig nær den for den fortsatte fraksjonen. Her er målet å nærme seg roten til n ved et optimalt uttrykk for følgende natur:
La n være et naturlig ikke-kvadratisk tall. Vi definerer ved induksjon to sekvenser, ( f j ) j ≥0 med verdier i ℤ og (θ j ) j ≥ - 1 i ℚ ( √ n ) ved: θ –1 = √ n og for alle j ≥ –1 , f j +1 er heltallet (eller det minste av de to heltallene) som | N (θ j - f j +1 ) | er minimal og θ j +1 = 1 / (θ j - f j +1 ). Det at √ n er irrasjonell viser at θ j alltid er irrasjonell; sekvensene ( f j ) og (θ j ) er således godt definert.
Denne definisjonen skiller seg fra den tradisjonelle fortsatte fraksjonen fordi her er θ j og f j ikke nødvendigvis positive.
La ( h j ) og ( k j ) være sekvensene til tellerne og nevnerne for reduksjonene .
Hvis (α j ) og (β j ) betegner sekvensene som er definert tidligere , er følgende likheter tilfredsstilt (med, konvensjonelt, m –1 = 0):
Dermed gjør den sykliske karakteren og palindromegenskapene til denne fortsatte fraksjonen det mulig å demonstrere de som er i chakravala- metoden , og omvendt. Hvis den rekursive algoritmen pålegger βj å være av systematisk negativ norm, forblir bevisene for artikkelen gyldige og de tilhørende fortsatte brøkene tilsvarer den vanlige definisjonen.
DemonstrasjonDen kontinuerlige fraksjonstilnærmingen gir en berikelse av den forrige algoritmiske metoden for Pell-Fermat-ligningen eller bestemmelsen av den fortsatte fraksjonen. La oss illustrere disse metodene ved hjelp av eksemplet n = 313 og vise hvordan Brouncker faktisk kunne løse denne utfordringen om en time eller to. Per definisjon er m –1 = 0 og N (α 0 ) = 1, for enhver indeks j ≥ 0:
Vi finner altså m 0 = 18, N (β 0 ) = 11, N (α 1 ) = 11, m 1 = 15, N (β 1 ) = –88, N (α 2 ) = –8, etc.
Vi trekker ut f j med formelen i forrige avsnitt: f 0 = m 0 = 18, f 1 = - (18 + 15) / 11 = –3, etc.
Denne tilnærmingen unngår store tall, bortsett fra h j –1 og k j –1 , der a j og b j er de absolutte verdiene. De beregnes for j ≥ 1 av induksjonsformelen fra f j .
Videre, hvis normene for to påfølgende α er like eller motsatte, følger det umiddelbart av algoritmen at β og normene for α danner et palindrom. Mer presist: hvis N (α r +1 ) = ε N (α r ) med ε = ± 1, ved induksjon på k , β r + k = β r - k og N (α r + k +1 ) = ε N (α r - k ). Følgelig er α 2 r +1 da inverterbar (av norm ε) og - i henhold til uttrykket for sekvensen til α som en funksjon av den for β - lik ε r α r +1 / φ (α r ) = ε r α r α r +1 / N (α r ).
Vi konstruerer således følgende tabell, der vi ser at den nevnte situasjonen oppstår for r = 6 og ε = –1:
|
Normsekvensen til α er derfor 1, 11, –8, 3, 16, –9, 13, –13, 9, –16, –3, 8, –11, –1, som gir et element av norm - 1:
(Dette tallet er også lik α 3 2 α 5 / 9.) Det gjenstår nå bare å kvadratere for å oppnå ønsket løsning:
Chakravala- metoden gjør det dermed mulig å løse denne typen beregninger for hånd. Den samme tilnærmingen, uten beregning av kolonnene h j –1 og k j –1 , ubrukelig for dette målet, tillater å bestemme en fortsatt brøkdel av √ 313 . Å finne løsningen slik at sekvensen ( f k ) bare inneholder positive verdier antar å begrense valget til m k mindre enn eller lik 17. Vi vil da finne den fortsatte brøkdelen av denne kvadratiske irrasjonelle : [17, 1, 2, 4, 11, 1, 1, 3, 2, 2, 3, 1, 1, 11, 4, 2, 1, 34 ].
(en) John J. O'Connor og Edmund F. Robertson , “Indian Mathematics: Redressing the balance, 8 VI. Pells ligning ” , i MacTutor History of Mathematics archive , University of St. Andrews ( les online ).