Metoda ćakrawala

Metoda ćakrawala (चक्रवाल विधि) – algorytm pozwalający rozwiązywać nieoznaczone równania kwadratowe, w tym równanie Pella. Przypisywana jest zazwyczaj Bhaskarze II (ok. 1114–1185)^[1][2], choć niektórzy przypisują ją Dźajadewie (ok. 950–1000)^[3]. Jayadeva odkrył, że metoda Brahmagupty rozwiązywania tego typu równań może być uogólniona, a następnie opisał ogólny proces, który został dopracowany przez Bhaskarę II w pracy Bidźaganita. Algorytm został nazwany metodą ćakrawala od słowa ćakra, oznaczającego koło w sanskrycie, co odnosi się do jego cyklicznej natury^[4]. E.O. Selenius stwierdził, że żadne z ówczesnych, ani późniejszych dokonań matematyki europejskiej nie dorównuje potędze matematycznej złożoności metody Bhaskary^[1][4].

Metoda znana jest także jako metoda cykliczna i zawiera ślady indukcji matematycznej^[5].

Historia

Brahmagupta w 628 r. n.e. badał nieoznaczone równania kwadratowe, w tym równanie Pella

${\displaystyle x^{2}=Ny^{2}+1,}$

dla całkowitych wartości ${\displaystyle x}$ i ${\displaystyle y.}$ Brahmagupta potrafił rozwiązać je dla wielu, choć nie wszystkich wartości ${\displaystyle N.}$

Dźajadewa (IX wiek) i Bhaskara (XII wiek) zaproponowali pierwsze pełne rozwiązanie powyższego równania, używając metody ćakrawala do rozwiązania przypadku ${\displaystyle N=61{:}}$

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

Równanie to zostało po raz pierwszy rozwiązane w Europie przez Williama Brounckera w latach 1657–1658 w odpowiedzi na wyzwanie rzucone przez Fermata. W całości metoda została po raz pierwszy opisana przez Lagrange’a w 1766^[6]. Metoda Lagrange’a wymagała obliczania dwudziestu jeden kolejnych rozwinięć ułamka łańcuchowego pierwiastka z 61, podczas gdy metoda ćakrawala jest znacznie prostsza. Selenius, ocenia metodę ćakrawala, mówiąc:

„Metoda ta jest najkrótszym i najlepiej przybliżającym algorytmem, który, dzięki swoim właściwościom, przy minimalnym wysiłku i bez potrzeby obliczania dużych liczb, podaje najlepsze rozwiązanie równania. Metoda ćakrawala wyprzedziła metody europejskie o ponad tysiąc lat. Żadne europejskie osiągnięcie na polu algebry w czasach późniejszych niż czasy Bhaskary nie może się równać cudownej złożoności i pomysłowości tej metody”^[1][4].

Hermann Hankel nazywa metodę ćakrawala

„najdoskonalszym wynikiem w teorii liczb przez Lagrangem”^[7].

Opis metody

Metoda ćakrawala pozwala rozwiązywać równanie Pella dzięki użyciu tożsamości Brahmagupty:

${\displaystyle (x_{1}^{2}-Ny_{1}^{2})(x_{2}^{2}-Ny_{2}^{2})=(x_{1}x_{2}+Ny_{1}y_{2})^{2}-N(x_{1}y_{2}+x_{2}y_{1})^{2}.}$

Pozwala to „łączyć” (samāsa) dwie trójki ${\displaystyle (x_{1},y_{1},k_{1})}$ i ${\displaystyle (x_{2},y_{2},k_{2})}$ będące rozwiązaniami równania

${\displaystyle x^{2}-Ny^{2}=k,}$

aby wygenerować nową trójkę:

${\displaystyle (x_{1}x_{2}+Ny_{1}y_{2},x_{1}y_{2}+x_{2}y_{1},k_{1}k_{2}).}$

W metodzie ogólnej łączy się dowolną trójkę ${\displaystyle (a,b,k)}$ będącą znanym rozwiązaniem ${\displaystyle a^{2}-Nb^{2}=k}$ z trójką trywialną ${\displaystyle (m,1,m^{2}-N)}$ uzyskując nową trójkę ${\displaystyle (am+Nb,a+bm,k(m^{2}-N))}$ z parametrem ${\displaystyle m.}$ Równanie z nowo uzyskaną trójką dzieli się przez ${\displaystyle k^{2}}$ (przekształcenie to nosi nazwę lematu Bhaskary):

${\displaystyle a^{2}-Nb^{2}=k\Rightarrow \left({\frac {am+Nb}{k}}\right)^{2}-N\left({\frac {a+bm}{k}}\right)^{2}={\frac {m^{2}-N}{k}},}$

lub, ponieważ znaki wyrażeń wewnątrz nawiasów nie grają roli,

${\displaystyle \left({\frac {am+Nb}{|k|}}\right)^{2}-N\left({\frac {a+bm}{|k|}}\right)^{2}={\frac {m^{2}-N}{k}}.}$

Otrzymana nowa trójka liczb niekoniecznie jest całkowita. Jeśli jednak wystartowaliśmy od względnie pierwszych ${\displaystyle a}$ i ${\displaystyle b}$ (tj. takich, że ${\displaystyle NWD(a,b)=1}$) i wybierzemy całkowite ${\displaystyle m}$ tak, aby ${\displaystyle {\frac {a+bm}{k}}}$ było całkowite, to wtedy pozostałe dwa wyrażenia ${\displaystyle {\frac {am+Nb}{k}}}$ i ${\displaystyle {\frac {m^{2}-N}{k}}}$ także będą całkowite.

Ze wszystkich odpowiadających ${\displaystyle m}$ wybiera się takie, aby wartość bezwzględna ${\displaystyle m^{2}-N}$ była najmniejsza. Wtedy trójkę ${\displaystyle (a,b,k)}$ zastępuje się nową trójką uzyskaną z tego równania i cały proces zaczyna się od nowa, aż do momentu uzyskania trójki, dla której ${\displaystyle k=1.}$ Lagrange w 1768 roku udowodnił, że taki algorytm zawsze się zakończy^[8]. Brahmagupta znalazł również rozwiązania w przypadkach, gdy ${\displaystyle k}$ wynosi ±1, ±2, or ±4, na których można zakończyć algorytm.

Przykłady

Znajdźmy w liczbach całkowitych rozwiązanie równania

${\displaystyle x^{2}-7y^{2}=1.}$

W pierwszym kroku znajdujemy znaną trójkę ${\displaystyle (a,b,k)}$ spełniającą równanie ${\displaystyle a^{2}-7b^{2}=k.}$ Zauważmy, że

${\displaystyle 2^{2}-7\cdot 1^{2}=-3.}$

Trójkę (2, 1, -3) łączymy z trójką trywialną, uzyskując:

${\displaystyle \left({\frac {2m_{1}+7}{3}}\right)^{2}-7\cdot \left({\frac {2+m_{1}}{3}}\right)^{2}=-{\frac {m_{1}^{2}-7}{3}}.}$

Wybierając ${\displaystyle m_{1}=1}$ uzyskujemy trójkę ${\displaystyle (3,1,2).}$ Powtarzając algorytm otrzymujemy kolejne równanie:

${\displaystyle \left({\frac {3m_{2}+7}{2}}\right)^{2}-7\cdot \left({\frac {3+m_{2}}{2}}\right)^{2}={\frac {m_{2}^{2}-7}{2}}.}$

Wybierając ${\displaystyle m_{2}=3}$ ostatecznie otrzymujemy trójkę ${\displaystyle (8,3,1),}$ co oznacza, że

${\displaystyle 8^{2}-7\cdot 3^{2}=1.}$

Przypadek ${\displaystyle n=61}$

Znalezienie rozwiązań całkowitych równania

${\displaystyle a^{2}-61b^{2}=1,}$

ustanowione przez Fermata jako wyzwanie, zostało podane przez Bhaksarę jako przykład^[8].

Rozpoczynamy od znalezienia rozwiązania równania

${\displaystyle a^{2}-61b^{2}=k.}$

Przyjmując ${\displaystyle b}$ równe 1, uzyskujemy trójkę ${\displaystyle (8,1,3).}$ Łącząc ją z trójką trywialną ${\displaystyle (m,1,m^{2}-61),}$ otrzymujemy ${\displaystyle (8m+61,8+m,3(m^{2}-61)),}$ która z lematu Bhaskary przekształcana jest do postaci:

${\displaystyle \left({\frac {8m+61}{3}},{\frac {8+m}{3}},{\frac {m^{2}-61}{3}}\right).}$

Aby 3 dzieliło ${\displaystyle 8+m}$ i ${\displaystyle m^{2}-61}$ było najmniejsze, wybieramy ${\displaystyle m=7,}$ uzyskując trójkę ${\displaystyle (39,5,-4).}$ Ponieważ ${\displaystyle k=-4,}$ możemy użyć pomysłu Brahmagupty, dzieląc uzyskaną trójkę przez ${\displaystyle -4,}$ sprowadzając ją do postaci ${\displaystyle \left({\tfrac {39}{2}},\ {\tfrac {5}{2}},\ -1\right),}$ która po połączeniu dwa razy z sobą samą daje ${\displaystyle \left({\tfrac {1523}{2}},\ {\tfrac {195}{2}},\ 1\right),}$ a następnie ${\displaystyle (29\,718,\ 3805,\ -1).}$

W końcu łączy się dwie kopie trójki ${\displaystyle (29\,718,\ 3805,\ -1),}$ otrzymując ${\displaystyle (1\,766\,319\,049,\ 226\,153\,980,\ 1).}$ Jest to najmniejsze rozwiązanie całkowite.

Przypadek ${\displaystyle n=67}$

Przypuśćmy, że chcielibyśmy rozwiązać równanie

${\displaystyle x^{2}-67y^{2}=1}$

dla ${\displaystyle x}$ i ${\displaystyle y}$^[9].

Rozpoczynamy od pewnego rozwiązania równania

${\displaystyle a^{2}-67b^{2}=k.}$

Możemy przyjąć ${\displaystyle b=1,}$ otrzymując

${\displaystyle 8^{2}-67\cdot 1^{2}=-3.}$

W każdym kroku algorytmu znajdziemy ${\displaystyle m>0}$ takie, że ${\displaystyle k}$ dzieli ${\displaystyle a+bm}$ i ${\displaystyle |m^{2}-N|}$ jest najmniejsze, a następnie zastąpimy trójkę ${\displaystyle (a,b,k)}$ przez trójkę

${\displaystyle {\frac {am+Nb}{|k|}},{\frac {a+bm}{|k|}},{\frac {m^{2}-N}{k}}.}$

W pierwszej iteracji otrzymujemy ${\displaystyle (a_{1},b_{1},k_{1})=(8,1,-3).}$ Chcemy znaleźć dodatnie ${\displaystyle m}$ takie, że ${\displaystyle k_{1}}$ dzieli ${\displaystyle a_{1}+mb_{1},}$ tj. 3 dzieli ${\displaystyle 8+m,}$ i ${\displaystyle |m^{2}-67|}$ jest minimalne. Pierwszy warunek mówi, że ${\displaystyle m}$ jest postaci ${\displaystyle 3t+1}$ (np. 1, 4, 7, 10,... itd.), a najmniejsza wartość wyrażenia zachodzi dla ${\displaystyle m=7.}$ Z trójki ${\displaystyle (a_{1},b_{1},k_{1})}$ otrzymujemy nową:

${\displaystyle a_{2}={\frac {(8\cdot 7+67\cdot 1)}{3}}=41,b_{2}={\frac {(8+1\cdot 7)}{3}}=5,k_{2}={\frac {(7^{2}-67)}{(-3)}}=6.}$

Otrzymujemy więc nowe rozwiązanie:

${\displaystyle 41^{2}-67\cdot (5)^{2}=6.}$

Pierwsza część cyklicznego algorytmu jest zakończona.

Druga iteracja

Teraz powtarzamy proces: mamy ${\displaystyle a_{2}=41,b_{2}=5,k_{2}=6.}$ Chcemy znaleźć takie ${\displaystyle m>0,}$ że ${\displaystyle k_{2}}$ dzieli ${\displaystyle a_{2}+mb_{2},}$ tzn. 6 dzieli ${\displaystyle 41+5m,}$ i ${\displaystyle |m^{2}-67|}$ jest minimalne. Pierwszy warunek mówi nam, że ${\displaystyle m}$ jest postaci ${\displaystyle 6t+5}$ (np. 5, 11, 17,...), a wartość ${\displaystyle |m^{2}-67|}$ jest najmniejsza dla ${\displaystyle m=5.}$ W podobny sposób jak poprzednio otrzymujemy nowe rozwiązanie ${\displaystyle (a_{3},b_{3},k_{3})=(90,11,-7)}$ równania:

${\displaystyle 90^{2}-67\cdot 11^{2}=-7.}$

Trzecia iteracja

Aby 7 dzieliło ${\displaystyle 90+11m,}$ musi zachodzić ${\displaystyle m=2+7t(m=2,9,16,\dots ),}$ a z takich ${\displaystyle m,}$ wybieramy ${\displaystyle m=9,}$ otrzymując kolejną trójkę ${\displaystyle (a_{4},b_{4},k_{4})=(221,27,-2)}$ spełniającą równanie

${\displaystyle 221^{2}-67\cdot 27^{2}=-2.}$

Rozwiązanie końcowe

Moglibyśmy powtarzać metodę cykliczną (która zakończyłaby się po siedmiu iteracjach), ale ponieważ prawa strona równania jest równa jednej z liczb ±1, ±2, ±4, możemy użyć obserwacji Brahmagupty: łącząc trójkę ${\displaystyle (221,27,-2)}$ z sobą samą, otrzymujemy

${\displaystyle \left({\frac {221^{2}+67\cdot 27^{2}}{2}}\right)^{2}-67\cdot (221\cdot 27)^{2}=1,}$

czyli rozwiązanie w liczbach całkowitych równania:

${\displaystyle 48\,842^{2}-67\cdot 5967^{2}=1.}$

Dzięki niemu otrzymujemy również przybliżenie

${\displaystyle {\sqrt {67}}\approx {\frac {48\,842}{5967}},}$

z dokładnością rzędu ok. ${\displaystyle 2\times 10^{-9}.}$

Przypisy

1. Hoiberg & Ramchandani – Students’ Britannica India: Bhaskaracharya II, s. 200.
2. Kumar, s. 23.
3. Plofker, s. 474.
4. Goonatilake, s. 127, 128.
5. Cajori (1918), s. 197

   „Metoda dowodzenia zwana „indukcją matematyczną” narodziła się w wielu miejscach jednocześnie. Została znaleziona u Szwajcara Jakuba Bernoulliego, Francuza B. Pascala i P. Fermata i Włocha F. Maurolycusa [...] Jeśli wgłębić się w lekturę można odnaleźć ją wcześniej, w dziełach indyjskich i greckich, między innymi w „cyklicznej metodzie” Bhaskary i w dowodzie Euklidesa o tym, że zbiór liczb pierwszych jest nieskończony.”

   .
6. John J. O’Connor; Edmund F. Robertson: Pell’s equation w MacTutor History of Mathematics archive (ang.)
7. Kaye (1919), s. 337.
8. John Stillwell: Mathematics and its history. Wyd. 2. Springer, 2002, s. 72–76. ISBN 978-0-387-95336-6.
9. Przykład podany w tej sekcji (przy oznaczeniach ${\displaystyle Q_{n}}$ na ${\displaystyle k,}$ ${\displaystyle P_{n}}$ na ${\displaystyle m}$ itd.) można znaleźć w: Michael J. Jacobson, Hugh C. Williams: Solving the Pell equation. Springer, 2009, s. 31. ISBN 978-0-387-84922-5.

Bibliografia

• Florian Cajori (1918), Origin of the Name „Mathematical Induction”, „The American Mathematical Monthly” 25 (5), s. 197–201.
• George Gheverghese Joseph, The Crest of the Peacock: Non-European Roots of Mathematics (1975).
• G.R. Kaye, Indian Mathematics, „Isis” 2:2 (1919), s. 326–356.
• C.O. Selenius, Rationale of the chakravala process of Jayadeva and Bhaskara II, „Historia Mathematica” 2 (1975), s. 167–184.
• C.O. Selenius, Kettenbruch theoretische Erklarung der zyklischen Methode zur Losung der Bhaskara-Pell-Gleichung, „Acta Acad. Abo. Math. Phys.” 23 (10) (1963).
• Hoiberg, Dale & Ramchandani, Indu (2000). Students’ Britannica India. Mumbai: Popular Prakashan. ISBN 0-85229-760-2.
• Goonatilake, Susantha (1998). Toward a Global Science: Mining Civilizational Knowledge. Indiana: Indiana University Press. ISBN 0-253-33388-1.
• Kumar, Narendra (2004). Science in Ancient India. Delhi: Anmol Publications Pvt Ltd. ISBN 81-261-2056-8.
• Ploker, Kim (2007) „Mathematics in India”. The Mathematics of Egypt, Mesopotamia, China, India, and Islam: A Sourcebook New Jersey: Princeton University Press. ISBN 0-691-11485-4.
• Harold Edwards: Fermat’s Last Theorem. Nowy Jork: Springer, 1977. ISBN 0-387-90230-9. Brak numerów stron w książce

Linki zewnętrzne

• Wstęp do metody ćakrawala. www-groups.dcs.st-and.ac.uk. [zarchiwizowane z tego adresu (2011-07-07)]. (ang.)