V matematiky a konkrétněji v aritmetické je chakravala metoda je algoritmus pro řešení Pell-Fermat rovnice . Tato rovnice je příkladem diofantické rovnice , to znamená s celočíselnými koeficienty a jejíž celočíselná řešení jsou hledána. Přesněji řečeno, je to rovnice
kde n je přirozené jiné než čtvercové číslo .
Tato metoda byla vyvinuta v Indii a její kořeny lze vysledovat na VI -tého století s Aryabhata , následovaný Brahmagupta . Iniciována Jayadeva (en) , byl dále vyvinut Bhaskara II .
Selenius to hodnotí takto: „Metoda představuje nejlepší aproximační algoritmus minimální délky, který díky několika vlastnostem minimalizace automaticky vytváří […], při nižších nákladech […] a vyhýbá se velkému počtu, nejmenším řešením rovnice […] Metoda chakravāla předcházela evropským metodám o více než tisíc let. Ale žádný evropský výkon v celé oblasti algebry , mnohem později po Bhāskarovi […], neodpovídal úžasné složitosti a vynalézavosti chakravāly . "
Musí ovšem očekávat, že XVII tého století, že Evropané, kteří ignorovali práci indických matematiků objevují algoritmy - méně efektivní - řešící stejný problém.
Forma Pell-Fermatovy rovnice je vyjádřena následovně:
kde n je přirozené jiné než čtvercové číslo. Rovnice je Diophantine, což znamená, že hledané páry ( x , y ) jsou páry celých čísel. Všechna řešení jsou vyjádřena z dvojice řešení vytvořené ze dvou minimálních celých čísel v absolutní hodnotě v sadě řešení. Metoda chakravala umožňuje získat pár této povahy.
Následující rovnost je příkladem řešení; Indové se vědělo o VII tého století:
Tyto indické matematiky zaujala velmi brzké aritmetiku. Aryabhata , matematik ze VI -tého století , stanovuje základy. Vyvinul systém čísel, který ukazuje, že pravděpodobně věděl o poziční notaci i existenci nuly . Pracuje na diofantických rovnicích a řeší identitu Bézouta , vyvíjí algoritmus ekvivalentní Euklidovu, kterému říká ku ṭ ṭ aka (कूटटक) a který znamená postřikovač, protože rozděluje čísla na menší celá čísla. Pracuje také na pokračujících zlomcích .
Jako první do hloubky analyzuje tuto otázku indický matematik Brahmagupta ( 598 - 668 ) . Chápe, jak ze dvou řešení je možné postavit nové. Zopakováním tak získá tolik odlišných řešení, kolik si přeje. Tuto metodu indičtí matematici nazývají samasa . Brahmagupta z toho odvozuje tři algoritmy. První mu umožňuje najít řešení, pokud má dvojici celých čísel ( x , y ), jejichž obraz podle rovnice je –1. Najde druhý zabývající se případem, kdy je obraz v absolutní hodnotě 2 . Najde třetí, který poskytne stejný výsledek, pokud je obraz roven ± 4. Zrodila se metoda návrhu. Začíná to pokusem a omylem, dokud nenajde pár, který má pro obrázek 1, 2 nebo 4 absolutní hodnotu, pokračuje jedním ze tří algoritmů. Brahmagupta ji používá v roce 628 ve své knize Brahmasphuta siddhanta k řešení následující rovnice:
Tento přístup není dostatečný pro řešení složitých případů, může být obtížné najít metodou pokusu a omylu pár, který dává jednu ze šesti hodnot, které umožňují závěr. V XII -tého století , Bhaskara II navazuje na předchozí smluv a navrhuje konečnou podobu metody chakravala . Odpovídá přidání cyklického algoritmu, to znamená poskytnutí periodické posloupnosti párů, které nutně obsahují řešení. Cyklický algoritmus je ekvivalentní algoritmu pokračujících zlomků . Metoda chakravala končí výpočty Brahmagupty, pokud dojde k jedné z hodnot –1, ± 2 a ± 4. Bhāskara II jej používá v roce 1150 ve svém pojednání Bijaganita k nalezení minimálního řešení následující rovnice, kterou již Brahmagupta našel:
Nalezený pár řešení je:
Je nepravděpodobné, že Bhaskara II prokázala, že algoritmus vždy nabízí řešení, to znamená, že pro každou hodnotu n , protože demonstrace, dlouhý a technický vyžaduje propracovanosti daleko přesahující možnosti matematiky XII th století. Nové příklady pojednávají později indičtí matematici. V XIV th století matematik jmenoval Narayana studovat, pokud n je rovno 103 ve svých připomínkách ke knize Bijaganita z Bhaskara II.
V únoru 1657 (po další slavnější výzvě z 3. ledna téhož roku) Pierre de Fermat vyzývá Bernarda Frénicle de Bessyho a skrze něj i všechny evropské matematiky, aby vyřešil (mimo jiné) problém pro n = 61. Anglická reakce je rychlá: William Brouncker najde algoritmus. Frénicle de Bessy poté navrhuje tabulku obsahující všechna řešení pro hodnoty n menší než 150, která budou nakonec ztracena, poté John Wallis znovu objeví výsledky Brahmagupty a důsledně je předvede. Frénicle de Bessy vyzve Brounckera s hodnotou n = 313; dostává v reakci nejen řešení, ale i potvrzení, že jeho autor nepotřeboval k nalezení více než „hodinu či dvě“.
Dvě základní teoretické otázky, jmenovitě, zda pro nějaké jiné než čtvercové přirozené číslo n existuje řešení, a pokud nalezené řešení skutečně generuje všechny ostatní, jsou nakonec vyřešeny Lagrangeem v roce 1767 algoritmem méně účinným než ten - pak ignorovány Evropany - kvůli Bhāskarovi, jehož oprava je však snazší prokázat. V roce 1930 AA Krishnaswami Ayyangar (in) tvrdí, že je první, kdo dokázal, že chakravala .
Zde navržené metody využívají sílu současného formalismu. Pokud je matematický obsah analogický s Brahmaguptou, výstavní techniky i demonstrace neodráží myšlenku indického matematika. Následující notace se používají ve zbytku článku. Zvažte následující diofantickou rovnici, kde n je jiné než čtvercové přirozené číslo:
Nechť A je kruh čísel ve tvaru a + √ n b , kde a a b označují dvě celá čísla, N aplikace, která k prvku A spojuje jeho „ normu “ a φ aplikace, která k prvku A spojuje jeho " konjugát ":
Tyto funkce N odpovídá normě z A ve smyslu algebraické teorie čísel . Prvek + √ n b z A se nazývá kořen rovnice (1), v případě, a pouze tehdy, když jeho normou je 1, tj. V případě, ( , b ) je roztok (1).
Funkce φ má také užitečné vlastnosti. Je to automorphism of A :
Konjugace φ je involutivní, to znamená, že složená dvakrát za sebou, je stejná jako identita, nebo její vzájemná bijekce se rovná sobě:
Nakonec se produkt dvou konjugovaných prvků rovná jejich společné normě:
Pokud napíšeme α = a + √ n b , je to odůvodněno následujícím výpočtem:
První použitá vlastnost je:
Nechť α a β jsou dva prvky A , pak:
Pokud α = a 1 + √ n a 2 a β = b 1 + √ n b 2 , zapíše se tato rovnost:
Tato rovnost, známá jako identita Brahmagupty , byla Indy nazývána Samasa . Abychom byli přesvědčeni o jeho přesnosti, stačí vyjádřit N jako funkci automorfismu φ:
Zvláštní případ odpovídá tomu, kde β je celé číslo k , má rovnost následující podobu:
Nechť α je prvek A a k celé číslo, pak:
Ve skutečnosti N (α) = N (φ (α)) = αφ (α), a pokud α je řešením (1), pak α k také pro všechna přirozená čísla k (protože norma produktu je stejná jako produkt norem), ale mocniny reálného jiného než 0, 1 a –1 jsou odlišné.
Pochopení toho, jak Brahmagupta řeší rovnici (1), závisí na třech tvrzeních:
Nechť α je prvek A.
Pojďme s touto metodou zacházet s následujícím příkladem Brahmagupty:
Nechť α = m + √ 83 , celé číslo m je zvoleno tak, aby norma N (α) = m 2 - 83 byla nejmenší možná v absolutní hodnotě: m = 9, α = 9 + √ 83 , N (α) = –2. A předchozí návrh ukazuje, že a 2 /2 je řešení. Účinně:
a
Fermat výzvaFermatova výzva je vyřešena stejným způsobem:
Brahmagupta to dělá následujícím způsobem: všimne si, že pokud α = 39 + 5 √ 61, pak N (α) se rovná –4. Brahmaguptův formalismus zjevně nemá nic společného s zde použitým, i když jsou výpočty stejné. Počítá alfa 2 /2:
Pak vypočítá α 3 /8 a jeho standardní:
Řešení je tedy α 6 /64, je:
Metoda je pro takový starý algoritmus pozoruhodně ekonomická.
Potíž s Brahmaguptovou metodou spočívá ve skutečnosti, že není vždy snadné najít číslo α A, jehož norma se rovná ± 1, ± 2 nebo ± 4. Příspěvek Bhāskary II popsaný v Siddhanta Siroman spočívá v obohacení metody o algoritmus, který neomylně končí poskytnutím „ kvaziřešení “ této povahy.
Bhāskara II vytváří indukcí posloupnost prvků α j = a j + b j √ n z A následovně. Prvním prvkem posloupnosti je α 0 = 1, normy k 0 = 1. Předpokládejme posloupnost definovanou v pořadí j . Zkonstruujeme prvek β j = m j + √ n . Přirozené celé číslo m j je takové, že a j + m j b j je násobkem normy k j z α j - jinými slovy takové, že b j m j je shodné s - a j modulo k j - a m j minimalizuje absolutní hodnota normy m j 2 - n β j . Prvek α j + 1 je pak definován symbolem
nebo
se nad ± odpovídající znamení N (α j ) - tu výhodu, že užívání tohoto označení v úvahu, je, že tak, j a b j jsou vždy kladné.
Později uvidíme , že podmínka „ a j + m j b j násobek k j “ odpovídá „ m j shodnému s - m j –1 modulo k j “, což zjednodušuje algoritmus.
Zvolme znovu n rovné 61. Hodnota m 0 se rovná 8, abychom minimalizovali | N (β 0 ) |. Ve skutečnosti je √ 61 mezi 7 a 8 a 8 2 - 61 = 3 <61 - 7 2 . Celé číslo m 1 je poté vybráno z těch shodných, modulo N (α 1 ) = N (8 + √ 61 ) = 8 2 - 61 = 3, při - m 0 = –8 tedy při 1. Ze dvou po sobě následujících členů 7 a 10 této aritmetické posloupnosti, která obklopuje √ 61 , ta, která minimalizuje | N (β 1 ) | je m 1 = 7, což dává:
Zbytek metody je metoda Brahmagupta . Metoda chakravala nyní umožňuje vyřešit Fermatovu výzvu bez pokusů a omylů as minimem výpočtu.
Příklad narayanaTento druhý příklad je rovněž převzat ze Siromana Siddhanty z Bhāskary II, komentovaného Narayanou. Pro n = 103, m 0 = 10. Celé číslo m 1 se poté zvolí shodně s –10 modulo N (α 1 ) = N (10 + √ 103 ) = 10 2 - 103 = –3. Protože 8 < √ 103 <11 a 11 2 - 103 = 18 <103 - 8 2 , dostaneme m 1 = 11 a
Poté zvolíme m 2 shodné s –11 modulo 6. Protože 7 < √ 103 <13 a 103 - 7 2 = 54 <13 2 - 103, získáme m 2 = 7 - všimněte si při této příležitosti „minimalizovat | m 2 - n | „Ne vždy se shoduje s“ minimalizovat | m - √ n | "- pak
Potom musí být modulo 9, m 3 shodné s –7. Chcete-li minimalizovat | N (β 3 ) |, musíme zvolit m 3 rovné 11. Získáváme
Brahmaguptův výpočet nám umožňuje dospět k závěru: hledaná hodnota je
NeunikátnostNásledující příklad ukazuje, že počet α j +1 definovaný z α j není vždy jedinečný: pro n = 58 se α 1 rovná 8 + √ 58 , normy 6, pak pro m 1 shodné s –2 modulo 6, minimálně | m 1 2 - 58 | je 42, dosaženo pro dvě hodnoty 4 a 10 m 1 . Dvě odpovídající hodnoty pro α 2 jsou 15 + 2 √ 58 , s normou –7, a 23 + 3 √ 58 , s normou 7. Pro první pak nalezneme m 2 = 10 a pro druhou m 2 = 4 tedy pro oba, α 3 = 38 + 5 √ 58 , s normou –6, poté m 3 = 8 a α 4 = 99 + 13 √ 58 , s normou –1. Bifurkace byla proto pouze dočasná a obě sady poskytují stejné řešení.
Lema dokazuje existenci posloupnosti používané Bhāskarou II, protože věděla, že pokud k a b jsou navzájem prvočísla, pak pro každé celé číslo a existují celá čísla m, pro která je + bm dělitelné k . Skutečně, řešením identity Bézouta - kterou indiáni již věděli, jak dělat s Euklidovým algoritmem - najdeme celá čísla v, pro která 1 - bv je násobkem k , a stačí nastavit m = - av .
Nechť a , b jsou coprime a m , n libovolná dvě celá čísla. Nastavili jsme k = a 2 - nb 2 , c = am + bn a d = a + bm .
Pokud d je násobkem k, pak i c a dvě celá čísla c / k a d / k jsou coprime.
Toto lemma je okamžité, když si všimneme, že ad - bc = k a b je prvočíslo s k . Aplikováno - s poznámkami § „Princip metody“ - na a = a j a b = b j , ukazuje, že v každé fázi konstrukce posloupnosti (α j ), pokud je m j zvoleno podle metoda naznačila, že α j β j je násobkem N (α j ), α j +1 je prvek A a a j +1 a b j +1 jsou coprime, což umožňuje iteraci konstrukce.
Dále si můžeme všimnout, že omezení (při volbě m j ) „ a j + b j m dělitelné N (α j )“ je ekvivalentní „ m kongruentní s - m j –1 modulo N (α j )“. Ve skutečnosti je b j prvočíslo s N (α j ) a a j + b j (- m j –1 ) je dělitelné N (α j ), protože φ (α j ) β j –1 = ± N (α j ) φ (α j –1 ).
Jakmile ukážeme, že posloupnost (α j ) je dobře definovaná, prostudujme si její chování. Je to v určitém smyslu „cyklické“. Přesněji řečeno, upozorněním cl (α) třída ekvivalence α pro vztah „být přidružen “ (to znamená, že je jeden z ostatních invertovatelným prvkem - takže všechny prvky třídy mají stejnou normu v absolutní hodnota), posloupnost ( cl (α j )) je periodická od určité hodnosti. Tato vlastnost je bezprostředním důsledkem tří tvrzení:
Tyto vlastnosti prokazují periodicitu pouze od určité pozice. Následující odstavec ukazuje že tato pozice je 0.
Skutečnost, že posloupnost je periodická, neznamená a priori, že dosáhne bodu normy rovného 1 v absolutní hodnotě. Stále to však platí:
Nechť B je soubor prvků, a + b √ n z A , pro kterou a b jsou primární k sobě, a ¥ je funkce z B do B definovanou: na prvek alfa části B spojujeme element beta formy m + √ n s přirozeným celým číslem m takovým, že βα je násobkem normy α, minimální normy ( výše jsme viděli , že mohou existovat dvě: můžeme si například v tomto případě zvolit systematicky to, které odpovídá menšímu z dvě hodnoty m ), pak nastavíme ψ (α) = αβ / | N (α) |. Lemma a předchozí odstavec ukazují, že mapa ψ je dobře definovaná a to
Tato funkce má symetrii vzhledem k funkci φ:
Přesněji: ψ (φ (γ)) = ε 1 ε 2 φ (α), kde ε 1 (resp. Ε 2 ) označuje znaménko normy α (resp. Γ).
Ve skutečnosti, pokud α má pro obraz o ψ hodnotu γ, existuje jedinečný prvek β ve tvaru m + √ n s m přirozeným celým číslem takový, že
Prvek β má tvar m + √ n s m celé přirozené číslo takové, že βφ (γ) je násobek standardního cp (y), protože φ (α) patří do A . Nechť β 'je prvek splňující tyto vlastnosti as normou menší než β ukazuje rovnost γ = αβ' / N (β '), že β' má normu větší než β . Dedukujeme, že normy β a β 'jsou stejné a je ověřen jejich minimální charakter. Rovnost (1) pak ukazuje, že ε 1 ε 2 φ (α) je skutečně obrazem φ (γ) o ψ. Návrh je demonstrován.
Odvodíme, že funkce ψ je bijection B na B .
Podle předchozího odstavce „Cyklický charakter“ existují dva indexy 0 ≤ k <k + j takové, že cl (α k + j ) = cl (α k ). V bijectivity o ln je uvedeno výše , odvodíme, že cl (α j ) = cl (α 0 ), to znamená, že N (α j ) = ± 1. Navíc, stejně jako b j > 0, nalezené řešení není triviální .
Z cl (ψ (α j –1 )) = cl (φ (α 0 )) indukcí pomocí vlastnosti ψ prokázané výše , že cl (ψ (α j –1– k )) = cl (φ (α k )).
Chakravala metoda je velmi blízká metodě pokračující frakce. Zde je cílem přiblížit se ke kořenu n optimálním vyjádřením následující povahy:
Nechť n je přirozené jiné než čtvercové číslo. Definujeme indukcí dvě posloupnosti, ( f j ) j ≥0 s hodnotami v ℤ a (θ j ) j ≥ - 1 v ℚ ( √ n ) podle: θ –1 = √ n a pro všechna j ≥ –1 , f j +1 je celé číslo (nebo menší ze dvou celých čísel), pro které | N (θ j - f j +1 ) | je minimální a θ j +1 = 1 / (θ j - f j +1 ). Skutečnost, že √ n je iracionální, ukazuje, že θ j je vždy iracionální; sekvence ( f j ) a (θ j ) jsou tak dobře definované.
Tato definice se liší od tradičního řetězový zlomek, protože tady je θ j a f j nejsou nutně pozitivní.
Nechť ( h j ) a ( k j ) jsou posloupnosti čitatelů a jmenovatelů redukcí .
Pokud (α j ) a (β j ) označují dříve definované posloupnosti , jsou splněny následující rovnosti (s konvencí m –1 = 0):
Cyklický charakter a vlastnost palindromu této pokračující frakce tedy umožňují demonstrovat vlastnosti metody chakravala a naopak. V případě, že rekurzivní algoritmus ukládá p j být systematicky negativní normu, pak důkazy výrobku zůstávají v platnosti a příslušné řetězové zlomky odpovídají obvyklé definice.
DemonstracePřístup kontinuální frakce nabízí obohacení předchozí algoritmické metody pro Pell-Fermatovu rovnici nebo stanovení pokračující frakce. Pojďme si ilustrovat tyto metody na příkladu n = 313 a ukážeme, jak by Brouncker mohl tuto výzvu vyřešit za hodinu nebo dvě. Podle definice m –1 = 0 a N (α 0 ) = 1 pro libovolný index j ≥ 0:
Zjistíme tedy m 0 = 18, N (β 0 ) = 11, N (α 1 ) = 11, m 1 = 15, N (β 1 ) = –88, N (α 2 ) = –8 atd.
My odvodit f j vzorcem předchozího odstavce: f 0 = m 0 = 18, f 1 = - (18 + 15) / 11 = -3, atd.
Tento přístup se vyhýbá velkým číslům, s výjimkou h j –1 a k j –1 , kde a j a b j jsou absolutní hodnoty. Počítají se pro j ≥ 1 indukčním vzorcem z f j .
Navíc, pokud jsou normy dvou po sobě následujících α stejné nebo opačné, z algoritmu okamžitě vyplývá, že β a normy α tvoří palindrom. Přesněji: pokud N (α r +1 ) = ε N (α r ) s ε = ± 1, pak indukcí na k , β r + k = β r - k a N (α r + k +1 ) = ε N (α r - k ). Následně je α 2 r +1 invertibilní (normy ε) a - podle vyjádření posloupnosti α podle sekvence β - rovné ε r α r +1 / φ (α r ) = ε r α r a r +1 / N (a r ).
Zkonstruujeme tedy následující tabulku, kde vidíme, že uvedená situace nastává pro r = 6 a ε = –1:
|
Sekvence norem α je tedy 1, 11, –8, 3, 16, –9, 13, –13, 9, –16, –3, 8, –11, –1, což poskytuje prvek normy - 1:
(Toto číslo je také rovná jako α 3 2 α 5 A / 9.) Nyní zbývá pouze náměstí pro získání požadované řešení:
Metoda chakravala tak umožňuje řešit tento typ výpočtu ručně. Stejný přístup, bez výpočtu sloupce h j -1 a K j -1 , neužitečný pro tento cíl, umožňuje určit na pokračující zlomek √ 313 . Hledání řešení tak, že sekvence ( f k ) obsahuje pouze kladné hodnoty předpokládá omezující volbu na m k menší než nebo rovnající se 17. bychom pak najít na pokračující zlomek této kvadratický nerozumný : [17, 1, 2, 4, 11, 1, 1, 3, 2, 2, 3, 1, 1, 11, 4, 2, 1, 34 ].
(en) John J. O'Connor a Edmund F. Robertson , „Indian Mathematics: Redressing the balance, 8 VI. Pellova rovnice “ , v archivu MacTutor History of Mathematics , University of St Andrews ( číst online ).