Metoda Chakravala

Metoda chakravala ( Skt. चक्रवाल विधि ) este un algoritm iterativ pentru rezolvarea unor ecuații patratice incerte , inclusiv Ecuația Pell . De obicei metoda este atribuită lui Bhaskara II , (1114 - 1185) [1] [2] , deși unii atribuie autorul lui Jayadeva (950 ~ 1000 d.Hr.) [3] . Jayadeva a subliniat că abordarea lui Brahmagupta pentru rezolvarea ecuațiilor de acest tip poate fi generalizată și a descris această metodă de generalizare. Metoda a fost dezvoltată mai târziu de Bhaskara II în tratatul său Bijaganita ( Algebra ). El a numit această metodă „chakravala” – chakra în sanscrită înseamnă „roată”, ceea ce indică natura ciclică a algoritmului [4] . Selenius [5] este de părere că niciun european la vremea lui Bhaskar și în vremurile de mai târziu nu a atins o înălțime atât de uimitoare de complexitate matematică [1] [4] .

Metoda este cunoscută și ca metoda ciclică și conține urme de inducție matematică [6] .

Istorie

Chakra în sanscrită înseamnă ciclu. În cosmografia budistă, universul este format din nenumărate sfere ( chakraval ), fiecare dintre ele având propriul pământ, propriul soare, propria sa lună, ceruri și iaduri și este împărțită în trei regiuni, sau avachara [7]

Brahmagupta în 628 d.Hr a studiat ecuații pătratice nedefinite, inclusiv ecuația lui Pell

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

pentru numerele întregi minime x și y . Brahmagupta a reușit să rezolve ecuația pentru unele N , dar nu pentru toate.

Jayadeva (secolul al IX-lea) și Bhaskara (secolul al XII-lea) au propus o soluție completă a ecuației, folosind metoda chakravala pentru a găsi soluția pentru $\,x^{2}=61y^{2}+1$

\,x=1766319049,y=226153980.

Cazul a fost renumit pentru dificultatea sa și a fost rezolvat pentru prima dată în Europa de Brauncker în 1657–58, ca răspuns la provocarea lui Fermat . Braunker a folosit fracții continue pentru a rezolva. Metoda pentru rezolvarea completă a problemei a fost descrisă pentru prima dată strict de Lagrange în 1766 [8] . Metoda Lagrange, totuși, necesită calculul a 21 de fracții parțiale continuate ale rădăcinii pătrate a lui 61, în timp ce metoda Chakravala este mult mai simplă. Selenius, în recenzia sa despre metoda chakravala , afirmă

„Metoda reprezintă cel mai bun algoritm de aproximare a lungimii minime, care, datorită unor proprietăți de minimizare, cu cel mai mic efort și fără numere mari, dă automat cea mai bună soluție ecuației. Metoda chakravala a apărut cu o mie de ani înaintea metodelor europene. Dar succesul europenilor în toată algebra în vremuri ulterioare timpului lui Bhaskar nu a fost atât de remarcabil, în comparație cu complexitatea și originalitatea uimitoare a metodei chakravala [1] [4] ”

Herman Gankel a numit metoda chakravala

„cel mai bun care a fost realizat în teoria numerelor înainte de Lagrange” [9] .

Metoda

Din identitatea Brahmagupta , vedem că pentru un N dat ,

(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}

Pentru o ecuație, aceasta vă permite să „combinați” două triple de soluție și într-un nou triplu $x^{2}-Ny^{2}=k$ $(x_{1},y_{1},k_{1})$ $(x_{2},y_{2},k_{2})$

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

Ideea principală a metodei este că orice triplu (care satisface ecuația ) poate fi combinat cu un triplu trivial (pentru orice m ) pentru a da un nou triplu . Presupunând că începem cu un triplu pentru care mcd( a , b )=1, ultimul triplu poate fi micșorat cu k (aceasta este lema lui Bhaskara ): $(a,b,k)$ $a^{2}-Nb^{2}=k$ $(m,1,m^{2}-N)$ $(am+Nb,a+bm,k(m^{2}-N))$

a^{2}-Nb^{2}=k\săgeată la dreapta \left({\frac {am+Nb}{k))\right)^{2}-N\left({\frac {a +bm}{k}}\right)^{2}={\frac {m^{2}-N}{k}}

Deoarece caracterele din paranteze nu au sens, sunt posibile următoarele înlocuiri:

a\leftarrow {\frac {am+Nb}{|k|}},b\leftarrow {\frac {a+bm}{|k|}},k\leftarrow {\frac {m^{2 }-N}{k}}

Când un număr pozitiv m este ales astfel încât ( a + bm )/ k este un număr întreg, atunci celelalte două numere din triplu vor fi, de asemenea, numere întregi. Dintre valorile posibile ale lui m , metoda o alege pe cea care minimizează valoarea absolută a lui m 2 − N , și deci valoarea lui ( m 2 − N )/ k . Apoi efectuăm o înlocuire cu valoarea aleasă a lui m , ceea ce duce la triplul ( a , b , k ). Procesul se repetă până când se găsește triplul c. Această metodă se termină întotdeauna cu o soluție (demonstrată de Lagrange în 1768) [10] . Putem încheia procesul când k este ±1, ±2 sau ±4, unde abordarea lui Brahmagupta dă soluția. $k=1$

Exemple

n = 61

Cazul n = 61 (căutarea unei soluții pentru ecuația ), care a fost provocarea lui Fermat multe secole mai târziu, a fost dat de Bhaskara ca exemplu [10] . $a^{2}-61b^{2}=1$

Începem cu o soluție pentru orice k , găsită într-un mod arbitrar. Putem lua b ca fiind 1, iar din moment ce , obținem un triplu . Îl combinăm cu triplul , care dă , și după reducere (conform lemei lui Bhaskara ) $a^{2}-61b^{2}=k$ $8^{2}-61\cdot 1^{2}=3$ $(a,b,k)=(8,1,3)$ $(m,1,m^{2}-61)$ $(8m+61,8+m,3(m^{2}-61))$

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

Pentru ca 3 să împartă , și să fie minim, alegem , așa că obținem un triplu . Acum avem k = −4 și putem folosi ideea lui Brahmagupta - triplul poate fi redus la o soluție rațională , care este apoi combinată cu ea însăși de trei ori , respectiv, c , până când k devine un pătrat și putem reduce. Aceasta dă . Această procedură se poate repeta până când avem o soluție (necesită 9 combinații suplimentare și 4 reduceri pătratice suplimentare) . Aceasta este soluția întregului minim. $8+m$ $|m^{2}-61|$ $m=7$ $(39,5,-4)$ $(39/2,5/2,-1)\,$ $m={7,11,9}$ $(1523/2.195/2.1)$ $(1766319049,\,226153980,\,1)$

n = 67

Să fie necesară rezolvarea ecuației [11] $x^{2}-67y^{2}=1$

Începem prin a rezolva ecuația pentru k , găsită în orice fel. Putem lua b egal cu 1, ceea ce dă . La fiecare iterație găsim m > 0 astfel încât k împarte a + bm și | m 2 − 67| minim. Apoi actualizăm a , b și k cu . $a^{2}-67b^{2}=k$ $8^{2}-67\cdot 1^{2}=-3$ ${\frac {am+Nb}{|k|}},{\frac {a+bm}{|k|}},{\frac {m^{2}-N}{k}}$

Prima iterație

Avem . Avem nevoie de un întreg pozitiv m astfel încât k să împartă a + bm , deci 3 să împartă 8 + m. Avem nevoie și de valoarea | m 2 − 67| a fost minim. Din prima condiție rezultă că m are forma 3 t + 1 (adică m = 1, 4, 7, 10,…, etc.), iar dintre astfel de valori ale lui m , valoarea minimă se obține la m = 7. Înlocuind ( a , b , k ) cu , obținem noi valori . Adică avem o nouă soluție $(a,b,k)=(8,1,-3)$ $\left({\frac {am+Nb}{|k|}},{\frac {a+bm}{|k|}},{\frac {m^{2}-N}{k }}\dreapta)$ $a=(8\cdot 7+67\cdot 1)/3=41,b=(8+1\cdot 7)/3=5,k=(7^{2}-67)/(- 3)=6$

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

A doua iterație

Repetăm procesul. Avem . Avem nevoie de m > 0 astfel încât k să împartă a + bm , deci 6 să împartă 41 + 5 m . În același timp, avem nevoie de | | m 2 − 67| a fost minim. Din prima condiție rezultă că m are forma 6 t + 5 (adică m = 5, 11, 17,…, etc.), iar dintre astfel de numere, m este cel puțin | m 2 − 67| se ajunge la m = 5. Aceasta ne conduce la o nouă soluție a = (41⋅5 + 67⋅5)/6 și așa mai departe: $(a,b,k)=(41,5,6)$

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

A treia iterație

Pentru ca 7 să împartă 90 + 11 m , m trebuie să aibă forma m = 2 + 7 t (adică 2, 9, 16,... etc.). Dintre astfel de m alegem m = 9.

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

Soluție finală

Putem continua să repetăm (și să terminăm după șapte iterații), dar deoarece partea dreaptă este printre numerele ±1, ±2, ±4, putem folosi direct observația lui Brahmagupta. Combinați triplul (221, 27, −2) cu el însuși, obținem

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

Adică avem toată soluția:

48842^{2}-67\cdot 5967^{2}=1.

Această soluție este o aproximare în forma în care eroarea este în . ${\sqrt {67}}$ ${\frac {48842}{5967}}$ $10^{{-9}}$

Note

↑ 1 2 3 Enciclopedia Britannica (India), 2000 , p. 200.
↑ Kumar, 2004 , p. 23.
↑ Plofker, 2007 , p. 474.
↑ 1 2 3 Goonatilake, 1998 , p. 127-128.
↑ Selenius, 1975 , p. 167-184.
↑ Cajori, 1918
„Raționamentul numit „inducție matematică” a avut mai multe surse independente. Aceștia pot fi urmăriți în profunzime până la elvețianul Jacob Bernoulli, francezul B. Pascal și P. Fermat, italianul F. Mavrolik. [...] Dacă citești puțin printre rânduri, poți găsi urme de inducție matematică mult mai devreme, în lucrările hindușilor și grecilor, ca, de exemplu, în „metoda ciclică” a lui Bhaskar și în dovada lui Euclid că numărul de numere prime este infinită.
↑ Dicţionar enciclopedic F.A Brockhaus și I.A. Efron. - Sankt Petersburg: Brockhaus-Efron 1890-1907
↑ John J. O'Connor, Edmund F. Robertson; „Ecuația lui Pell” arhiva MacTutor History of Mathematics , Universitatea din St Andrews
↑ Kaye, 1919 , p. 337.
↑ 12 Stillwell , 2002 , p. 72–76.
↑ Exemplu preluat din cartea (cu notație pentru k , pentru m , etc.) de Jacobson și Williams ( Jacobson, Williams 2009 ) $Q_{n}$ $P_{n}$

Literatură

Dale Hoiberg, Indu Ramchandani. Bhaskaracharya II // Students' Britannica India. - New Delhi: Encyclopedia Britannica (India), 2000. - V. 1 (A - C).
Florian Cajori . Originea numelui „Inducție matematică” // The American Mathematical Monthly . - 1918. - T. 25 , nr. 5 . - S. 197-201 .
George Gheverghese Joseph. Cresta păunului: rădăcini non-europene ale matematicii . — al 3-lea. - Princeton University Press, 1991. - ISBN 9780691135267 .
GR Kaye. Matematică indiană // Isis. - 1919. - Vol. 2 , numărul. 2 . — S. 326–356 .
C.-O. Selenius. Rațiunea procesului chakravala al lui Jayadeva și Bhaskara II // Historia Mathematica. - 1975. - Emisiune. 2 . — S. 167-184 .
C.-O. Selenius. Kettenbruch theoretische Erklarung der zyklischen Methode zur Losung der Bhaskara-Pell-Gleichung // Acta Acad. Abo. Matematică. Fiz. - 1963. - T. 23 , nr. 10 .
Susantha Goonatilake. Către o știință globală: cunoștințe civilizaționale miniere . - Indiana: Indiana University Press, 1998. - ISBN 0-253-33388-1 .
Narendra Kumar. Știința în India antică. - Delhi: Anmol Publications Pvt Ltd, 2004. - ISBN 81-261-2056-8 .
Kim Ploker. Matematica în India // Matematica Egiptului, Mesopotamiei, Chinei, Indiei și Islamului: O sursă . - New Jersey: Princeton University Press, 2007. - ISBN 0-691-11485-4 .
Harold Edwards. Ultima teoremă a lui Fermat. - New York: Springer , 1977. - ISBN 0-387-90230-9 .
John Stillwell. Matematica și istoria ei . - 2. - Springer, 2002. - S. 72–76. — ISBN 978-0-387-95336-6 .
Michael J. Jacobson, Hugh C. Williams. Rezolvarea ecuației Pell . - Springer, 2009. - P. 31. - ISBN 978-0-387-84922-5 .

Link -uri

Introducere în chakravala Arhivat 7 iulie 2011 la Wayback Machine

Algoritmi teoretici numerelor
Teste de simplitate	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Saxonia Privighetoarea - Strassen
Găsirea numerelor prime	Iterarea peste divizori Sita lui Eratosthenes sita lui Atkin Sieve Sundarama
Factorizarea	Iterarea peste divizori Metoda Fermat p −1 Metoda Pollard Algoritmul ρ al lui Pollard metoda Lehmann Metoda curbei eliptice (algoritmul lui Lenstra) algoritmul lui Dixon Sita pătrată
Logaritm discret	Algoritmul Gelfond-Shanks Algoritmul Polig-Hellman Metoda ρ a lui Pollard Algoritmul Cangurului lui Pollard Algoritmul lui Adleman Algoritmul COS
Găsirea GCD	algoritmul lui Euclid Algoritm avansat Algoritm binar
Modul de aritmetică	Algoritmul lui Montgomery Teorema chineză a restului
Înmulțirea și împărțirea numerelor	Algoritmul Karatsuba Algoritmul Toom-Cook Algoritmul Schönhage-Strassen Algoritmul Fuhrer Algoritmul Harvey-van der Hoeven Algoritmul Burnickel-Ziegler
Calcularea rădăcinii pătrate	Algoritmul Tonelli-Shanks Algoritmul Berlekamp-Rabin