Kontinuální zlomek kvadratické iracionální
V matematiky , a přesněji v aritmetické se pokračuje frakce z a kvadratických iracionálních odpovídá zastoupení tohoto čísla ve formě
na0+1na1+1na2+1na3+⋯sna0∈Za∀i>0nai∈NE{\ 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 {a}} \ quad \ forall i> 0 \ quad a_ {i} \ in \ mathbb {N}}.
Pokud je iracionální číslo představované kvadraticky, tj. Jedná-li se o řešení kvadratické rovnice s racionálními koeficienty , pak je posloupnost celých čísel ( a n ) periodická od určité pozice.
Zájem o studium pokračujícího zlomku kvadratické iracionality se neomezuje pouze na toto. Jednoduchost algoritmu pro určování koeficientů zlomku z něj na dlouhou dobu udělala metodu extrakce druhou odmocninou . Znát pokračující zlomek také mimo jiné umožňuje vyřešit slavnou diofantickou rovnici zvanou Pell-Fermat : x 2 - ny 2 = ± 1.
Preambule
Úvod k příkladu
Můžeme vypočítat pokračující zlomek kvadratické iracionální pomocí pozoruhodné identity ( a + b ) ( a - b ) = a 2 - b 2 v každém kroku, jako v následujícím příkladu.
13=3+(-3+13)=3+(13-3)(13+3)13+3=3+43+13=3+113+34{\ displaystyle {\ 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}}}}
a
na0=3, X1=13+34{\ displaystyle a_ {0} = 3, ~ x_ {1} = {\ frac {{\ sqrt {13}} + 3} {4}}}.
Použitím stejného algoritmu na x 1 :
13+34=1+13-14=1+113+13proto13=3+11+113+13{\ displaystyle {\ frac {{\ sqrt {13}} + 3} {4}} = 1 + {\ frac {{\ sqrt {13}} - 1} {4}} = 1 + {\ frac {1 } {\ frac {{\ sqrt {13}} + 1} {3}}} \ quad {\ text {proto}} \ quad {\ sqrt {13}} = 3 + {\ cfrac {1} {1+ {\ cfrac {1} {\ frac {{\ sqrt {13}} + 1} {3}}}}}}
a tak:
na1=1, X2=13+13{\ displaystyle a_ {1} = 1, ~ x_ {2} = {\ frac {{\ sqrt {13}} + 1} {3}}}.
Počítáme stejným způsobem :
X3{\ displaystyle x_ {3}}
13+13=1+113+23proto13=3+11+11+113+23ana2=1, X3=13+23.{\ displaystyle {\ frac {{\ sqrt {13}} + 1} {3}} = 1 + {\ frac {1} {\ frac {{\ sqrt {13}} + 2} {3}}} \ quad {\ text {proto}} \ quad {\ sqrt {13}} = 3 + {\ cfrac {1} {1 + {\ cfrac {1} {1 + {\ frac {1} {\ frac {{\ sqrt {13}} + 2} {3}}}}}}} \ quad {\ text {a}} \ quad a_ {2} = 1, ~ x_ {3} = {\ frac {{\ sqrt {13 }} + 2} {3}}.}
jeden pokračuje takto a jeden počítá následující podmínky vývoje, dokud :
X6{\ displaystyle x_ {6}}
X3=13+23=1+11+16+113+34{\ displaystyle x_ {3} = {\ frac {{\ sqrt {13}} + 2} {3}} = 1 + {\ frac {1} {1 + {\ frac {1} {6 + {\ frac {1} {\ frac {{\ sqrt {13}} + 3} {4}}}}}}}} Konečně :
na3=1, na4=1, na5=6, X6=13+34.{\ displaystyle a_ {3} = 1, ~ a_ {4} = 1, ~ a_ {5} = 6, ~ x_ {6} = {\ frac {{\ sqrt {13}} + 3} {4}} .}
Slovník a zápisy zde použity, jsou ty, které jsou definovány v článku „ Kontinuální frakci “ rozumí, že částečný podíl n je celá část z kompletního kvocientu x n , jeho desetinná část je 1 / x n + 1 . Snížený index n označuje komolého kontinuální frakce obsahující n frakce tyče a konstruovány s použitím n + 1 koeficientů; označuje se h n / k n . Pokud nahradíme si n -1 o a n -1 + 1 / x n ve výrazu z snížení indexu n - 1, dostaneme přesně počáteční číslo. Celý kvocient x 0 je počáteční hodnota.
Ve zvoleném příkladu
X0=13=3+11+11+11+11+16+⋯Eth0k0=31, h1k1=41, h2k2=72, h3k3=113, h4k4=185, h5k5=11933{\ displaystyle x_ {0} = {\ sqrt {13}} = 3 + {\ cfrac {1} {1 + {\ cfrac {1} {1 + {\ cfrac {1} {1 + {\ frac {1 } {1 + {\ frac {1} {6+ \ cdots}}}}}}}}} \ quad {\ rm {et}} \ quad {\ frac {h_ {0}} {k_ {0} }} = {\ frac {3} {1}}, ~ {\ frac {h_ {1}} {k_ {1}}} = {\ frac {4} {1}}, ~ {\ frac {h_ { 2}} {k_ {2}}} = {\ frac {7} {2}}, ~ {\ frac {h_ {3}} {k_ {3}}} = {\ frac {11} {3}} , ~ {\ frac {h_ {4}} {k_ {4}}} = {\ frac {18} {5}}, ~ {\ frac {h_ {5}} {k_ {5}}} = {\ frac {119} {33}}}.
Vzhledem k tomu, že tato nota je trochu těžká, přednostně používáme následující, se stejným významem:
13=[3,1,1,1,1,6⋯]{\ displaystyle {\ sqrt {13}} = [3,1,1,1,1,6 \ cdots]}.
Nakonec je úplný kvocient roven , což umožňuje dospět k závěru, že posloupnost koeficientů se opakuje od hodnosti 1. Mluvíme o „periodické posloupnosti od určité hodnosti“ a používáme notaci:
X6{\ displaystyle x_ {6}}X1{\ displaystyle x_ {1}}
13=[3,1,1,1,1,6¯]{\ displaystyle {\ sqrt {13}} = [3, {\ overline {1,1,1,1,6}}]},
bar znamenat nekonečné opakování konečných řady z celých čísel , jichž se týká.
Prvky příběhu
Od VI -tého století , Aryabhata ( 476 - na 550 ) , matematik indické použití pokračovalo frakcí pro racionální okolí odmocnin čísel. Pokud Brahmagupta ( 598 - 668 ) , další indický matematik, se zajímá o rovnici Pella a využívá pozoruhodnou identity Chcete-li, to nebylo až do XII th století a Bhaskara II vidět podobný přístup ke že pokračující frakce aplikována na to rovnice. Jeho algoritmus je metoda chakravala , odpovídá článku, s tím rozdílem, že 0 není vždy menší než číslo, které má být osloven. Tento rozdíl se přenáší do všech koeficientů a n , které se mohou stát zápornými. Tato specifičnost trochu zrychluje hledání řešení.
Teprve později se o takový přístup začala zajímat Evropa. Teprve v XVI -tého století, který Rafael Bombelli make využití předchůdce řetězovými zlomky k výpočtu aproximací na druhé odmocnině z 13. Pietro Antonio Cataldi rozumí rozsah způsobu Bombelli a platí pro všechny odmocniny, v malé brožurce o pro toto téma zvolí příklad hodnoty 18. Podobné výsledky najdeme s Albertem Girardem v roce 1625, poté v roce 1634, abychom se přiblížili √ 2 a √ 10 .
Po výzvě, kterou zahájil Pierre de Fermat v roce 1657, William Brouncker empiricky najde vztahy, které spojují pokračující zlomek kvadratické iracionality s Pell-Fermatovou rovnicí. Je pravděpodobné, že Bernard Frénicle de Bessy také znal tuto metodu řešení Pell-Fermatovy rovnice, pro kterou našel všechna řešení pro n méně než 150, ale tato práce byla ztracena; vyzve Brounckera, aby našel řešení rovnice pro n = 313. Ten ve své odpovědi naznačuje, že hledání „mu netrvalo„ déle než hodinu nebo dvě “. Tato odpověď je následující:
X=32188120829134849ay=1819380158564160{\ Displaystyle x = 32 \, 188 \, 120 \, 829 \, 134 \, 849 \ quad {\ text {a}} \ quad y = 1 \, 819 \, 380 \, 158 \, 564 \, 160 \;}
Tato informace pochází z intenzivního epištolského vztahu mezi různými aktéry, který nakonec publikoval John Wallis v roce 1658.
Příští století je to demonstrace. Leonhard Euler se ujal práce Brounckera a Wallise a důsledně předvádí všechny poněkud elementární aspekty teorie; také ukazuje, že pokud je pokračující zlomkové zastoupení čísla periodické, od určité pozice, pak je toto číslo kvadraticky iracionální. Stále si musíme počkat na práci Josepha-Louise Lagrangeova na předvedení vzájemnosti a také na důvody platnosti metody Bhāskara II nebo Brounckera. Vlastnosti pokračující frakce kvadratické iracionální jsou poté v podstatě objasněny; Zbývá jen pochopit, v jakém případě není pokračující zlomek pouze periodický z určité pozice, ale čistě periodický, což Évariste Galois dosáhl v roce 1828.
Doba
Jakýkoli iracionální, jehož kontinuální expanze zlomků je periodická, je kvadratický iracionální ( a fortiori , také jeho plné kvocienty).
Příklad
Iracionální se rovná se .
X=[0,1,1,2,1,2,1,2,...]=[0,1,1,2¯]{\ displaystyle x = [0,1,1,2,1,2,1,2, \ dots] = [0,1, {\ overline {1,2}}]}0+11+1y=yy+1{\ displaystyle 0 + {\ frac {1} {1 + {\ frac {1} {y}}}} = {\ frac {y} {y + 1}}}y=[1,2¯]=1+12+1y{\ displaystyle y = [{\ overline {1,2}}] = 1 + {\ frac {1} {2 + {\ frac {1} {y}}}}}
Nahrazením by v této rovnici pak zjednodušením ji najdeme .
y{\ displaystyle}X1-X{\ displaystyle {\ frac {x} {1-x}}}3X2-1=0{\ displaystyle 3x ^ {2} -1 = 0}
Tato implikace je jádrem zájmu pojmu pokračující zlomek pro kvadratické iracionály, protože (více než sto let po jeho objevení) Lagrangeovi se podařilo prokázat opak:
Lagrangeova věta - Iracionální je kvadratická právě tehdy, je -li její pokračující expanze zlomků periodická z určité pozice.
Lagrangeova dokonce ukázalo, že pro kvadratickou nerozumný formy ( P + √ D ) / Q , dílčí kvocienty se i se zvýší o 2 √ D a doba 2 D . Jemnější argumenty, založené na funkci dělitele , ukazují, že tato doba je velký O z √ D log ( D ) .
Čistě periodický vývoj
P -periodicity z rank r vývoje kvadratické neracionální x je psáno, se stejnou notaci jako v preambuli:
X=[na0,na1,⋯,nar-1,nar,nar+1,⋯nar+p-1,nar,nar+1⋯]=[na0,na1,⋯,nar-1,nar,nar+1,⋯nar+p-1¯]{\ 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}}}}}.
Některá čísla mají čistě periodický vývoj, to znamená od prvního koeficientu ( r = 0). To je například případ zlatého řezu φ. Vskutku,
φ=1+1φ=1+11+1φ=⋯aφ=[1,1,1,⋯]=[1¯]{\ 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}}]}.
Vyvstává otázka, v takovém případě je vývoj v pokračujícím zlomku čistě periodický. Číslo x je nutně kvadratické iracionální, proto jeho minimální polynom je stupně 2. Odpověď - prokázaná Galoisem (ještě jako student střední školy), ale již implicitní v předchozí práci Lagrangeovy - je vyjádřena podle konjugátu x c of x , což je další kořen jeho minimálního polynomu:
Galoisova věta - Pokud má x čistě periodické expanzi spojitých zlomků x = [ a 0 , a 1 ,…, a p –1 ], pak jeho konjugát x c splňuje –1 / x c = [ a p –1 ,…, a 1 , a 0 ]. Zejména x je redukovaný kvadratický iracionální, tj. X > 1 a –1 < x c <0.
Naopak pokračující rozšiřování zlomků jakékoli redukované kvadratické iracionality je čistě periodické.
Palindrom
Předchozí vlastnost poskytuje přesnější popis řetězového zlomku expanzi kořenové ne čtverec racionální :
Legendrova věta - Pokud d > 1 není racionální kvadratická část, má pokračující zlomek √ d tvar
d=[na0,na1,na2,na3⋯,na3,na2,na1,2na0¯]{\ displaystyle {\ sqrt {d}} = [a_ {0}, {\ overline {a_ {1}, a_ {2}, a_ {3} \ cdots, a_ {3}, a_ {2}, a_ { 1}, 2a_ {0}}}]}.
Naopak jakýkoli iracionální, jehož pokračující zlomek má tuto formu, je druhou odmocninou racionálního.
Palindrome který pak tvoří dobu zbaven svého posledního funkčního období 2 až 0 ° C má střední termín tehdy a jen tehdy, pokud toto období má ještě dlouhá. Například √ 13 = [3, 1, 1, 1, 1, 6 ] a √ 19 = [4, 2, 1, 3, 1, 2, 8 ].
Pell-Fermatova rovnice
Struktura řešení
Pokračující zlomek je jak teoretická, tak praktická technika pro řešení následující Pell-Fermatovy rovnice , pokud d je necelkové kladné celé číslo:
(1)X2-dy2=±1{\ displaystyle (1) \ quad x ^ {2} -dy ^ {2} = \ pm 1}.
Řešení je dvojice ( , b ) z celá čísla taková, že 2 - db 2 se rovná ± 1. Kromě triviálních řešení (1, 0) a (–1, 0) se všechna odvozují od těch, pro která jsou a a b přísně pozitivní, změnou znaménka a nebo b . Tři návrhy poté umožňují pochopit strukturu řešení:
- Jakákoli dvojice přísně kladných celých čísel řešení rovnice (1) se rovná dvojici čitatele a jmenovatele jedné z redukcí √ d .
- Sníží i -tý z √ d odpovídá řešení rovnice (1), a pouze v případě, i + 1 je dělitelné období √ d .
- Pokud je tato perioda p lichá, existují řešení pro hodnotu –1: odpovídají indexům i = qp - 1 pro q lichá, ta pro q sudá s hodnotou 1. Pokud je perioda p sudá, hodnota –1 není nikdy dosaženo.
Skupina jednotek
V algebraické teorii čísel je někdy důležité znát skupinovou strukturu jednotek kruhu algebraických celých čísel . K této situaci dochází zejména u kruhů kvadratických celých čísel. Pochopení této struktury je užitečné například k prokázání Fermatovy poslední věty pro n = 3 nebo 5 nebo k ustavení zákona o vzhledu prvočísel ve Fibonacciho posloupnosti (srov. „ Kruh celých čísel ℚ ( √ 5 ) “) .
Jsme vedeni hledat invertibilní prvky prstenu ring [ω], které mají tvar a + b ω, kde ω je kvadratické celé číslo a a a b jsou prvky ℤ. Ukážeme, že to odpovídá řešení jedné z následujících dvou diofantických rovnic, kde d je dokonalé celé číslo jiné než čtvercové a f celé číslo takové, že 4 f + 1 není dokonalý čtverec:
(1)X2-dy2=±1(2)X2+Xy-Fy2=±1{\ displaystyle (1) \; x ^ {2} -dy ^ {2} = \ pm 1 \ quad (2) \; x ^ {2} + xy-fy ^ {2} = \ pm 1}.
První pro d > 0 již byl studován. Jelikož řešení a + b √ d s a a b > 0 jsou dána v rostoucím pořadí a , mocninami základní jednotky h p –1 + k p –1 √ d (kde p je doba √ d ) a také jsou podle výše uvedeného h qp –1 + k qp –1 √ d (pro q > 0), máme h qp –1 + k qp –1 √ d = ( h p - 1 + k p –1 √ d ) q , který nabízí způsob, jak přímo vypočítat tuto posloupnost redukcí √ d , pomocí binomického vzorce nebo indukcí.
Druhá pro f > 0 je velmi podobná. Nejprve máme analogii první ze tří vlastností předchozí části:
Pokud d = 4 f + 1 a pokud dvojice celých čísel ( a , b ), s b > 0 a a + b / 2 ≥ 0, je řešením rovnice (2), pak a / b je redukce
α: =d-12{\ displaystyle \ alpha: = {\ frac {{\ sqrt {d}} - 1} {2}}}.
Demonstrace
Buď .
ω=1+d2{\ displaystyle \ omega = {\ frac {1 + {\ sqrt {d}}} {2}}}
(X+ωy)(X-αy)=(X+y2+dy2)(X+y2-dy2)=(X+y2)2-d(y2)2=X2+Xy+1-d4y2{\ displaystyle (x + \ omega y) (x- \ alpha y) = \ left (x + {\ tfrac {y} {2}} + {\ sqrt {d}} {\ tfrac {y} {2} } \ right) \ left (x + {\ tfrac {y} {2}} - {\ sqrt {d}} {\ tfrac {y} {2}} \ right) = \ left (x + {\ tfrac { y} {2}} \ vpravo) ^ {2} -d \ vlevo ({\ tfrac {y} {2}} \ vpravo) ^ {2} = x ^ {2} + xy + {\ frac {1- d} {4}} y ^ {2}}proto se píše rovnice (2):
(X+y2)2-d(y2)2=(X+ωy)(X-αy)=±1{\ displaystyle \ left (x + {\ tfrac {y} {2}} \ right) ^ {2} -d \ left ({\ tfrac {y} {2}} \ right) ^ {2} = (x + \ omega y) (x- \ alpha y) = \ pm 1}.
Nechť ( a , b ) je dvojice řešení tak, že b ≥ 1 a a + b / 2 ≥ 0 získáme na jedné straně
(nab+ω)(nab-α)=±1b2proto|nab-α|=1b2(nab+ω){\ displaystyle \ left ({\ frac {a} {b}} + \ omega \ right) \ left ({\ frac {a} {b}} - \ alpha \ right) = {\ frac {\ pm 1} {b ^ {2}}} \ quad {\ text {proto}} \ quad \ left | {\ frac {a} {b}} - \ alpha \ right | = {\ frac {1} {b ^ {2 } \ left ({\ frac {a} {b}} + \ omega \ right)}}}
A na druhé straně
nab+ω=nab+12+12d≥12(d-4b2+d){\ displaystyle {\ tfrac {a} {b}} + \ omega = {\ tfrac {a} {b}} + {\ tfrac {1} {2}} + {\ tfrac {1} {2}} { \ sqrt {d}} \ geq {\ frac {1} {2}} \ vlevo ({\ sqrt {d - {\ tfrac {4} {b ^ {2}}}}} + {\ sqrt {d} } \ že jo)}.
Dolní mez vpravo je obecně přísně větší než 2 a poté získáme následující horní mez, která ukazuje, že a / b je redukce α:
|nab-α|<12b2{\ displaystyle \ left | {\ frac {a} {b}} - \ alpha \ right | <{\ frac {1} {2b ^ {2}}}}.
Jediná výjimka nastane, když d = 5 a b = 1:
12(5-4+5)<2{\ displaystyle {\ frac {1} {2}} \ vlevo ({\ sqrt {5-4}} + {\ sqrt {5}} \ vpravo) <2}
ale v tomto případě se a rovná 0 nebo 1, nebo 0/1 a 1/1 jsou skutečně redukce ( √ 5 - 1) / 2 = φ - 1 = [0, 1 ].
Další dvě vlastnosti lze zobecnit následovně, proto platí pro α = √ d stejně jako (pokud je d shodné s 1 modulo 4) až α = ( √ d - 1) / 2:
Nechť α je kvadratické celé číslo (ne celé číslo) větší než jeho konjugát, p jeho období a h i / k i jeho redukce.
-
N ( h i - k i α) = ± 1 tehdy a jen i + 1 je dělitelné p ;
- je-li p liché, existují řešení pro hodnotu –1: odpovídají indexům i = qp - 1 pro q lichá, ta pro q sudá s hodnotou 1. Pokud je p sudé, hodnoty –1 se nikdy nedosáhne.
První metoda
Vlastnosti pokračujícího zlomku kvadratické iracionální umožňují vypočítat aproximace druhé odmocniny . První technika spočívá jednoduše ve výpočtu koeficientů pokračující frakce než jejích redukovaných. Například :
3=[1,1,2¯]{\ displaystyle {\ sqrt {3}} = [1, {\ overline {1,2}}]}.
Redukce h n / k n se vypočítá indukce :
h-1=1,h0=na0,hne+2=nane+2hne+1+hne,k-1=0,k0=1,kne+2=nane+2kne+1+kne,{\ displaystyle {\ begin {aligned} 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 {zarovnáno}}}
což dává následující aproximace √ 3 :
h0=1,h1=2,h2=2×2+1=5,h3=1×5+2=7,h4=19,h5=26,⋯h10=989k0=1,k1=1,k2=2×1+1=3,k3=1×3+1=4,k4=11,k5=15,⋯k10=571.{\ displaystyle {\ begin {aligned} h_ {0} & = 1, & h_ {1} & = 2, & h_ {2} & = 2 \ krát 2 + 1 = 5, & h_ {3} & = 1 \ krát 5 + 2 = 7, & h_ {4} & = 19, & h_ {5} & = 26, & \ cdots \, h_ {10} & = 989 \\ k_ {0} & = 1, & k_ {1} & = 1, & k_ {2} & = 2 \ krát 1 + 1 = 3, & k_ {3} & = 1 \ krát 3 + 1 = 4, & k_ {4} & = 11, & k_ {5} & = 15, & \ cdots \, k_ {10} & = 571. \ end {aligned}}}
Tak, v 10 th kroku, dostaneme zlomek 989/571, přibližně 1,732 až 049, zatímco první 7 přesné významné údaje jsou 1,732 051. Přesnost algoritmu kroku n je lepší než 1 / k n 2 (a sudé, protože zde je období 2, lepší než 1 / (2 k n 2 ), pokud n je liché, podle výše uvedeného článku „Struktura řešení“ ). Pro aproximaci indexu 10 tedy víme, že chyba je menší než 1/571 2 , lepší než 300 000 tis . Jednou silnou stránkou tohoto algoritmu je „kvalita“ navrhovaných řešení, kde jakýkoli zlomek typu a / b s b striktně menší než 571 bude nutně méně dobrý než snížená desetina pokračujícího zlomku ve výše uvedeném smyslu (a dokonce v jemnějším smyslu specifikovaném v článku Spojitý zlomek a Diophantinova aproximace ). Například, nejlepší desetinná přiblížení k jádru 3 se dvěma platné číslice rovna 17/10, se dopustí chyby větší než 50 tis . Tento poněkud ekvivalent 19/11, který odpovídá snížené hodnotě 4, poskytuje přibližně 100 e , což je dvakrát lepší.
Urychlování konvergence
Řešení ( a q , b q ) = ( h qp –1 , k qp –1 ) Pell-Fermatovy rovnice dávají sekvenci extrahovanou ze sekvence redukcí √ n , která tedy konverguje rychleji než druhá. Navíc, protože a + q + b q √ n má tvar ( a + b √ n ) q , můžeme dále urychlit konvergenci výpočtem pouze některých z těchto sil, například u j + v j √ n = ( a + b √ n ) 2 d . Od té doby
uj+1+protij+1ne=(uj+protijne)2,{\ displaystyle u_ {j + 1} + v_ {j + 1} {\ sqrt {n}} = (u_ {j} + v_ {j} {\ sqrt {n}}) ^ {2},}
tato dílčí sekvence se počítá indukcí pomocí:
u0=na,proti0=b,uj+1=uj2+neprotij2aprotij+1=2ujprotij.{\ displaystyle 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}.}
Například pro n = 3 najdeme a = h 1 = 2 a b = k 1 = 1 (srov. Předchozí §) poté
u0=2,u1=22+3×12=7,u2=72+3×42=97,u3=972+3×562=18817,u4=708158977proti0=1,proti1=2×2×1=4,proti2=2×7×4=56,proti3=2×97×56=10864,proti4=408855776{\ displaystyle {\ begin {aligned} u_ {0} & = 2, & u_ {1} & = 2 ^ {2} +3 \ krát 1 ^ {2} = 7, & u_ {2} & = 7 ^ {2} +3 \ krát 4 ^ {2} = 97, & u_ {3} & = 97 ^ {2} +3 \ krát 56 ^ {2} = 18 \, 817, & u_ {4} & = 708 \, 158 \, 977 \\ v_ {0} & = 1, & v_ {1} & = 2 \ krát 2 \ krát 1 = 4, & v_ {2} & = 2 \ krát 7 \ krát 4 = 56, & v_ {3} & = 2 \ krát 97 \ krát 56 = 10 \, 864, & v_ {4} & = 408 \, 855 \, 776 \ end {zarovnáno}}}
a přesnost u 4 / v 4 již přesahuje 18 desetinných míst.
Posloupnost racionálů x j = u j / v j není nic jiného než sekvence vytvořená Heronovou metodou z x 0 = a / b . Podle definice posloupností ( u j ) a ( v j ) skutečně máme
Xj+1=Xj+neXj2{\ displaystyle x_ {j + 1} = {\ frac {x_ {j} + {\ frac {n} {x_ {j}}}} {2}}}.
Jeho konvergence je proto kvadratická .
Historický příklad řešení Pell Fermatovy rovnice
Následující rovnice má dlouhou historii:
X2-61y2=1{\ displaystyle x ^ {2} -61y ^ {2} = 1}.
Brahmagupta použít jako ilustraci předchůdce chakravala metoda na VII -tého století. Využívá ji Bhāskara II, který zdokonaluje metodu a dává jí algoritmickou sílu o něco vyšší, než je zde prezentovaná pokračující frakce.
V únoru 1657 (po další slavnější výzvě z 3. ledna téhož roku) se příkladu chopil opět Pierre de Fermat v dopise Bernardovi Frénicle de Bessymu (rovněž navrhl případ n = 109). Tato výzva je počátkem anglické práce o pokračujících zlomcích kvadratických iracionálů a jejich souvislosti s Pell-Fermatovou rovnicí.
Použijme algoritmus pokračujícího zlomku k výpočtu úplných a částečných kvocientů:
X0=61=7+1X1,X1=7+6112=1+1X2,X2=5+613=4+1X3,{\ displaystyle 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}}},}
X3=7+614=3+1X4,X4=5+619=1+1X5,X5=4+615=2+1X6,X6=6+615,{\ displaystyle \ 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}},}
což dává první dílčí kvocienty: 7, 1, 4, 3, 1, 2. Už není nutné pokračovat. Ve skutečnosti jsou úplné kvocienty x 5 a x 6 přidruženy, protože mají stejného jmenovatele. Polovina palindromu je proto již vysvětlena. Jak dochází k tomuto jevu na dvou sousedních indexy, můžeme odvodit, že tato doba je lichý a rovná se 2 x 5 + 1. Také můžeme odvodit, že 6 se rovná s 5 , jakož i s následujícími podmínkami: 2, 1, 3, 4, 1. Nakonec se poslední člen rovná dvojnásobku prvního, tj. 14. Prvním řešením je řešení indexu 10, jehož pozice je v následujícím výrazu zvýrazněna červeně:
61=[7,1,4,3,1,2,2,1,3,4,1,14¯]{\ displaystyle {\ sqrt {61}} = [7, {\ overline {1,4,3,1,2,2,1,3,4, {\ color {Red} 1}, 14}}]}.
Recyklačními vzorci (jako v § „První metoda“ ) získáme:
h1=8,h2=39,h3=125,h4=164,⋯h10=29718k1=1,k2=5,k3=16,k4=21,⋯k10=3805.{\ displaystyle {\ begin {aligned} 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 {zarovnáno}}}
Víme, protože období je liché, že toto první řešení dává h 10 2 - 61 k 10 2 = –1 a ne +1. Brahmagupta ani Fermat tento typ řešení nepřijímají. Správnou redukcí je tedy 21. st . Abychom to vypočítali, můžeme buď rozšířit výpočet, nebo použít stejný princip jako u druhé metody extrakce kořene:
h21+k2161=(h10+k1061)2{\ displaystyle h_ {21} + k_ {21} {\ sqrt {61}} = (h_ {10} + k_ {10} {\ sqrt {61}}) ^ {2}}.
Řešení problému Fermata je:
h21=1766319049,k21=226153980ah212-61×k212=1{\ displaystyle h_ {21} = 1 \, 766 \, 319 \, 049, \ quad k_ {21} = 226 \, 153 \, 980 \ quad {\ text {a}} \ quad h_ {21} ^ { 2} -61 \ krát k_ {21} ^ {2} = 1}.
Poznámky a odkazy
(fr) Tento článek je částečně nebo zcela převzat z článku na
anglické Wikipedii s názvem
„ Periodická pokračující frakce “ ( viz seznam autorů ) .
-
Georges Ifrah , Univerzální historie postav: Inteligence mužů sdělená čísly a výpočty , Robert Laffont, 1994 ( ISBN 978-2-70284212-6 ) .
-
(it) MT Rivolo a A. Simi, „ on calcolo delle radici quadrate e cubiche in Italia da Fibonacci Bombelli “ , Arch. Hist. Přesné Sci. , sv. 52, n O 21998, str. 161-193.
-
(it) S. Maracchia, „ Estrazione di secondo Cataldi radice quadrata “ , Archimede , sv. 28, n O 21976, str. 124-127.
-
(in) Leonard Eugene Dickson , Diophantine analysis , AMS Bookstore, 1999 ( ISBN 0821819356 ) , str. 355-356 , náhled v Knihách Google .
-
(La) John Wallis, Commercium epistolicum de quæstionibus quibusdam mathematicis nuper habitum Oxonii: Excudebat A. Lichfield, Impensis Tho. Robinson, 1658.
-
(La) Leonhard Euler, Introductio in analysin infinitorum , 1748, sv. I (E101), kap. 18, § 379 [ číst online ] .
-
Joseph-Louis Lagrange, Dodatky k disertační práci o řešení numerických rovnic, § II. - O způsobu přiblížení číselné hodnoty kořenů rovnic , 1770, rééd. Joseph-Alfred Serret , Works of Lagrange , sv. II, Gauthier-Villars ,1877( číst online ) , s. 593-652, přesněji: Poznámka II, s. 603-622 .
-
Různé výsledky jsou publikovány v Lagrangeových Přírůstky do Élémens d'Algebre Leonard Euler, Volume 2: de analyzovat indeterminée , 1 re ed., Bruyset a Desaint, 1774, s. 379-658 + 662-664 a 2 th ed., Bruyset, 1798, s. 379-662 + 666-668 , přetištěno v: Serret 1877 , Œuvres de Lagrange , sv. VII, s. 5-180 . Viz také Serret 1877 , Œuvres de Lagrange , sv. Já, str. 671-731, „ Řešení aritmetického problému “.
-
Évariste Galois , „ Demonstrace z věty o pravidelných řetězové zlomky “, Annals of čistou a aplikovanou matematiku , sv. 19, 1828-1829, str. 294-301 ( číst online )na bibnum , analyzovali Norbert Verdier, Christian Gérini a Alexandre Moatti.
-
K ukázce viz například (de) Oskar Perron , Die Lehre von den Kettenbrüchen , Teubner,1913( číst online ), § 20 ( str. 73–77 ) nebo § 21 ( str. 77–79 ), nebo toto cvičení bylo opraveno z lekce „Úvod do teorie čísel“ na Wikiversity .
-
(in) Dean R. Hickerson, „ Délka jediné periody pokračujícího rozšiřování zlomků √ d “ , Pacific J. Math. , sv. 46,1973, str. 429-432 ( DOI 10.2140 / pjm.1973.46.429 ).
-
(in) JHE Cohn, „ Délka období pokračujícího zlomku lehkého na 1/2 “ , Pacific J. Math. , sv. 71, n o 1,1977, str. 21–32 ( číst online ).
-
(en) EV Podsypanin, „ Délka období kvadratické iracionality “ , Journal of Soviet Mathematics , sv. 18, n o 6,1982, str. 919-923 ( DOI 10.1007 / BF01763963 ).
-
(in) Harold Davenport , The Higher Arithmetic: An Introduction to the Theory of Numbers , Cambridge University Press ,1999, 7 th ed. , 241 s. ( ISBN 978-0-521-63446-5 , číst online ) , s. 99.
-
Demonstraci viz například Perron 1913 , str. 80-82, nebo toto opravené cvičení z lekce „Úvod do teorie čísel“ na Wikiversity .
-
Tato věta je přičítána Legendrovi v (en) Kiyoshi Itō , Encyclopedic Dictionary of Mathematics , sv. 1, MIT Stiskněte ,1993, 2 nd ed. , 1147 s. ( ISBN 978-0-262-59020-4 , číst online ) , s. 315-316. Nicméně, AM Legendre , esej o teorii čísel ,1798( číst online ) , s. 50-57(jako Davenport 1999 , s. 104) se zajímá pouze v případě, že d je celé číslo, a dokazuje pouze přímý význam. Kompletní ukázku najdete například v publikaci Perron 1913 , str. 87-88, nebo toto opravené cvičení z lekce „Úvod do teorie čísel“ na Wikiversity .
-
(in) Eric W. Weisstein , „ Periodic Continued Fraction “ na MathWorld .
-
Perron 1913 , str. 102-104. První vlastnost je také demonstrována v tomto opraveném cvičení lekce „Úvod do teorie čísel“ na Wikiversity . Další dva budou zobecněny a předvedeny v následujícím §.
-
Perron 1913 , str. 104, dokažte to přímo pomocí opakovacích vzorců redukcí a skutečnosti, že a p = 2 a 0 .
-
Pro demonstraci viz například tento domácí úkol opravený na Pell-Fermatově rovnici na Wikiversity .
-
Pomocí toho ( viz výše ) nebo přímým výpočtem, jak je v tomto cvičení opraveno na Wikiversity .13=[0,1,1,2¯]{\ displaystyle {\ frac {1} {\ sqrt {3}}} = [0,1, {\ overline {1,2}}]}
-
(in) BL van der Waerden , „ Pellova rovnice v řecké a hinduistické matematice “ , Russ. Math Surveys (in) , sv. 31, n o 5,1976, str. 210-225.
-
Bhāskara II , Bijaganita , 1150, podle (in) Johna J. O'Connora a Edmunda F. Robertsona , „Pellova rovnice“ v archivu MacTutor History of Mathematics , University of St Andrews ( číst online )..
-
Díla Fermata , str. 334 .
Podívejte se také
Bibliografie
- (en) Alan Baker , Stručný úvod do teorie čísel , Cambridge University Press,1985, 95 s. ( ISBN 978-0-521-28654-1 , číst online )
- Alain Faisant , Diophantinova rovnice druhého stupně , Hermann ,1991, 237 s. ( ISBN 978-2-7056-1430-0 )
- Marc Guinot, aritmetika pro amatéry. Let. 4: Lagrange and Legendre , Aléas, 1996 ( ISBN 978-2-908016-71-0 )
- (en) GH Hardy a EM Wright , Úvod do teorie čísel ( 1 st ed. 1938) [ Obchodní edice ]
- (en) Alexandre Junod, „ Algoritmus řešení Pellovy rovnice “ , General Mathematics Notes , sv. 28, n O 22015, str. 1-8 ( číst online )
- Pierre Samuel , Algebraická teorie čísel [ detail vydání ]
-
Georges Valiron , funkce teorie , 3 e ed., Masson , 1966 Primer aritmetického pokračovat frakce, s. 17-24
-
Sabah Al Fakir , Algebra a teorie čísel - kryptografie: Primality , Paříž, elipsy ,2003, 276 s. ( ISBN 2-7298-1480-9 ) (kapitola 9, Diophantine aproximace)
externí odkazy
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">