Lihat sumber bagi Kaedah chakravala

{{BM}}
{{Terjemahan kasar}}
{{Short description| Algoritma kitaran untuk menyelesaikan persamaan kuadratik tak tentu}}
Kaedah '''''chakravala''''' ({{lang-sa|चक्रवाल विधि}}) ialah [[algoritma]] kitaran untuk menyelesaikan [[Persamaan tak tentu|tak tentu]] [[persamaan kuadratik]]s , termasuk [[persamaan Pell]]. Ia biasanya dikaitkan dengan [[Bhāskara II]], (s. 1114 – 1185 CE)<ref name=SBI200>Hoiberg & Ramchandani – Students' Britannica India: Bhaskaracharya II, page 200</ref><ref name=Kumar23>Kumar, page 23</ref> walaupun ada yang mengaitkannya dengan [[Jayadeva (ahli matematik)|Jayadeva]] (s. 950 ~ 1000 CE).<ref name=Plofker474>Plofker, muka surat 474</ref> Jayadeva menegaskan bahawa pendekatan [[Brahmagupta]] untuk menyelesaikan persamaan jenis ini boleh digeneralisasikan, dan dia kemudian menerangkan kaedah umum ini, yang kemudiannya diperhalusi oleh Bhāskara II dalam risalah ''[[Bijaganita]]''nya. Dia memanggilnya kaedah Chakravala: ''chakra'' bermaksud "roda" dalam [[Sanskrit]], merujuk kepada sifat kitaran algoritma.<ref name= Goonatilake127>Goonatilake, page 127 &ndash; 128</ref> C.-O. Selenius berpendapat bahawa tiada persembahan Eropah pada masa Bhāskara, dan tidak lama kemudian, melebihi ketinggian kerumitan matematiknya yang mengagumkan.<ref name=SBI200/><ref name= Goonatilake127/>

Kaedah ini juga dikenali sebagai '''kaedah kitaran''' dan mengandungi kesan [[aruhan matematik]].<ref>Cajori (1918), ms. 197<blockquote>" Proses penaakulan yang dipanggil "Induksi Matematik" mempunyai beberapa asal usul bebas. Ia telah dikesan kembali kepada Jakob (James) Bernoulli dari Switzerland, warga Perancis B. Pascal dan P. Fermat, dan F. Maurolycus dari Itali. [...] Dengan membaca sedikit di antara baris seseorang boleh menemui jejak aruhan matematik yang masih lebih awal, dalam tulisan orang Hindu dan Yunani, seperti, misalnya, dalam "kaedah kitaran" Bhaskara, dan dalam bukti Euclid bahawa bilangan prima adalah tidak terhingga."</blockquote></ref>

== Sejarah ==
''Chakra'' dalam bahasa Sanskrit bermaksud kitaran. Mengikut legenda popular, Chakravala menunjukkan rangkaian mitos gunung yang mengelilingi bumi seperti dinding dan tidak dihadkan oleh cahaya dan kegelapan.<ref name=Madan>{{cite book|title=India through the ages|url=https://archive.org/details/indiathroughages00mada|last=Gopal|first=Madan|year= 1990| page= [https://archive.org/details/indiathroughages00mada/page/79 79]|editor=K.S. Gautam|publisher=Publication Division, Ministry of Information and Broadcasting, Government of India}}</ref>

[[Brahmagupta]] pada 628 CE mengkaji persamaan kuadratik tak tentu, termasuk [[persamaan Pell]]

:<math>\,x^2 = Ny^2 + 1,</math>

untuk integer minimum ''x'' dan ''y''. Brahmagupta boleh menyelesaikannya untuk beberapa ''N'', tetapi bukan semua.

Jayadeva (abad ke-9) dan Bhaskara (abad ke-12) menawarkan penyelesaian lengkap pertama untuk persamaan, menggunakan kaedah ''chakravala'' untuk mencari <math>\,x^2 = 61y^2 + 1,</math> penyelesaiannya

:<math>\,x = 1 766 319 049, y = 226 153 980.</math>

Kes ini terkenal dengan kesukarannya, dan pertama kali diselesaikan di [[Eropah]] oleh [[William Brouncker, 2nd Viscount Brouncker|Brouncker]] pada 1657–58 sebagai tindak balas kepada cabaran oleh [[Pierre de Fermat|Fermat]] , menggunakan pecahan bersambung. Kaedah untuk masalah umum pertama kali diterangkan sepenuhnya oleh [[Lagrange]] pada tahun 1766.<ref>{{MacTutor|class=HistTopics|id=Pell|title=Pell's equation}}</ref> Kaedah Lagrange, walau bagaimanapun, memerlukan pengiraan 21 penumpuan berturut-turut bagi [[pecahan bersambung]] untuk [[punca kuasa dua]] daripada 61, manakala kaedah ''chakravala'' adalah lebih mudah. Selenius, dalam penilaiannya tentang kaedah "chakravala", menyatakan

: "Kaedah ini mewakili algoritma penghampiran terbaik dengan panjang minimum yang, disebabkan oleh beberapa sifat pengecilan, dengan usaha yang minimum dan mengelakkan bilangan besar secara automatik menghasilkan penyelesaian terbaik kepada persamaan. Kaedah ''chakravala'' menjangkakan kaedah Eropah dengan lebih daripada seribu tahun. Tetapi tiada persembahan Eropah dalam keseluruhan bidang [[algebra]] pada satu masa lebih lewat daripada Bhaskara, bahkan hampir menyamai zaman kita, menyamai kerumitan dan kepintaran yang menakjubkan dari ''chakravala''."<ref name=SBI200/><ref name= Goonatilake127/>

[[Hermann Hankel]] memanggil kaedah ''chakravala''
: "perkara terbaik yang dicapai dalam teori nombor sebelum Lagrange."<ref>Kaye (1919), p. 337.</ref>

==Kaedahnya==
Daripada [[pengenalan Brahmagupta]], kita perhatikan bahawa untuk diberikan ''N'',

:<math>(x_1x_2 + Ny_1y_2)^2 - N(x_1y_2 + x_2y_1)^2 = (x_1^2 - Ny_1^2)(x_2^2 - Ny_2^2)</math>

Untuk persamaan <math>x^2 - Ny^2 = k</math>, ini membenarkan "komposisi" (''samāsa'') dua penyelesaian tiga kali ganda <math>(x_1, y_1, k_1)</math > dan <math>(x_2, y_2, k_2)</math> menjadi tiga kali ganda baru

:<math>(x_1x_2 + Ny_1y_2 \,,\, x_1y_2 + x_2y_1 \,,\, k_1k_2).</math>

Dalam kaedah umum, idea utama ialah mana-mana tiga <math>(a,b,k)</math> (iaitu, satu yang memenuhi <math>a^2 - Nb^2 = k</math>) boleh digubah dengan tiga kali ganda <math>(m, 1, m^2 - N)</math> untuk mendapatkan tiga kali ganda <math>(am + Nb, a+bm, k(m^2-N) )</math> untuk sebarang ''m''. Dengan mengandaikan kita bermula dengan tiga kali ganda yang <math>\gcd(a,b)=1</math>, ini boleh dikecilkan dengan ''k'' (ini ialah [[lemma Bhaskara]]):

:<math>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}</math>

Oleh kerana tanda-tanda di dalam petak tidak penting, penggantian berikut adalah mungkin:

:<math>a\leftarrow\frac{am+Nb}{|k|}, b\leftarrow\frac{a+bm}{|k|}, k\leftarrow\frac{m^2-N}{k}</math>

Apabila integer positif ''m'' dipilih supaya (''a''&nbsp;+&nbsp;''bm'')/''k'' ialah integer, begitu juga dengan dua nombor lain dalam rangkap tiga. Di antara ''m'' itu, kaedah memilih kaedah yang meminimumkan nilai mutlak ''m''<sup>2</sup>&nbsp;&minus;&nbsp;''N'' dan oleh itu daripada (''m''<sup>2</sup>&nbsp;&minus;&nbsp;''N'')/''k''. Kemudian hubungan penggantian digunakan untuk ''m'' sama dengan nilai yang dipilih. Ini menghasilkan tiga kali ganda baharu (''a'', ''b'', ''k''). Proses ini diulang sehingga tiga kali ganda dengan <math>k=1</math> ditemui. Kaedah ini sentiasa ditamatkan dengan penyelesaian (dibuktikan oleh Lagrange pada tahun 1768).<ref name=stillwell>{{citation | year=2002 | title = Mathematics and its history | author1=John Stillwell | author-link=John Stillwell | edition=2 | publisher=Springer | isbn=978-0-387-95336-6 | pages=72–76 | url=https://books.google.com/books?id=WNjRrqTm62QC&pg=PA72}}</ref>
Secara pilihan, kita boleh berhenti apabila ''k'' ialah ±1, ±2, atau ±4, kerana pendekatan Brahmagupta memberikan penyelesaian untuk kes tersebut.

== Kaedah gubahan Brahmagupta ==
Pada tahun 628 Masihi, Brahmagupta menemui cara umum untuk mencari <math>x</math> dan <math>y</math> bagi <math>x^2 = Ny^2 + 1,</math> apabila diberi <math >a^2 = Nb^2 + k</math>, apabila k ialah ±1, ±2, atau ±4.<ref>{{Cite web|title=Pell's equation|url=https://mathshistory.st-andrews.ac.uk/HistTopics/Pell/|access-date=2021-06-14|website=Maths History|language=en}}</ref> 

=== k = -1 ===
Menggunakan [[pengenalan Brahmagupta]], untuk mengarang tiga <math>(a,b,k)</math> dengan dirinya sendiri:
<math>(a^2+Nb^2)^2-N(2ab)^2=k^2</math> <math>\Rightarrow</math> <math>(2a^2-k)^2-N(2ab)^2=k^2</math>

Tiga kali ganda baharu boleh dinyatakan sebagai <math>(2a^2-k,2ab,k^2)</math>. Menggantikan <math>k=-1</math> untuk mendapatkan penyelesaian:

<math>x=2a^2+1, 
y=2ab</math>

=== k = ±2 ===
Sekali lagi menggunakan persamaan,<math>(2a^2-k)^2-N(2ab)^2=k^2</math><math>\Rightarrow</math><math> \left( \frac{2a^2-k}{k} \right)^2-N \left (\frac{2ab}{k} \right)^2=1</math>

Menggantikan <math>k=2</math>,

<math>x=a^2-1, 
y=ab</math>

Menggantikan <math>k=-2</math>,

<math>x=a^2+1, 
y=ab</math>

=== k = 4 ===
Menggantikan <math>k=4</math> ke dalam persamaan <math>(\frac{2a^2-4}{4})^2-N(\frac{2ab}{4})^2=1</math> mencipta tiga kali ganda <math>(\frac{a^2-2}{2},\frac{ab}{2},1)</math>.

Manakah penyelesaian jika <math>a</math> genap:

<math>x=\frac{a^2-2}{2},
y=\frac{ab}{2}
</math>

Jika a ganjil, mulakan dengan persamaan <math>(\frac{a}{2})^2-N(\frac{b}{2})^2=1</math> dan <math>(\ frac{2a^2-4}{4})^2-N(\frac{2ab}{4})^2=1</math>.

Membawa kepada tiga kali ganda <math>(\frac{a}{2},\frac{b}{2},1)</math> dan <math>(\frac{a^2-2}{2},\frac{ab}{2},1)</math>. Mengarang tiga kali ganda memberi <math>(\frac{a}{2}(a^2-3))^2-N(\frac{b}{2}(a^2-1))^2=1</math>

Apabila <math>a</math> ganjil,

<math>x=\frac{a}{2}(a^2-3))^2,
y=(\frac{b}{2}(a^2-1))^2</math>

=== k = -4 ===
Apabila <math>k=-4</math>, then <math>(\frac{a}{2})^2-N(\frac{b}{2})^2=-1</math>. Mengarang dengan sendiri membuahkan hasil <math>(\frac{a^2+Nb^2}{4})^2-N(\frac{ab}{2})^2=1</math><math>\Rightarrow</math><math>(\frac{a^2+2}{2})^2-N(\frac{ab}{2})^2=1</math>.

Sekali lagi mengarang sendiri membuahkan hasil <math>(\frac{(a^2+2)^2+Na^2b^2)}{4})^2-N(\frac{ab(a^2+2)}{2})^2=1</math><math>\Rightarrow</math> <math>(\frac{a^4+4a^2+2}{2})^2-N(\frac{ab(a^2+2)}{2})^2=1</math>

Akhir sekali, daripada persamaan terdahulu, susun tiga kali ganda <math>(\frac{a^2+2}{2},\frac{ab}{2},1)</math> dan <math>(\frac{a^4+4a^2+2}{2},\frac{ab(a^2+2)}{2},1)</math>, untuk mendapatkan
<math>(\frac{(a^2+2)(a^4+4a^2+2)+Na^2b^2 (a^2+2)}{4})^2-N(\frac{ab(a^4+4a^2+3)}{2})^2=1</math><math>\Rightarrow</math><math>(\frac{(a^2+2)(a^4+4a^2+1)}{2})^2-N(\frac{ab(a^2+3)(a^2+1)}{2})^2=1</math><math>\Rightarrow</math><math>(\frac{(a^2+2)[(a^2+1)(a^2+3)-2)]}{2})^2-N(\frac{ab(a^2+3)(a^2+1)}{2})^2=1</math>. 

Ini memberi kita penyelesaian

<math>x=\frac{(a^2+2)[(a^2+1)(a^2+3)-2)]}{2}
y=\frac{ab(a^2+3)(a^2+1)}{2}</math><ref>{{Cite book|last=Datta and Singh|title=History of Hindu Mathematics : A Source Book Parts I and II|publisher=Asia Publishing House|year=1962|isbn=8180903907|pages=157–160}}</ref>

(Note, <math>k=-4</math> berguna untuk mencari penyelesaian kepada [[Persamaan Pell|Persamaan Pell]], tetapi ia bukan selalunya pasangan integer terkecil. cth. <math>36^2-52*5^2=-4</math>. Persamaan akan memberi anda <math>x=1093436498,y=151632270</math>, yang apabila dimasukkan ke dalam Persamaan Pell menghasilkan <math>1195601955878350801-1195601955878350800 = 1</math>, yang berfungsi, tetapi begitu juga <math>x = 649,y=90</math> untuk <math>N=52</math>.

==Contoh ==
===''n'' = 61===
Kes ''n''&nbsp;=&nbsp;61 (menentukan penyelesaian integer yang memuaskan <math>a^2 - 61b^2 = 1</math>), dikeluarkan sebagai cabaran oleh Fermat berabad-abad kemudian, telah diberikan oleh Bhaskara sebagai contoh.<ref name=stillwell/>

Kita mulakan dengan penyelesaian <math>a^2 - 61b^2 = k</math> untuk sebarang ''k'' yang ditemui dengan apa-apa cara. Dalam kes ini kita boleh membiarkan ''b'' menjadi 1, oleh itu, oleh kerana <math>8^2 - 61\cdot1^2 = 3</math>, kita mempunyai tiga kali ganda <math>(a,b,k) = (8, 1, 3)</math>. Mengarangnya dengan <math>(m, 1, m^2-61)</math> memberikan tiga kali ganda <math>(8m+61, 8+m, 3(m^2-61))</math>, yang dikecilkan (atau [[lemma Bhaskara]] digunakan secara langsung) untuk mendapatkan:
: <math>\left( \frac{8m+61}{3}, \frac{8+m}{3}, \frac{m^2-61}{3} \right).</math>

Untuk 3 membahagikan <math>8+m</math> dan <math>|m^2-61|</math> menjadi minimum, kami memilih <math>m=7</math>, supaya kami mempunyai tiga kali ganda <matematik>(39, 5, -4)</math>. Memandangkan ''k'' ialah &tolak;4, kita boleh menggunakan idea Brahmagupta: ia boleh dikecilkan kepada penyelesaian rasional <math>(39/2, 5/2, -1)\,</math>, yang digubah dengan dirinya sendiri tiga kali, dengan masing-masing <math>m={7,11,9}</math>, apabila k menjadi segi empat sama dan penskalaan boleh digunakan, ini memberikan <math>(1523/2, 195/2, 1 )\,</math>. Akhir sekali, prosedur sedemikian boleh diulang sehingga penyelesaian ditemui (memerlukan 9 gubahan diri tambahan dan 4 skala persegi tambahan): <math>(1766319049,\, 226153980,\, 1)</math>. Ini ialah penyelesaian integer minimum.

===''n'' = 67===
Katakan kita hendak menyelesaikan <math>x^2 - 67y^2 = 1</math> untuk ''x'' dan ''y''.<ref>Contoh dalam bahagian ini diberikan (dengan tatatanda <math> Q_n</math> untuk ''k'', <math>P_n</math> untuk ''m'', dsb.) dalam:{{citation | year=2009 | title = Solving the Pell equation | author1=Michael J. Jacobson | author2=Hugh C. Williams | publisher=Springer | isbn=978-0-387-84922-5 | page=31 | url=https://books.google.com/books?id=2INzqrEUGzAC&pg=PA31}}</ref>

Kita mulakan dengan penyelesaian <math>a^2 - 67b^2 = k</math> untuk sebarang ''k'' yang ditemui dengan sebarang cara; dalam kes ini kita boleh membiarkan ''b'' menjadi 1, dengan itu menghasilkan <math>8^2 - 67\cdot1^2 = -3</math>. Pada setiap langkah, kami menemui ''m''&nbsp;>&nbsp;0 sedemikian rupa sehingga ''k'' membahagikan ''a''&nbsp;+&nbsp;''bm'' dan |''m''< sup>2</sup>&nbsp;&tolak;&nbsp;67| adalah minimum. Kami kemudian mengemas kini ''a'', ''b'' dan ''k'' kepada <math>\frac{am+Nb}{|k|}, \frac{a+bm}{|k|} </math> dan <math>\frac{m^2-N}{k}</math> masing-masing.

;Lelaran pertama
Kami mempunyai <math>(a,b,k) = (8,1,-3)</math>. Kami mahukan integer positif ''m'' supaya ''k'' membahagi ''a''&nbsp;+&nbsp;''bm'', iaitu 3 bahagi 8 + m dan |''m''<sup >2</sup>&nbsp;&tolak;&nbsp;67| adalah minimum. Syarat pertama membayangkan bahawa ''m'' adalah dalam bentuk 3''t'' + 1 (iaitu 1, 4, 7, 10,… dll.), dan di antara ''m'' itu, nilai minimum ialah dicapai untuk ''m'' = 7. Menggantikan (''a'',&nbsp;''b'',&nbsp;''k'') dengan <math>\left(\frac{am+Nb}{| k|}, \frac{a+bm}{|k|}, \frac{m^2-N}{k}\right)</math>, kita mendapat nilai baharu <math>a = (8\ cdot7+67\cdot1)/3 = 41, b = (8 + 1\cdot7)/3 = 5, k = (7^2-67)/(-3) = 6</math>. Iaitu, kami mempunyai penyelesaian baharu:
: <math>41^2 - 67\cdot(5)^2 = 6.</math>

Pada ketika ini, satu pusingan algoritma kitaran selesai.

;Lelaran kedua
Kami kini mengulangi proses itu. Kami mempunyai <math>(a,b,k) = (41,5,6)</math>. Kami mahukan ''m''&nbsp;>&nbsp;0 supaya ''k'' membahagikan ''a''&nbsp;+&nbsp;''bm'', iaitu 6 bahagi 41&nbsp;+&nbsp;5''m '' dan |''m''<sup>2</sup>&nbsp;&minus;&nbsp;67| adalah minimum. Syarat pertama membayangkan bahawa ''m'' adalah dalam bentuk 6''t''&nbsp;+&nbsp;5 (iaitu 5, 11, 17,… dsb.), dan antara ''m'' itu, |''m''<sup>2</sup>&nbsp;&minus;&nbsp;67| adalah minimum untuk ''m''&nbsp;=&nbsp;5. Ini membawa kepada penyelesaian baharu ''a''&nbsp;=&nbsp;(41⋅5&nbsp;+&nbsp;67⋅5)/6, dsb.:
:<math>90^2 - 67 \cdot 11^2 = -7.</math>

;Lelaran ketiga
Untuk 7 membahagi 90 + 11''m'', kita mesti mempunyai ''m'' = 2&nbsp;+&nbsp;7''t'' (iaitu 2, 9, 16,… dsb.) dan antara '' m'', kita pilih ''m'' = 9.

:<math>221^2 - 67\cdot 27^2 = -2.</math>

;Penyelesaian muktamad
Pada ketika ini, kita boleh meneruskan kaedah kitaran (dan ia akan berakhir, selepas tujuh lelaran), tetapi memandangkan sebelah kanan adalah antara ±1, ±2, ±4, kita juga boleh menggunakan pemerhatian Brahmagupta secara langsung. Mengarang tiga kali ganda (221, 27, &tolak;2) dengan dirinya sendiri, kita dapat
:<math> \left(\frac{221^2 + 67\cdot27^2}{2}\right)^2 - 67\cdot(221\cdot27)^2 = 1,</math>

iaitu, kita mempunyai penyelesaian integer:
:<math> 48842^2 - 67 \cdot 5967^2 = 1.</math>

Persamaan ini menghampiri <math>\sqrt{67}</math> sebagai <math> \frac{48842}{5967}</math> dalam jidar kira-kira <math> 2 \times 10^{-9}</math>.

==Nota==
{{Reflist}}

==Rujukan==
*[[Florian Cajori]] (1918), Origin of the Name "Mathematical Induction", ''[[The American Mathematical Monthly]]'' '''25''' (5), p.&nbsp;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), p.&nbsp;326–356.
*Clas-Olaf Selenius, [http://www.msc.uky.edu/sohum/ma330/files/Rationale-of-the-chakrav-la-process-of-Jayadeva-and-Bh-skara-II_1975_Historia-Mathematica.pdf "Rationale of the chakravala process of Jayadeva and Bhaskara II"], ''Historia Mathematica'' '''2''' (1975), pp.&nbsp;167–184.
*Clas-Olaf Selenius, "Kettenbruchtheoretische Erklärung der zyklischen Methode zur Lösung der Bhaskara-Pell-Gleichung", ''Acta Acad. Abo. Math. Phys.'' '''23''' (10) (1963), pp.&nbsp;1–44.
*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}}
*{{cite book
  | last = Edwards
  | first = Harold
  | title = Fermat's Last Theorem
  | publisher = [[Springer Science+Business Media|Springer]]
  | location = New York
  | date = 1977
  | isbn = 0-387-90230-9}}

==Pautan luar==
*[https://web.archive.org/web/20110707120031/http://www-groups.dcs.st-and.ac.uk/~history/Miscellaneous/Pearce/Lectures/Ch8_6.html Introduction to chakravala]

{{number theoretic algorithms}}

[[Kategori:Brahmagupta]]
[[Kategori:Persamaan Diophantine]]
[[Kategori:Algoritma teori nombor]]
[[Kategori:Matematik India]]