Kaedah chakravala

Kaedah chakravala (Sanskrit: चक्रवाल विधि) ialah algoritma kitaran untuk menyelesaikan tak tentu persamaan kuadratiks , termasuk persamaan Pell. Ia biasanya dikaitkan dengan Bhāskara II, (s. 1114 – 1185 CE)^[1][2] walaupun ada yang mengaitkannya dengan Jayadeva (s. 950 ~ 1000 CE).^[3] 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 Bijaganitanya. Dia memanggilnya kaedah Chakravala: chakra bermaksud "roda" dalam Sanskrit, merujuk kepada sifat kitaran algoritma.^[4] C.-O. Selenius berpendapat bahawa tiada persembahan Eropah pada masa Bhāskara, dan tidak lama kemudian, melebihi ketinggian kerumitan matematiknya yang mengagumkan.^[1][4]

Kaedah ini juga dikenali sebagai kaedah kitaran dan mengandungi kesan aruhan matematik.^[5]

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.^[6]

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

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

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 ${\displaystyle \,x^{2}=61y^{2}+1,}$ penyelesaiannya

${\displaystyle \,x=1766319049,y=226153980.}$

Kes ini terkenal dengan kesukarannya, dan pertama kali diselesaikan di Eropah oleh Brouncker pada 1657–58 sebagai tindak balas kepada cabaran oleh Fermat , menggunakan pecahan bersambung. Kaedah untuk masalah umum pertama kali diterangkan sepenuhnya oleh Lagrange pada tahun 1766.^[7] 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."^[1][4]

Hermann Hankel memanggil kaedah chakravala

"perkara terbaik yang dicapai dalam teori nombor sebelum Lagrange."^[8]

Kaedahnya

Daripada pengenalan Brahmagupta, kita perhatikan bahawa untuk diberikan N,

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

Untuk persamaan ${\displaystyle x^{2}-Ny^{2}=k}$, ini membenarkan "komposisi" (samāsa) dua penyelesaian tiga kali ganda ${\displaystyle (x_{1},y_{1},k_{1})}$ dan ${\displaystyle (x_{2},y_{2},k_{2})}$ menjadi tiga kali ganda baru

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

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

${\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}}}$

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

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

Apabila integer positif m dipilih supaya (a + 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² − N dan oleh itu daripada (m² − 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 ${\displaystyle k=1}$ ditemui. Kaedah ini sentiasa ditamatkan dengan penyelesaian (dibuktikan oleh Lagrange pada tahun 1768).^[9] 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 ${\displaystyle x}$ dan ${\displaystyle y}$ bagi ${\displaystyle x^{2}=Ny^{2}+1,}$ apabila diberi ${\displaystyle a^{2}=Nb^{2}+k}$, apabila k ialah ±1, ±2, atau ±4.^[10]

k = -1

Menggunakan pengenalan Brahmagupta, untuk mengarang tiga ${\displaystyle (a,b,k)}$ dengan dirinya sendiri: ${\displaystyle (a^{2}+Nb^{2})^{2}-N(2ab)^{2}=k^{2}}$ ${\displaystyle \Rightarrow }$ ${\displaystyle (2a^{2}-k)^{2}-N(2ab)^{2}=k^{2}}$

Tiga kali ganda baharu boleh dinyatakan sebagai ${\displaystyle (2a^{2}-k,2ab,k^{2})}$. Menggantikan ${\displaystyle k=-1}$ untuk mendapatkan penyelesaian:

${\displaystyle x=2a^{2}+1,y=2ab}$

k = ±2

Sekali lagi menggunakan persamaan,${\displaystyle (2a^{2}-k)^{2}-N(2ab)^{2}=k^{2}}$${\displaystyle \Rightarrow }$${\displaystyle \left({\frac {2a^{2}-k}{k}}\right)^{2}-N\left({\frac {2ab}{k}}\right)^{2}=1}$

Menggantikan ${\displaystyle k=2}$,

${\displaystyle x=a^{2}-1,y=ab}$

Menggantikan ${\displaystyle k=-2}$,

${\displaystyle x=a^{2}+1,y=ab}$

k = 4

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

Manakah penyelesaian jika ${\displaystyle a}$ genap:

${\displaystyle x={\frac {a^{2}-2}{2}},y={\frac {ab}{2}}}$

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

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

Apabila ${\displaystyle a}$ ganjil,

${\displaystyle x={\frac {a}{2}}(a^{2}-3))^{2},y=({\frac {b}{2}}(a^{2}-1))^{2}}$

k = -4

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

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

Akhir sekali, daripada persamaan terdahulu, susun tiga kali ganda ${\displaystyle ({\frac {a^{2}+2}{2}},{\frac {ab}{2}},1)}$ dan ${\displaystyle ({\frac {a^{4}+4a^{2}+2}{2}},{\frac {ab(a^{2}+2)}{2}},1)}$, untuk mendapatkan ${\displaystyle ({\frac {(a^{2}+2)(a^{4}+4a^{2}+2)+Na^{2}b^{2}(a^{2}+2)}{4}})^{2}-N({\frac {ab(a^{4}+4a^{2}+3)}{2}})^{2}=1}$${\displaystyle \Rightarrow }$${\displaystyle ({\frac {(a^{2}+2)(a^{4}+4a^{2}+1)}{2}})^{2}-N({\frac {ab(a^{2}+3)(a^{2}+1)}{2}})^{2}=1}$${\displaystyle \Rightarrow }$${\displaystyle ({\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}$.

Ini memberi kita penyelesaian

${\displaystyle x={\frac {(a^{2}+2)[(a^{2}+1)(a^{2}+3)-2)]}{2}}y={\frac {ab(a^{2}+3)(a^{2}+1)}{2}}}$^[11]

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

Contoh

n = 61

Kes n = 61 (menentukan penyelesaian integer yang memuaskan ${\displaystyle a^{2}-61b^{2}=1}$), dikeluarkan sebagai cabaran oleh Fermat berabad-abad kemudian, telah diberikan oleh Bhaskara sebagai contoh.^[9]

Kita mulakan dengan penyelesaian ${\displaystyle a^{2}-61b^{2}=k}$ untuk sebarang k yang ditemui dengan apa-apa cara. Dalam kes ini kita boleh membiarkan b menjadi 1, oleh itu, oleh kerana ${\displaystyle 8^{2}-61\cdot 1^{2}=3}$, kita mempunyai tiga kali ganda ${\displaystyle (a,b,k)=(8,1,3)}$. Mengarangnya dengan ${\displaystyle (m,1,m^{2}-61)}$ memberikan tiga kali ganda ${\displaystyle (8m+61,8+m,3(m^{2}-61))}$, yang dikecilkan (atau lemma Bhaskara digunakan secara langsung) untuk mendapatkan:

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

Untuk 3 membahagikan ${\displaystyle 8+m}$ dan ${\displaystyle |m^{2}-61|}$ menjadi minimum, kami memilih ${\displaystyle m=7}$, 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 ${\displaystyle (39/2,5/2,-1)\,}$, yang digubah dengan dirinya sendiri tiga kali, dengan masing-masing ${\displaystyle m={7,11,9}}$, apabila k menjadi segi empat sama dan penskalaan boleh digunakan, ini memberikan ${\displaystyle (1523/2,195/2,1)\,}$. Akhir sekali, prosedur sedemikian boleh diulang sehingga penyelesaian ditemui (memerlukan 9 gubahan diri tambahan dan 4 skala persegi tambahan): ${\displaystyle (1766319049,\,226153980,\,1)}$. Ini ialah penyelesaian integer minimum.

n = 67

Katakan kita hendak menyelesaikan ${\displaystyle x^{2}-67y^{2}=1}$ untuk x dan y.^[12]

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

Lelaran pertama

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

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

Pada ketika ini, satu pusingan algoritma kitaran selesai.

Lelaran kedua

Kami kini mengulangi proses itu. Kami mempunyai ${\displaystyle (a,b,k)=(41,5,6)}$. Kami mahukan m > 0 supaya k membahagikan a + bm, iaitu 6 bahagi 41 + 5m dan |m² − 67| adalah minimum. Syarat pertama membayangkan bahawa m adalah dalam bentuk 6t + 5 (iaitu 5, 11, 17,… dsb.), dan antara m itu, |m² − 67| adalah minimum untuk m = 5. Ini membawa kepada penyelesaian baharu a = (41⋅5 + 67⋅5)/6, dsb.:

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

Lelaran ketiga

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

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

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

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

iaitu, kita mempunyai penyelesaian integer:

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

Persamaan ini menghampiri ${\displaystyle {\sqrt {67}}}$ sebagai ${\displaystyle {\frac {48842}{5967}}}$ dalam jidar kira-kira ${\displaystyle 2\times 10^{-9}}$.