Metoda Chakravala

W matematyce, a dokładniej w arytmetyce , metoda chakravala jest algorytmem rozwiązywania równania Pell-Fermata . Powyższe równanie jest przykładem równania diofantycznego , to znaczy z całkowitych współczynników , i których całkowita rozwiązania są poszukiwane. Dokładniej, jest to równanie

x ^ {2} -ny ^ {2} = 1

gdzie n jest naturalną non liczba kwadratowy .

Metoda ta została opracowana w Indiach , a jego korzenie sięgają do VI XX wieku z Aryabhata , a następnie Brahmagupta . Zainicjowany przez Jayadevę (en) , został dalej rozwinięty przez Bhāskara II .

Selenius ocenia to w następujący sposób: „Metoda stanowi najlepszy algorytm aproksymacji o minimalnej długości, który ze względu na kilka właściwości minimalizujących automatycznie daje […], przy niższym koszcie […] i unikaniu dużych liczb, najmniejszych rozwiązań równania […] metoda chakravāla wyprzedziła metody europejskie o ponad tysiąc lat. Ale żadne europejskie wykonanie w całej dziedzinie algebry , dużo później po Bhāskara […], nie dorównało cudownej złożoności i pomysłowości chakravāla . "

To rzeczywiście musi oczekiwać XVII th wieku, że Europejczycy, którzy zignorowali prace indyjskich matematyków odkrywają mniej wydajnych algorytmów - - rozwiązywania tego samego problemu.

Cel

Forma równania Pell-Fermata jest wyrażona w następujący sposób:

x ^ {2} -ny ^ {2} = 1,

gdzie n jest naturalną liczbą niekwadratową. Równanie to diofantyna, co oznacza, że szukane pary ( x , y ) są parami liczb całkowitych. Wszystkie rozwiązania są wyrażone z pary rozwiązań utworzonej z dwóch minimalnych liczb całkowitych o wartości bezwzględnej w zbiorze rozwiązań. Metoda chakravala umożliwia uzyskanie kilku tego rodzaju.

Poniższa równość jest przykładem rozwiązania; Indianie wiadomo było na VII th century:

1151 ^ {2} -92 \ times 120 ^ {2} = 1.

Historia

Matematyka indyjska

The Indian matematyka zainteresował się bardzo wcześnie arytmetyki. Aryabhata , matematyka z VI XX wieku , określa zasady. Opracowuje system liczbowy pokazujący, że prawdopodobnie wiedział o notacji pozycyjnej, a także o istnieniu zera . Pracuje nad równaniami Diofantyna i rozwiązuje tożsamość Bézouta , opracowuje algorytm równoważny algorytmowi Euklidesa, który nazywa ku ṭ ṭ aka (कूटटक), a co oznacza rozpylacz, ponieważ dzieli liczby na mniejsze liczby całkowite. Pracuje również nad ciągłymi frakcjami .

Indyjski matematyk Brahmagupta ( 598 - 668 ) wydaje się być pierwszym, który dogłębnie przeanalizował tę kwestię. Rozumie, jak z dwóch rozwiązań można zbudować nowe. Powtarzając, uzyskuje w ten sposób dowolną liczbę różnych rozwiązań. Ta metoda jest nazywana przez indyjskich matematyków samasą . Brahmagupta wnioskuje z tego trzy algorytmy. Pierwsza pozwala mu znaleźć rozwiązanie, jeśli ma parę liczb całkowitych ( x , y ), których obraz z równania wynosi –1. Znajduje drugie, zajmujące się przypadkiem, w którym obraz ma wartość 2 w wartości bezwzględnej . Znajduje trzeci, dający ten sam wynik, jeśli obraz jest równy ± 4. Rodzi się szkicowa metoda. Rozpoczyna się metodą prób i błędów, aż do znalezienia pary mającej dla obrazu 1, 2 lub 4 w wartości bezwzględnej, kontynuuje z jednym z trzech algorytmów. Brahmagupta używa go w 628 w swojej książce Brahmasphuta siddhanta do rozwiązania następującego równania:

x ^ {2} -83y ^ {2} = 1.

Takie podejście jest niewystarczające, aby poradzić sobie ze złożonymi przypadkami, może być trudno znaleźć metodą prób i błędów parę podającą jedną z sześciu wartości, które pozwalają na wyciągnięcie wniosków. W XII -tego wieku , Bhaskaraćarja bazuje na poprzednich traktatach i proponuje ostateczną formę metodzie chakravala . Odpowiada to dodaniu algorytmu cyklicznego, to znaczy daniu okresowej sekwencji par koniecznie zawierających rozwiązanie. Algorytm cykliczny jest równoważny algorytmowi ułamków ciągłych . Metoda czakrawali kończy się obliczeniami Brahmagupty, jeśli wystąpi jedna z wartości –1, ± 2 i ± 4. Bhāskara II używa go w 1150 roku w swoim traktacie Bijaganita, aby znaleźć minimalne rozwiązanie następującego równania już znalezionego przez Brahmaguptę:

x ^ {2} -61y ^ {2} = 1.

Znaleziona para rozwiązań to:

x = 1 \, 766 \, 319 \, 049 \ quad {\ text {i}} \ quad y = 226 \, 153 \, 980.

Jest mało prawdopodobne, że Bhaskaraćarja wykazać fakt, że algorytm zawsze oferuje rozwiązanie, to znaczy dla każdej wartości n , ponieważ demonstracja, długi i technicznym, wymaga wyrafinowania znacznie wyższą matematyką XII th wieku. Nowe przykłady omawiają później indyjscy matematycy. W XIV th century matematyk nazwany Narayana studiowania jeśli n jest równa 103 w swoich uwagach na temat książki Bijaganita z Bhaskaraćarja.

Europa

W lutym 1657 r. (Po kolejnym bardziej znanym wyzwaniu z 3 stycznia tego samego roku), Pierre de Fermat rzuca wyzwanie Bernardowi Frénicle de Bessy, a za jego pośrednictwem wszystkim europejskim matematykom, aby rozwiązać (między innymi) problem n = 61. Angielska reakcja jest szybka: William Brouncker znajduje algorytm. Frénicle de Bessy proponuje następnie tabelę zawierającą wszystkie rozwiązania dla wartości n mniejszych niż 150, które ostatecznie zostaną utracone, a następnie John Wallis na nowo odkrywa wyniki Brahmagupty i rygorystycznie je demonstruje. Frénicle de Bessy rzuca wyzwanie Brounckerowi z wartością n = 313; w odpowiedzi otrzymuje nie tylko rozwiązanie, ale także stwierdzenie, że jego autor nie potrzebował więcej niż „godzinę lub dwie” na znalezienie.

Dwa podstawowe pytania teoretyczne, a mianowicie, czy dla jakiejkolwiek niekwadratowej liczby naturalnej n istnieje rozwiązanie i czy znalezione rozwiązanie rzeczywiście generuje wszystkie inne, są ostatecznie rozwiązane przez Lagrange'a w 1767 r. Za pomocą algorytmu mniej wydajnego niż ten - następnie zignorowane Europejczyków - ze względu na Bhāskarę, ale której korekta jest łatwiejsza do zademonstrowania. W 1930 roku AA Krishnaswami Ayyangar (nie) twierdzi, że był pierwszym, który udowodnił chakravala .

Wkład Brahmagupty

Tła

Zaproponowane tutaj metody wykorzystują potęgę obecnego formalizmu. Jeśli treść matematyczna jest analogiczna do tej z Brahmagupty, to zarówno techniki wystawiennicze, jak i demonstracje nie odzwierciedlają myśli indyjskiego matematyka. Następujące oznaczenia są używane w dalszej części artykułu. Rozważmy następujące równanie diofantyny, gdzie n jest niekwadratową liczbą naturalną:

(1) \ quad x ^ {2} -ny ^ {2} = 1.

Niech A będzie pierścień o liczbie postaci + $\sqrt$ $n$ b , w którym a i b oznaczają dwie liczby całkowite, N odwzorowanie którego element A łączy swoje „ norma ” i cp mapowanie którego element A wiążącą prowadzone „ koniugat ”:

{\ mathcal N} (a + {\ sqrt n} b) = a ^ {2} -nb ^ {2}, \ quad \ varphi (a + {\ sqrt n} b) = a - {\ sqrt n} b.

W przypadku funkcji N wartość odpowiada normie z A w sensie algebraicznej teorii liczb . Element a + $\sqrt n$ b z A nazywany jest pierwiastkiem równania (1) wtedy i tylko wtedy, gdy jego norma wynosi 1, tj. Jeśli ( a , b ) jest rozwiązaniem (1).

Funkcja φ ma również przydatne właściwości. Jest to automorfizmem od A :

\ forall \ alpha, \ beta \ in A \ quad \ varphi (\ alpha + \ beta) = \ varphi (\ alpha) + \ varphi (\ beta), \ quad \ varphi (\ alpha \ beta) = \ varphi ( \ alpha) \ varphi (\ beta), \ quad \ varphi (1) = 1.

Koniugacja φ jest niekolektywna, to znaczy, że składa się ze sobą dwa razy pod rząd, jest równa tożsamości lub jej wzajemne bijekcja jest sobie równa:

\ forall \ alpha \ in A \ quad (\ varphi \ circ \ varphi) (\ alpha) = \ alpha.

Wreszcie iloczyn dwóch sprzężonych elementów jest równy ich wspólnej normie:

\ forall \ alpha \ in A \ quad {\ mathcal N} (\ alpha) = \ alpha \ varphi (\ alpha).

Jeśli napiszemy α = a + $\sqrt n$ b , jest to uzasadnione następującym obliczeniem:

{\ mathcal N} (\ alpha) = a ^ {2} -nb ^ {2} = (a + {\ sqrt n} b) (a - {\ sqrt n} b) = \ alpha \ varphi (\ alpha ).

Samasa

Pierwsza użyta właściwość to:

Niech α i β będą dwoma elementami A , więc:

{\ mathcal N} (\ alpha \ beta) = {\ mathcal N} (\ alpha) {\ mathcal N} (\ beta).

Jeśli α = a 1 + $\sqrt n$ a 2 i β = b 1 + $\sqrt n$ b 2 , to równość jest zapisana:

(a_ {1} b_ {1} + na_ {2} b_ {2}) ^ {2} -n (a_ {1} b_ {2} + a_ {2} b_ {1}) ^ {2} = ( a_ {1} ^ {2} -na_ {2} ^ {2}) (b_ {1} ^ {2} -nb_ {2} ^ {2}).

Ta równość, znana jako tożsamość Brahmagupty , została przez Indian nazwana Samasą . Aby być przekonanym o jego dokładności, wystarczy wyrazić N jako funkcję automorfizmu φ:

{\ mathcal N} (\ alpha \ beta) = \ alpha \ beta \ varphi (\ alpha \ beta) = \ alpha \ varphi (\ alpha) \ beta \ varphi (\ beta) = {\ mathcal N} (\ alpha ) {\ mathcal N} (\ beta).

Specjalny przypadek odpowiada przypadkowi, w którym β jest liczbą całkowitą k , równość przyjmuje następującą postać:

Niech α będzie elementem A i k liczbą całkowitą, a następnie:

{\ mathcal N} (k \ alpha) = {\ mathcal N} (k) {\ mathcal N} (\ alpha) = k ^ {2} {\ mathcal N} (\ alpha).

Konsekwencje

Niech α będzie elementem A normy 1, to φ (α) jest odwrotnością α i normy 1.
Jeśli równanie (1) dopuszcza rozwiązanie różne od ± 1, to dopuszcza nieskończoność różnych rozwiązań.

Rzeczywiście, N (α) = N (φ (α)) = αφ (α), a jeśli α jest rozwiązaniem (1), to α k również dla dowolnej liczby naturalnej k (ponieważ norma iloczynu jest równa iloczynowi norm), ale wszystkie potęgi liczby rzeczywistej innej niż 0, 1 i –1 są różne.

Zrozumienie, w jaki sposób Brahmagupta rozwiązuje równanie (1), zależy od trzech zdań:

Niech α będzie elementem A.

Jeśli N (α) = ± 1, to α 2 jest rozwiązaniem (1).
Jeśli N (α) = ± 2, tak α 2 /2 wynosi roztwór związku (1).
Jeśli N (α) = 4ε przy ε = ± 1, to rozwiązanie (1) to:
- jeśli α jest podzielne przez 2: (α / 2) (3 - ε) / 2 ;
- Jeśli brak jest jeszcze: α 2 /4;
- w przeciwnym razie: (α 3 /8) (3-e) / 2 .

Demonstracja

: natychmiast.
: jeśli α = a + b $\sqrt n$ to α 2 = a 2 + nb 2 + 2 ab $\sqrt n$ = N (α) + 2 nb 2 + 2 ab $\sqrt n$ jest podzielne przez 2 (i 2 2 N (α 2 / 2) = N (α 2 ) = (± 2) 2 w związku N (α 2 /2) = 1).
: pierwsze dwa przypadki są natychmiastowe, aw trzecim n , a i b są nieparzyste, więc α 3 jest podzielne przez 8, ponieważ ${\ begin {aligned} \ alpha ^ {3} & = (a + b {\ sqrt n}) ^ {3} = a ^ {3} + 3ab ^ {2} n + {\ sqrt n} (nb ^ {3} + 3a ^ {2} b) = a (a ^ {2} -nb ^ {2} + 4nb ^ {2}) + b {\ sqrt n} (3a ^ {2} -3nb ^ {2 } + 4nb ^ {2}) \\ & = a \ left ({\ mathcal N} (\ alpha) + 4nb ^ {2} \ right) + b {\ sqrt n} \ left (3 {\ mathcal N} (\ alpha) + 4nb ^ {2} \ right) = 4a \ left (\ varepsilon + nb ^ {2} \ right) + 4b {\ sqrt n} \ left (3 \ varepsilon + nb ^ {2} \ right) ) \ quad {\ text {with}} \ quad \ varepsilon = \ pm 1. \ end {aligned}}$

Przykłady

Przykład Brahmagupty

Rozpatrzmy tą metodą następujący przykład Brahmagupty:

x ^ {2} -83y ^ {2} = 1.

Niech α = m + √ 83 , przy czym liczba całkowita m zostanie wybrana tak, że norma N (α) = m 2 - 83 jest najmniejszą możliwą wartością bezwzględną: m = 9, α = 9 + √ 83 , N (α) = –2. Poprzedniej wniosek wynika, że a 2 /2 to rozwiązanie. Efektywnie :

\ alpha ^ {2} = (9 ^ {2} +83 \ cdot 1) + {\ sqrt {83}} \ cdot 2 \ times 9 \ times 1 = 164 + {\ sqrt {83}} \ cdot 18 = 2 \ left (82 + {\ sqrt {83}} \ cdot 9 \ right)

82 ^ {2} -83 \ times 9 ^ {2} = 6 \, 724-6 \, 723 = 1.

Wyzwanie Fermata

Wyzwanie Fermata rozwiązuje się w ten sam sposób:

x ^ {2} -61y ^ {2} = 1.

Brahmagupta robi to w następujący sposób: zauważa, że jeśli α = 39 + 5 √ 61, to N (α) jest równe –4. Oczywiście formalizm Brahmagupty nie ma nic wspólnego z tym użytym tutaj, nawet jeśli obliczenia są takie same. Oblicza a 2 /2:

{\ frac {\ alpha ^ {2}} 2} = {\ frac 12} (39 + 5 {\ sqrt {61}}) ^ {2} = {\ frac 12} (39 ^ {2} + 5 ^ {2} \ times 61 + 2 \ times 5 \ times 39 {\ sqrt {61}}) = 1 \, 523 + 195 {\ sqrt {61}}.

Następnie oblicza α 3 /8 i jego normy:

{\ frac {\ alpha ^ {3}} {8}} = {\ frac 14} (39 + 5 {\ sqrt {61}}) (1 \, 523 + 195 {\ sqrt {61}}) = 29 \, 718 + 3 \, 805 {\ sqrt {61}} \ quad {\ text {et}} \ quad {\ mathcal N} ({\ frac {\ alpha ^ {3}} 8}) = 29 \, 718 ^ {2} -61 \ times 3 \, 805 ^ {2} = - 1.

Rozwiązanie polega zatem α 6 /64, są:

{\ frac {\ alpha ^ {6}} {64}} = (29 \, 718 + 3 \, 805 {\ sqrt {61}}) ^ {2} = 29 \, 718 ^ {2} +61 \ times 3 \, 805 ^ {2} +2 \ times 29 \, 718 \ times 3 \, 805 {\ sqrt {61}} = 1 \, 766 \, 319 \, 049 + 226 \, 153 \, 980 { \ sqrt {61}}.

Metoda jest niezwykle ekonomiczna jak na tak stary algorytm.

Wkład Bhāskary II

Zasada metody

Trudność metody Brahmagupty polega na tym, że nie zawsze łatwo jest znaleźć liczbę α A, której norma jest równa ± 1, ± 2 lub ± 4. Wkład Bhāskary II opisany w Siddhanta Siroman polega na wzbogaceniu metody o algorytm, który nieomylnie kończy się dostarczeniem „quasi-rozwiązania” tego rodzaju.

Bhaskaraćarja opiera się na zasadzie indukcji sekwencję pierwiastków a j = o j + b j $\sqrt n$ z A w sposób następujący. Pierwszym elementem ciągu jest α 0 = 1, norma k 0 = 1. Załóżmy, że ciąg zdefiniowany jest w kolejności j . Konstruujemy element β j = m j + $\sqrt n$ . Naturalna liczba całkowita m j jest taka, że a j + m j b j jest wielokrotnością normy k j z α j - innymi słowy taka, że b j m j jest przystająca do - a j modulo k j - i m j minimalizuje bezwzględna wartość normy m j 2 - n z β j . Element α j + 1 jest wtedy definiowany przez

\ alpha _ {{j + 1}} = a _ {{j + 1}} + b _ {{j + 1}} {\ sqrt n} = {\ frac {\ alpha _ {j} \ beta _ { j}} {| {\ mathcal N} (\ alpha _ {j}) |}} = {\ frac {a_ {j} m_ {j} + nb_ {j} + {\ sqrt n} (a_ {j} + m_ {j} b_ {j})} {| {\ mathcal N} (\ alpha _ {j}) |}}

lub

\ alpha _ {{j + 1}} \ varphi (\ alpha _ {j}) = \ pm \ beta _ {j},

± odpowiadający znakowi N (α j ) - zaletą wzięcia pod uwagę tego znaku jest to, że a j i b j są zawsze dodatnie.

Zobaczymy później, że warunek „ a j + m j b j wielokrotność k j ” jest równoważny z „ m j przystającym do - m j –1 modulo k j ”, co upraszcza algorytm.

Przykłady

Wyzwanie Fermata

Wybierzmy ponownie n równe 61. Wartość m 0 jest równa 8, aby zminimalizować | N (β 0 ) |. Rzeczywiście, √ 61 jest między 7 a 8 a 8 2 - 61 = 3 <61 - 7 2 . Następnie wybiera się liczbę całkowitą m 1 spośród tych przystających, modulo N (α 1 ) = N (8 + √ 61 ) = 8 2 - 61 = 3, przy - m 0 = –8, a więc w 1. Z dwóch kolejnych wyrazów 7 i 10 tej arytmetycznej sekwencji, która otacza √ 61 , tę, która minimalizuje | N (β 1 ) | jest m 1 = 7, co daje:

\ alpha _ {2} = {\ frac {8 \ times 7 + 61} 3} + {\ frac {8 + 7} 3} {\ sqrt {61}} = 39 + 5 {\ sqrt {61}} \ quad {\ text {i}} \ quad {\ mathcal N} (\ alpha _ {2}) = - 4.

Reszta metody jest metodą Brahmagupty . Metoda chakravala umożliwia teraz rozwiązanie wyzwania Fermata bez prób i błędów oraz przy minimum obliczeń.

Przykład Narayana

Ten drugi przykład również pochodzi z Siroman Siddhanty z Bhāskary II, z komentarzem Narayana. Dla n = 103, m 0 = 10. Następnie wybiera się liczbę całkowitą m 1 przystającą do –10 modulo N (α 1 ) = N (10 + √ 103 ) = 10 2 - 103 = –3. Ponieważ 8 < √ 103 <11 i 11 2 - 103 = 18 <103 - 8 2 , otrzymujemy m 1 = 11 i

\ alpha _ {2} = {\ frac {10 \ times 11 + 103} {3}} + {\ frac {10 + 11} {3}} {\ sqrt {103}} = 71 + 7 {\ sqrt { 103}} \ quad {\ text {i}} \ quad {\ mathcal N} (\ alpha _ {2}) = - 6.

Następnie wybieramy m 2 przystające do –11 modulo 6. Ponieważ 7 < √ 103 <13 i 103 - 7 2 = 54 <13 2 - 103, otrzymujemy m 2 = 7 - zauważmy przy tej okazji, że „minimalizuj | m 2 - n | „Nie zawsze pokrywa się z” minimalizuj | m - $\sqrt n$ | "- następnie

\ alpha _ {3} = 203 + 20 {\ sqrt {103}} \ quad {\ text {i}} \ quad {\ mathcal N} (\ alpha _ {3}) = 9.

Wtedy modulo 9, m 3 musi być przystające do –7. Aby zminimalizować | N (β 3 ) |, musimy wybrać m 3 równe 11. Otrzymujemy

\ alpha _ {4} = 477 + 47 {\ sqrt {103}} \ quad {\ text {i}} \ quad {\ mathcal N} (\ alpha _ {4}) = 2.

Obliczenia Brahmagupty pozwalają nam stwierdzić: poszukiwaną wartością jest

{\ frac {\ alpha _ {4} ^ {2}} 2} = {\ frac {(477 + 47 {\ sqrt {103}}) ^ {2}} 2} = 227 \, 528 + 22 \; 419 {\ sqrt {103}}.

Niepowtarzalność

Poniższy przykład pokazuje, że liczba α j +1 zdefiniowana z α j nie zawsze jest unikalna: dla n = 58 α 1 jest równe 8 + √ 58 , z normy 6, to dla m 1 przystającej do –2 modulo 6, minimum | m 1 2 - 58 | wynosi 42, osiągnięty dla dwóch wartości 4 i 10 m 1 . Dwie odpowiednie wartości dla α 2 to 15 + 2 √ 58 , przy normie –7 i 23 + 3 √ 58 , przy normie 7. Jednak dla pierwszej z nich znajdujemy m 2 = 10, a dla drugiej m 2 = 4, więc dla obu α 3 = 38 + 5 √ 58 , przy normie –6, to m 3 = 8 i α 4 = 99 + 13 √ 58 , przy normie –1. Rozgałęzienie było więc tylko tymczasowe, a oba zestawy dają to samo rozwiązanie.

Demonstracje związane z wkładem Bhāskary II

Lemat

Lemat dowodzi istnienia ciągu używanego przez Bhāskara II, wiedząc, że jeśli k i b są dla siebie liczbami pierwszymi, to dla dowolnej liczby całkowitej a istnieją liczby całkowite m, dla których a + bm jest podzielne przez k . Rzeczywiście, rozwiązując tożsamość Bézouta - którą Indianie już wiedzieli, jak zrobić z algorytmem Euklidesa - znajdujemy liczby całkowite v, dla których 1 - bv jest wielokrotnością k , i wystarczy ustawić m = - av .

Niech a , b będą względnie pierwsze i m , n dowolnymi dwiema liczbami całkowitymi. Stawiamy k = a 2 - nb 2 , c = am + bn i d = a + bm .

Jeśli d jest wielokrotnością k następnie c zbyt, a dwie liczby całkowite c / k oraz d / k są względnie pierwsze.

Ten lemat jest natychmiastowy, zauważając, że ad - bc = k i że b jest liczbą pierwszą z k . Zastosowany - z zapisami § „Zasada metody” - do a = a j i b = b j , pokazuje, że na każdym etapie konstrukcji ciągu (α j ), jeśli m j wybiera się zgodnie z wskazana wówczas metoda α j β j jest wielokrotnością N (α j ), α j +1 jest elementem A, a a j +1 i b j +1 są względnie pierwsze, co umożliwia iterację konstrukcji.

Możemy dalej zauważyć, że ograniczenie (przy wyborze m j ) „ a j + b j m podzielne przez N (α j )” jest równoważne z „ m przystającym do - m j –1 modulo N (α j )”. Rzeczywiście, b j jest liczbą pierwszą przy N (α j ), a a j + b j (- m j –1 ) jest podzielne przez N (α j ), ponieważ φ (α j ) β j –1 = ± N (α j ) φ (α j –1 ).

Cykliczność

Kiedy już wykazaliśmy, że ciąg (α j ) jest dobrze zdefiniowany, zbadajmy jego zachowanie. Jest w pewnym sensie „cykliczny”. Dokładniej, zauważając cl (α) klasę równoważności α dla relacji „być skojarzoną ” (to znaczy zwielokrotnić jeden z drugiego elementem odwracalnym - tak, że wszystkie elementy klasy mają tę samą normę w wartość bezwzględna), sekwencja ( cl (α j )) jest okresowa od określonej rangi. Ta właściwość jest bezpośrednią konsekwencją trzech twierdzeń:

Ciąg (| N (α j ) |) jest ograniczony przez $\sqrt n$ .
Dla każdego prawdziwego C > 0, istnieje skończona liczba standardowych klas równoważności wartości bezwzględnej mniejszej niż C .
Jeśli dla dwóch indeksów i i j , a i = εα j przy ε odwracalnej w A , to α i +1 = εα j +1 .

Demonstracja

k j : = | N (α j ) | < $\sqrt n$ : pokażmy to przez indukcję. Mamy k 0 = 1 < $\sqrt n$ . Załóżmy, że k j < $\sqrt n$ . Wtedy istnieje liczba całkowita m (koniecznie dodatnia) taka, że m < $\sqrt n$ <m + k j i taka, że m j jest równe m lub m + k j , w zależności od tego, czy n - m 2 jest mniejsze lub większe niż ( mK + j ) 2 - n , innymi słowy, w zależności od tego, czy m 2 + k j m + k j 2 /2 - n jest dodatnia lub ujemna. Porównując m z dodatnim pierwiastkiem tego wielomianu kwadratowego , możemy łatwo wywnioskować, że w obu przypadkach | m j 2 - n | ≤ k j $\sqrt n - k j 2 /4$ < k j $\sqrt n$ , gdzie k j + 1 = | m j 2 - n | / k j < $\sqrt n$ .
Istnieje tylko skończoną liczbę klas równoważności z normą wartości bezwzględnej mniejszej niż C : wystarczy, aby pokazać, że przez każdą wartość całkowitą N > 0, istnieje tylko skończoną liczbę klas normy wartość bezwzględną równą N . W tym celu należy najpierw zauważyć, że dwa elementy mają tę samą klasę wtedy i tylko wtedy, gdy główny ideał, który generują, jest taki sam, i że każdy ideał wygenerowany przez element, którego bezwzględna wartość normy jest równa N, jest subaddytywną grupą A zawierające NA . Dlatego wystarczy udowodnić, że dodatkowe podgrupy A zawierające NA są skończone. Są jednak w sprzeczności z podgrupami grupy ilorazowej A / NA , która jest skończona (kardynała N 2 ), co kończy się wnioskiem.
Jeśli α i = εα j z ε odwracalnym w A, to α i +1 = εα j +1, ponieważ | N (α i ) | = | N (α j ) | a β podzielne przez φ (α i ) - które są takie same jak te podzielne przez φ (α j ) - spełniają α i β = εα j β.

Te właściwości pokazują tylko okresowość od określonej rangi. Poniższy akapit pokazuje że ta ranga wynosi 0.

Struktura pakietu

Fakt, że sekwencja jest okresowa, nie oznacza a priori, że osiąga punkt normy równy 1 w wartości bezwzględnej. Tak jest jednak nadal:

Istnieje indeks j > 0 taki, że N (α j ) = ± 1 (stąd N (α 2 j ) = 1).
Sekwencja ( cl (α k )) tworzy „ palindrom aż do koniugacji”: cl (α j –1 ) = cl (φ (α 1 )), cl (α j –2 ) = cl (φ (α 2 ) ) itp.

Częściowa demonstracja

Niech B będzie zbiorem elementów a + b $\sqrt n$ z A, dla których a i b są pierwsze względem siebie, oraz ψ będzie funkcją od B do B zdefiniowaną przez: do elementu α z B przypisujemy element β formy m + $\sqrt n$ z m naturalną liczbą całkowitą taką, że βα jest wielokrotnością normy α, normy minimalnej (widzieliśmy powyżej , że mogą być dwie: możemy na przykład systematycznie wybierać w tym przypadku tę, która odpowiada mniejszej z dwie wartości m ), to ustawiamy ψ (α) = αβ / | N (α) |. Lemat i poprzedni akapit pokazują, że mapa ψ jest dobrze zdefiniowana i to

\ forall k \ in \ mathbb {N}, \ quad \ psi (\ alpha _ {k}) = \ alpha _ {{k + 1}}.

Ta funkcja ma symetrię względem funkcji φ:

Następująca właściwość jest weryfikowana:

\ forall \ alpha, \ gamma \ in B \ quad \ psi (\ alpha) = \ gamma \ Rightarrow \ psi (\ varphi (\ gamma)) = \ pm \ varphi (\ alpha).

Dokładniej: ψ (φ (γ)) = ε 1 ε 2 φ (α), gdzie ε 1 (odp. Ε 2 ) oznacza znak normy α (odp. Γ).

Rzeczywiście, jeśli α ma dla obrazu przez ψ wartość γ, istnieje unikalny element β postaci m + $\sqrt n$ z m naturalną liczbą całkowitą taką, że

\ gamma = {\ frac {\ alpha \ beta} {| {\ mathcal N} (\ alpha) |}} = \ epsilon _ {1} {\ frac {\ alpha \ beta} {\ alpha \ varphi (\ alpha )}} = \ epsilon _ {1} {\ frac {\ beta} {\ varphi (\ alpha)}} \ quad {\ text {i}} \ quad (1) \ quad \ varphi (\ alpha) = \ epsilon _ {1} {\ frac {\ beta} {\ gamma}} = \ epsilon _ {1} \ epsilon _ {2} {\ frac {\ varphi (\ gamma) \ beta} {| {\ mathcal N} (\ varphi (\ gamma)) |}}.

Element β ma postać m + $\sqrt n$ z m naturalnego liczbą całkowitą, że βφ (γ) stanowi wielokrotność standardowej cp (y), ponieważ φ (α) należy do A . Niech β 'będzie elementem spełniającym te właściwości, a przy normie mniejszej niż β z równości γ = αβ' / N (β ') wynika, że β' ma normę większą niż β . Wychodzimy z tego, że normy β i β 'są równe, a ich minimalny charakter jest weryfikowany. Równość (1) pokazuje, że ε 1 ε 2 φ (α) jest rzeczywiście obrazem φ (γ) przez ψ. Propozycja jest zademonstrowana.

Możemy wywnioskować, że ψ jest funkcją bijection B w B .

Istnieje indeks j > 0 taki, że N (α j ) = ± 1:

Zgodnie z poprzednim § „Cykliczność” istnieją dwa wskaźniki 0 ≤ k <k + j takie, że cl (α k + j ) = cl (α k ). Z bijektywności ψ pokazanej powyżej , wnioskujemy, że cl (α j ) = cl (α 0 ), to znaczy, że N (α j ) = ± 1. Ponadto, podobnie jak b j > 0, znalezione rozwiązanie nie jest trywialne .

Sekwencja (α j ) tworzy palindrom:

Z cl (ψ (α j –1 )) = cl (φ (α 0 )) wnioskujemy przez indukcję z własności ψ przedstawionej powyżej , że cl (ψ (α j –1– k )) = cl (φ (α k )).

Ułamek ciągły

Metoda czakrawali jest bardzo zbliżona do metody frakcji ciągłej. Tutaj celem jest zbliżenie się do pierwiastka n przez optymalne wyrażenie o następującej naturze:

{\ sqrt n} = f_ {0} + {\ cfrac 1 {f_ {1} + {\ cfrac {1} {f_ {2} + {\ frac 1 {f_ {3} + \, \ cdots}}} }}} \ quad {\ text {with}} \ quad f_ {i} \ in \ mathbb {Z}.

Podejście teoretyczne

Niech n będzie naturalną liczbą niekwadratową. Definiujemy przez indukcję dwie sekwencje, ( f j ) j ≥0 o wartościach w ℤ i (θ j ) j ≥ - 1 w ℚ ( $\sqrt n$ ) przez: θ –1 = $\sqrt n$ i dla wszystkich j ≥ –1 , f j +1 jest liczbą całkowitą (lub mniejszą z dwóch liczb całkowitych), dla której | N (θ j - f j +1 ) | jest minimalna i θ j +1 = 1 / (θ j - f j +1 ). Fakt, że $\sqrt n$ jest irracjonalne, pokazuje, że θ j jest zawsze irracjonalne; sekwencje ( f j ) i (θ j ) są zatem dobrze zdefiniowane.

Ta definicja różni się od tradycyjnego ułamka ciągłego, ponieważ tutaj θ j i f j niekoniecznie są dodatnie.

Niech ( h j ) i ( k j ) będą ciągami liczników i mianowników redukcji .

Jeżeli (α j ) i (β j ) oznaczają sekwencje zdefiniowane wcześniej , spełnione są następujące równości (zgodnie z konwencją m –1 = 0):

\ forall j \ in \ mathbb {N} \ quad f_ {j} = (- 1) ^ {j} {\ frac {m _ {{j-1}} + m_ {j}} {{\ mathcal N} (\ alpha _ {j})}}, \ quad \ theta _ {j} = (- 1) ^ {{j + 1}} {\ frac {\ varphi (\ beta _ {j})} {{\ mathcal N} (\ alpha _ {j-1}}} \ quad {\ text {i}} \ quad \ alpha _ {j} = \ pm (h _ {{j- 1}} + k _ {{j- 1}} {\ sqrt n}).

Tak więc cykliczność i właściwość palindromu tej kontynuowanej frakcji pozwalają zademonstrować właściwości metody czakrawali i vice versa. Jeśli algorytm rekurencyjny narzuca β j, aby miała systematycznie ujemną normę, to dowody artykułu pozostają ważne, a powiązane ułamki ciągłe odpowiadają zwykłej definicji.

Demonstracja

f j = (–1) j ( m j –1 + m j ) / N (α j ) i θ j = (–1) j +1 N (α j ) / φ (β j ): pokażmy to wynik przez powtarzanie się na j . Z definicji f 0 = m 0 i $\ theta _ {0} = {\ frac 1 {{\ sqrt n} -m_ {0}}} = {\ frac 1 {- \ varphi (\ beta _ {0})}} = - {\ frac {{ \ mathcal N} (\ alpha _ {0})} {\ varphi (\ beta _ {0})}}.$ Załóżmy, że wynik ustalono dla zamówienia j - 1 i pokaż, że jest on prawdziwy dla zamówienia j . $(-1) ^ {j} \ left (f_ {j} + {\ frac 1 {\ theta _ {j}}} \ right) = (- 1) ^ {j} \ theta _ {{j- 1} } = {\ frac {{\ mathcal N} (\ alpha _ {{j-1}})} {\ varphi (\ beta _ {{j-1}})}} = {\ frac {{\ mathcal N } (\ alpha _ {{j- 1}}) \ beta _ {{j- 1}}} {\ varphi (\ beta _ {{j- 1}}) \ beta _ {{j- 1}}} } = {\ frac {{\ mathcal N} (\ alpha _ {{j- 1}}) \ beta _ {{j- 1}}} {{\ mathcal N} (\ pm \ alpha _ {j} \ varphi (\ alpha _ {{j-1}}))}} = {\ frac {\ beta _ {{j-1}}} {{\ mathcal N} (\ alpha _ {j})}} = { \ frac {m _ {{j-1}} + m_ {j}} {{\ mathcal N} (\ alpha _ {j})}} - {\ frac {\ varphi (\ beta _ {j})} {{\ mathcal N} (\ alpha _ {j})}}$ a wybierając β j , liczba całkowita f = ( m k –1 + m k ) / N (α k ) jest tą, dla której bezwzględna wartość normy (β j –1 / N (α j )) - f jest minimalne. Jest więc równe (–1) j f j, a reszta –φ (β j ) / N (α j ), to (–1) j / θ j .
α j = ± ( h j –1 + k j –1 $\sqrt n$ ): odnotowując ε j znak N (α j ) mamy dla wszystkich j > 0: $(-1) ^ {j} f_ {j} {\ mathcal N} (\ alpha _ {j}) = m_ {j} + m _ {{j- 1}} = \ beta _ {j} + \ varphi (\ beta _ {{j-1}}) = \ varepsilon _ {j} \ alpha _ {{j + 1}} \ varphi (\ alpha _ {j}) + \ varepsilon _ {{j-1}} \ varphi (\ alpha _ {j}) \ alpha _ {{j- 1}}$ to jest do powiedzenia $(-1) ^ {j} f_ {j} \ alpha _ {j} = \ varepsilon _ {j} \ alpha _ {{j + 1}} + \ varepsilon _ {{j- 1}} \ alpha _ { {d-1}}$ lub pozując $\ varepsilon '_ {j} = (- 1) ^ {{j (j-1) / 2}} \ prod _ {{0 \ leq i <j}} \ varepsilon _ {i} ~: \ quad \ varepsilon '_ {{j + 1}} \ alpha _ {{j + 1}} = f_ {j} \ varepsilon' _ {j} \ alpha _ {j} + \ varepsilon '_ {{j-1}} \ alfa _ {{j-1}}.$ Dwa ciągi (ε ' j α j ) i ( h j –1 + k j –1 $\sqrt n$ ) spełniają zatem tę samą relację powtarzania rzędu 2. Ponieważ pokrywają się dla j = 0 i dla j = 1, są one równe .

Metoda obliczeniowa

Podejście z ułamkiem ciągłym oferuje wzbogacenie poprzedniej metody algorytmicznej dla równania Pella-Fermata lub określenia frakcji ciągłej. Zilustrujmy te metody na przykładzie n = 313 i pokażmy, jak Brouncker mógł faktycznie rozwiązać to wyzwanie w godzinę lub dwie. Z definicji m –1 = 0 i N (α 0 ) = 1, wówczas dla dowolnego indeksu j ≥ 0:

m j jest przystające do - m j –1 modulo N (α j ) i jego kwadrat jest jak najbliżej 313;
N (β j ) = m j 2 - 313;
N (a j +1 ) = N (β j ) / N (a j ).

W ten sposób znajdujemy m 0 = 18, N (β 0 ) = 11, N (α 1 ) = 11, m 1 = 15, N (β 1 ) = –88, N (α 2 ) = –8 itd.

Wyprowadzamy f j ze wzoru z poprzedniego akapitu: f 0 = m 0 = 18, f 1 = - (18 + 15) / 11 = –3 itd.

To podejście pozwala uniknąć dużych liczb, z wyjątkiem h j –1 i k j –1 , gdzie a j i b j są wartościami bezwzględnymi. Są one obliczane dla j ≥ 1 za pomocą wzoru na indukcję z f j .

Co więcej, jeśli normy dwóch kolejnych α są równe lub przeciwne, to bezpośrednio z algorytmu wynika, że β i normy α tworzą palindrom. Dokładniej: jeśli N (α r +1 ) = ε N (α r ) z ε = ± 1, to przez indukcję na k , β r + k = β r - k i N (α r + k +1 ) = ε N (α r - k ). W konsekwencji α 2 r +1 jest wtedy odwracalne (o normie ε) i - zgodnie z wyrażeniem ciągu α zgodnie z ciągiem β - równe ε r α r +1 / φ (α r ) = ε r α r α r +1 / N (α r ).

W ten sposób konstruujemy poniższą tabelę, w której widzimy, że wspomniana sytuacja ma miejsce dla r = 6 i ε = –1:

jot	m j	N (β j ) = m j 2 - 313	N (α j ) = N (β j - 1 ) / N (α j - 1 )	f j = (–1) j (m j + m j - 1 ) / N (α j )	h j - 1 = f j - 1 h j - 2 + h j - 3	k j - 1 = f j - 1 k j - 2 + k j - 3
0	18	11	1	18	1	0
1	15	–88	11	–3	18	1
2	17	–24	–8	–4	–53	–3
3	19	48	3	–12	230	13
4	13	–144	16	2	–2 813,	–159
5	14	–117	–9	3	–5 396	–305
6	12	–169	13	2	–19,001	–1074
7	14	–117	–13	2	–43,398	–2 453,

Sekwencja norm α wynosi zatem 1, 11, –8, 3, 16, –9, 13, –13, 9, –16, –3, 8, –11, –1, co stanowi element normy - 1:

\ alpha _ {{13}} = {\ frac {\ alpha _ {6} \ alpha _ {7}} {13}} = (19 \, 001 + 1 \, 074 {\ sqrt {313}}) ( 43 \, 398 + 2 \, 453 {\ sqrt {313}}) = 126 \, 862 \, 368 + 7 \; 170 \; 685 {\ sqrt {313}}.

(Liczba ta jest równa również jako α 3 2 α 5 /9.) Teraz pozostaje tylko prostokątny uzyskania pożądanego rozwiązanie:

\ alpha _ {{26}} = \ alpha _ {{13}} ^ {2} = (126 \, 862 \, 368 + 7 \; 170 \; 685 {\ sqrt {313}}) ^ {2} = 32 \; 188 \; 120 \; 829 \; 134 \; 849 + 1 \; 819 \; 380 \; 158 \; 564 \; 160 {\ sqrt {313}}.

Metoda chakravala umożliwia zatem ręczne rozwiązywanie tego rodzaju obliczeń. To samo podejście bez obliczania kolumny h j -1 i k j -1 , bezużyteczne dla tego celu, pozwala na określenie do ułamka z √ 313 . Znalezienie rozwiązania tak, że sekwencja ( f k ) zawiera tylko wartości dodatnie zakłada ograniczające do wyboru m k mniej niż lub równe do 17 Chcielibyśmy następnie znaleźć się ułamka tego nieracjonalne kwadratowy : [17, 1, 2, 4, 11, 1, 1, 3, 2, 2, 3, 1, 1, 11, 4, 2, 1, 34 ].

Uwagi i odniesienia

(en) Clas-Olof Selenius , „ Rationale of the chakravāla process of Jayadeva and Bhāskara II ” , Historia Mathematica , tom. 2,1975, s. 167-184 ( czytaj online ).
(w) Victor J. Katz and Karen Parshall , Taming the Unknown , PUP ,2014, 504 str. ( ISBN 978-1-4008-5052-5 , czytaj online ) , str. 122-123 ° C.
Georges Ifrah , Uniwersalna historia liczb: inteligencja ludzi wyrażona liczbami i obliczeniami , Robert Laffont, 1994 ( ISBN 978-2-70284212-6 ) .
Dokładna analiza jego pracy matematycznej znajduje się w rozprawie doktorskiej A. Keller Indyjski komentarzem do VII XX wieku - Bhaskara i Ganita-pada od Aryabhatiya [ czytaj on-line ] .
(w) John Stillwell , Mathematics and Its History [ wydania detaliczne ], 2010, s. 75-80 .
(w) BL van der Waerden , równanie Pella w matematyce greckiej i hinduskiej , Russ. Ankiety matematyczne 31 (5), 1976, s. 210-225
(en) John J. O'Connor i Edmund F. Robertson , „Pell's equation” , w archiwum MacTutor History of Mathematics , University of St Andrews ( czytaj online ).
Zobacz stronę Pierre Fermat w witrynie gminy Beaumont-de-Lomagne .
Dzieła Fermata , s. 334 .
Ta informacja pochodzi z korespondencji pomiędzy różnymi aktorami, opublikowanej w (la) John Wallis, Commercium epistolicum de quæstionibus quibusdam mathematicis nuper habitum Oxonii: Excudebat A. Lichfield, Impensis Tho. Robinson , 1658
Joseph-Alfred Serret , Dzieła Lagrange , vol. I, str. 671-731 : „Rozwiązanie problemu arytmetycznego”.
(w) AA Krishnaswami Ayyangar , „ Nowe światło na złotą cykliczną metodę rozwiązywania nieokreślonych równań drugiego stopnia dla dwóch zmiennych Bhaskary Chakravala ” , J. Indian Math. Soc. , vol. 18, 1929-30, s. 225-248 ( czytaj online ).
W tym przypadku stosuje się α = (10 + √ 92 ) 2 /4 = 48 + 5 √ 92 8 standardowego 2 /4 2 -4, umożliwia Brahmagupta rozwiązania jego pierwszy przykład : Stillwell , s. 77 .
(w) Harold Edwards , Ostatnie twierdzenie Fermata: genetyczne wprowadzenie do algebraicznej teorii liczb , Springer al. " GTM " ( N O 50)2000, 3 e ed. , 407 s. ( ISBN 978-0-387-95002-0 , czytaj online ) , rozdz. I, § 9 („Równanie Pella”) , s. 25-36.
Selenius 1975 dodaje tę wartość bezwzględną do mianownika, jednocześnie dwukrotnie określając, że Bhāskara tego nie zrobił. Edwards 2000 uwzględnia tę bezwzględną wartość w swoim sformułowaniu, nawet bez tej precyzji.
(en) Stillwell , str. 79 .
Metoda czakrawali jest pod tym względem lepsza od metod Eulera i Brounckera: oprócz osiągnięcia wyniku w mniejszej liczbie kroków, obejmuje ona obliczenia na mniejszych liczbach ( Selenius 1975 ).
Edwards 2000 , str. 35.
Suite A040295 z OEIS .

Zobacz też

Link zewnętrzny

(en) John J. O'Connor i Edmund F. Robertson , „Indian Mathematics: Redressing the balance, 8 VI. Równanie Pella ” , w archiwum MacTutor History of Mathematics , University of St Andrews ( czytaj online ).

Bibliografia

(en) Leonard Eugene Dickson , Historia teorii liczb (en) [ szczegóły wydań ], vol. II, analiza diofantyczna
Jean Trignan, Wprowadzenie do problemów aproksymacji: ułamki ciągłe, różnice skończone , Éditions du Choix, 1994 ( ISBN 978-2-909028-16-3 )