Mètode chakravala

En matemàtiques i més precisament en aritmètica, el mètode chakravala és un algorisme per resoldre les equacions diofàntiques equivalents a les de Pell-Fermat. Una equació diofàntica és una equació amb coeficients en els nombres enters i les solucions que es busquessin són enteres. L'equació tractada és equivalent a:

${\displaystyle x^{2}-n\cdot y^{2}=1\quad {\text{amb}}\quad n\in \mathbb {N} -\{0,1\}}$

Aquest mètode es va desenvolupar a l'Índia i les seves arrels es poden resseguir fins al segle v. Iniciat per Aryabhata, es desenvolupa més endavant per Brahmagupta i Bhaskara II.

Selenius, en la seva avaluació del mètode chakravala, diu:

^[1]

En efecte cal esperar fins al Segle XVII perquè Europa descobreixi de manera independent els resultats dels treballs dels matemàtics indis.

Objectiu

Una forma de l'equació de Pell-Fermat s'expressa de la manera següent:

${\displaystyle x^{2}-n\cdot y^{2}=1\ ;}$

Aquí n designa un enter estrictament més gran que 1 i sense factor quadrat, el que significa que l'únic quadrat perfecte que divideix n és igual a u. L'equació és diofàntica la qual cosa significa que les parelles (x₀, y₀) cercats són parelles de nombres enters.

Totes les solucions s'expressen a partir de la parella solució formada per dos enters mínims en valor absolut en el conjunt de les solucions. El mètode chakravala permet obtenir una parella d'aquesta naturalesa.

La igualtat següent és un exemple de solució, era coneguda pels indis des d'abans de la nostra era:^[2]

${\displaystyle 1151^{2}-92\cdot 120^{2}=1\;}$

Història

Matemàtiques índies

Els matemàtics indis s'interessen molt aviat per l'aritmètica. Aryabhata, un matemàtic del Segle VI estableix les bases de l'aritmètica índia. Desenvolupa un sistema de numeració demostrant que coneixia probablement la notació posicional així com l'existència del zero^[3] Treballa sobre les equacions diofàntiques i per resoldre la identitat de Bézout, posa a punt un algorisme equivalent al d'Euclides que anomena kuṭṭaka (कूटटक) i que significa polvoritzador, ja que trenca els nombres en enters més petits. Treballa també sobre les fraccions contínues.^[4]

El matemàtic indi Brahmagupta (598 - 668) sembla el primer a analitzar en profunditat aquesta qüestió. Comprèn com, a partir de dues solucions, és possible construir-ne una de nova. Reiterant, obté així un nombre de solucions diferents tan elevat com es vulgui. Aquest mètode s'anomena samasa pels matemàtics indis^[5] Brahmagupta en dedueix tres algorismes. El primer li permet de trobar una solució si disposa d'una parella d'enters (x₀,y₀) la imatge del qual per l'equació és -1. En troba un segon tractant el cas on la imatge és 2 en valor absolut. En troba una tercera que dona el mateix resultat si la imatge és igual a +/- 4. Una primera versió del mètode chakravala veu la llum. Comença per un tempteig fins a trobar una parella que té per imatge 1, 2 o 4 en valor absolut, continua per un dels tres algorismes.^[6] Brahmagupta el fa servir el 628 per resoldre l'equació següent:^[7]

${\displaystyle x^{2}-83\cdot y^{2}=1\;}$

Aquest enfocament és insuficient per tractar els casos complexos, pot ser difícil trobar per tempteig una parella que doni un dels sis valors que permeten concloure. Al {Segle XII Bhskara II innova i proposa la forma definitiva del mètode chakravala. Correspon a la unió d'un algorisme cíclic, és a dir donanda una successió periòdica de parelles que contingui necessàriament una solució. L'algorisme cíclic és equivalent al de les fraccions contínues. El mètode chakravala acaba amb els càlculs de Brahmagupta si apareix un dels valors +/- 2 i +/- 4. Bhskara II el fa servir^[8] per trobar una solució mínima a l'equació següent ja trobada per Brahmagupta:

${\displaystyle x^{2}-61\cdot y^{2}=1\;}$

La parella solució que troba és:

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

És poc probable que Bhskara II hagi demostrat el fet que l'algorisme ofereix sempre una solució, és a dir per a qualsevol valor de n. Hi ha dues raons que ho fan pensar, primer de tot la demostració, llarga i tècnica, demana una sofisticació de lluny superior a les matemàtiques del Segle XII, a més si hagués trobat la demostració hauria tingut clar que el pas pel mètode de Brahmagupta no és necessari, encara que accelera la convergència de l'algorisme.^[9]

Més tard els matemàtics indis tracten nous exemples. Al Segle XIV un matemàtic de nom de Narayana estudia el cas on n és igual a 103 en els seus comentaris sobre el llibre Bijaganita' de Bhskara II.

Europa

Pierre de Fermat (1601 - 1665) llança el 3 de gener 1658 un desafiament als matemàtics europeus.^[10] Conté la cerca d'una solució al problema indi amb per a valor de n 61, ja tractat per Brahmagupta i Bhskara II. En aquesta època Europa no té coneixement dels resultats dels seus predecessors. A parti del repte,^[11] la reacció anglesa és ràpida, William Brouncker troba un algorisme equivalent al de Bhskara II, Bernard Frenicle de Bessy proposa una taula que conté totes les solucions per als valors de n inferiors a 150, que finalment es va perdre John Wallis descobreix els resultats de Brahmagupta i els demostra rigorosament. Frenicle de Bessy desafia Brouncker amb el valor n igual a 313, rep en resposta no només la solució sinó l'afirmació que el seu autor no ha necessitat més d'una hora o dues per a trobar-la.^[12]

Les dues qüestions teòriques subjacents, és a dir si per a tot valor de n estrictament positiu i sense factor quadrat existeix una solució i si la solució trobada genera totes les altres es resolen finalment per Joseph Louis Lagrange el 1767.^[13]

Aportacions de Brahmagupta

Conceptes previs

Els mètodes proposats aquí fan servir la potència del formalisme actual. Si bé el contingut matemàtic és anàleg al de Brahmagupta, les tècniques d'exposició així com les demostracions no reflecteixen el pensament del matemàtic indi.

Les notacions següents es fan servir en tota la resta de l'article. Es considera l'equació diofàntica següent, on n és un enter més gran que 1 i sense factor quadrat:

${\displaystyle (1)\quad x^{2}-n\cdot y^{2}=1\;}$

Sigui A l'anell dels nombres irracionals de la forma a + √n.b, on a i b designen dos nombres enters. Siguin N l'aplicació que al nombre a + √n. b li associa a² - n.b² i φ l'aplicació que a a + √n. b li associa φ(a + √n. b) = a - √n.b.

La funció N correspon a la norma de A en el sentit de la teoria de nombres algebraics. Posseeix una propietat força útil. Un nombre α de A igual a a + √n. b correspon a una solució (a , b) de l'equació (1) si i només si N(α) és igual a 1. Així, l'equació (1) també es pot escriure N(ξ) = 1. Per aquesta raó α si és un element de A que verifica N(α) = 1, es diu que és arrel de l'equació (1).

La funció φ també té altres propietats útils. És un automorfisme de A:

${\displaystyle \forall \alpha ,\beta \in \mathbb {A} \quad \varphi (\alpha \cdot \beta )=\varphi (\alpha )\cdot \varphi (\beta ),\quad \varphi (\alpha -\beta )=\varphi (\alpha )-\varphi (\beta )\;}$

L'aplicació φ és involutiva és a dir que si es compon dues vegades successives amb ella mateixa, és igual a la identitat o, cosa que és equivalent, és igual a la seva aplicació inversa:

${\displaystyle \forall \alpha \in \mathbb {A} \quad \varphi \circ \varphi (\alpha )=\alpha \;}$

Finalment, l'aplicació φ ofereix una expressió de la norma:

${\displaystyle \forall \alpha \in \mathbb {A} \quad {\mathcal {N}}(\alpha )=\alpha \cdot \varphi (\alpha )}$

Si es nota α = a + √n. b , prové del càlcul següent:

${\displaystyle {\mathcal {N}}(\alpha )=a^{2}-n\cdot b^{2}=(a+{\sqrt {n}}\cdot b)\cdot (a-{\sqrt {n}}\cdot b)=\alpha \cdot \varphi (\alpha )}$

Samasa

La primera propietat que es fa servir és la següent:

• Siguin α i β dos elements de A, llavors:

${\displaystyle {\mathcal {N}}(\alpha \cdot \beta )={\mathcal {N}}(\alpha )\cdot {\mathcal {N}}(\beta )\;}$

Si α = a₁ + √n.a₂ i β = b₁ + √n.b₂ aquesta igualtat s'escriu:

${\displaystyle (a_{1}b_{1}+na_{2}b_{2})^{2}-n\cdot (a_{1}b_{2}+a_{2}b_{1})^{2}=(a_{1}^{2}-na_{2}^{2})\cdot (b_{1}^{2}-nb_{2}^{2})\;}$

Aquesta igualtat és coneguda amb el nom d'Identitat de Brahmagupta que els indis en deien Samasa. Per convèncer-se de la seva exactitud, n'hi ha prou amb expressar N en funció de l'automorfisme φ:

${\displaystyle {\mathcal {N}}(\alpha \cdot \beta )=\alpha \beta \cdot \varphi (\alpha \beta )=\alpha \varphi (\alpha )\cdot \beta \varphi (\beta )={\mathcal {N}}(\alpha )\cdot {\mathcal {N}}(\beta )\;}$

Un cas particular correspon a aquell on β és un enter k , la igualtat pren la forma següent:

• Sigui α un element de A i k un enter, llavors:

${\displaystyle {\mathcal {N}}(k\alpha )={\mathcal {N}}(k)\cdot {\mathcal {N}}(\alpha )=k^{2}\cdot {\mathcal {N}}(\alpha )\;}$

Conseqüències

• Sigui α un element de A tal que N(α) = 1, llavors α ^-1 és un element de A i verifica N(α ^-1) = 1 i α ^-1 = φ(α).

En efecte, dir que N(φ) = 1, és dir que α.φ(α) = 1, el que demostra que φ(α) és l'invers de α i aplicant φ a la igualtat α.φ(α) = 1, s'obté substituint φ(α) per α ^-1: α ^-1.φ(α ^-1) = 1

• Si l'equació (1) admet una solució diferent de +/- 1, llavors admet una infinitat de solucions diferents.

En efecte, si α és una solució, α ^-1 també n'és una, segons la proposició precedent i com que la norma d'un producte és igual al producte de les normes, es disposa de les igualtats següent:

${\displaystyle \forall k\in \mathbb {Z} \quad {\mathcal {N}}(u^{k})=1\quad {\text{i}}\quad {\mathcal {N}}(-u^{k})=1\;}$

N'hi ha prou amb demostrar que les potències de α són totes diferents. Això prové del fet que si un nombre real x verifica x ^k = 1, on k és un enter diferent de 0, llavors x és igual a +/- 1. Sigui k i l dos enters tals que α^k = α^l llavors α^k-l és igual a 1 i com que α és diferent d'1 i -1, k - l és igual a 0. Comprendre com ho va fer Brahmagupta per resoldre l'equació (1) depèn de tres proposicions, simples de demostar:

• Sigui α un element de A tal que N(α) = -1, α ² és solució de (1).

N'hi ha prou amb fixar-se que la norma de α ² és el quadrat de la norma de α i és igual a 1.

• Sigui α un element de A tal que N(α) sigui igual a +/- 2 , llavors 1/2.α² és un element de A solució de (1).

En efecte, si α és igual a a + b .√n llavors un càlcul mostra que α² = a² + n.b² + 2ab.√n. Com que a² + n.b² = N(α) + 2.n.b² i com que N(α) i 2ab són múltiples de 2, α² també n'és. El càlcul següent permet concloure:

${\displaystyle 4\cdot {\mathcal {N}}\left({\frac {\alpha ^{2}}{2}}\right)={\mathcal {N}}\left(\alpha ^{2}\right)=4\quad {\text{i}}\quad {\mathcal {N}}\left({\frac {\alpha ^{2}}{2}}\right)=1\;}$

• Sigui α un element de A tal que N(α) sigui igual a +/- 4 i tal que 2 no divideix α, llavors 1/8.α³ és un element de A de norma igual a +/- 1 .

En efecte, calculant α³:

${\displaystyle \alpha ^{3}=(a+b\cdot {\sqrt {n}})^{3}=a^{3}+3ab^{2}n+{\sqrt {n}}\cdot (nb^{3}+3a^{2}b)=a(a^{2}-nb^{2}+4nb^{2})+b{\sqrt {n}}\cdot (3a^{2}-3nb^{2}+4nb^{2})\;}$

Fixant-se que N(α) = a ² - n.b ² = +/- 4, s'obté:

${\displaystyle \alpha ^{3}=a\left({\mathcal {N}}(\alpha )+4nb^{2}\right)+b{\sqrt {n}}\cdot \left(3\cdot {\mathcal {N}}(\alpha )+4nb^{2}\right)=4a\left(\epsilon +nb^{2}\right)+4b{\sqrt {n}}\cdot \left(3\epsilon +nb^{2}\right)\quad {\text{amb}}\quad \epsilon =\pm 1\;}$

Com que ${\displaystyle \epsilon }$ és senar, n'hi ha prou amb demostrar que b és senar per provar que α³ és un múltiple de 8. Si b és parell, n.b ² és un múltiple de quatre i com que N(α) = a ² - n.b ² també és un múltiple de quatre, a és parell. Ara bé per hipòtesi no és un múltiple de dos i a i b no poden ser parells de manera simultània. En conseqüència, b és senar i ε + nb² així com 3ε + nb² són parells si n és senar. Això demostra que α³ és un múltiple de 8 si n és senar.

Ara bé n és sempre senar. En efecte, si n és parell, com que N(α) és parell, a també ho és i a ² és un múltiple de quatre, per tant com que n no té cap factor quadrat, n no és un múltiple de quatre, per tant b és parell i α és un múltiple de 2, ço que és contrari a la hipòtesi i finalitza la demostració.

Així el coneixement d'un element α de norma igual a +/- 4 permet trobar una solució. Si α és divisible per 2 en A, 1/2.α és un element de norma igual a +/- 1 i el seu quadrat és una solució. Si no, 1/8.α³ és un element de norma igual a +/- 1, un pas al quadrat permet també determinar una solució.

Exemples

Exemple de Brahmagupta

Es tracta amb aquest mètode l'exemple de Brahmagupta següent:

${\displaystyle x^{2}-83\cdot y^{2}=1\;}$

S'escull com a primer assaig α = 9 + √83. Observant que N(α) = -2- És assenyat calcular α²:

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

Una proposició precedent mostra que 82 + √83.9 té per a norma 1 i (82, 9) és solució de l'equació, en efecte:

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

Desafiament de Fermat

El desafiament de Fermat es resol de la mateixa manera:

${\displaystyle x^{2}-61\cdot y^{2}=1\;}$

Brahmagupta opera de la manera següent, es fixa que si α = 39 + 5.√61 llavors N(α) és igual a -4. Ben evidentment el formalisme de Brahmagupta no té res a veure amb el que es fa servir aquí, fins i tot si els càlculs són els mateixos. Calcula 1/2.α²:

${\displaystyle {\frac {1}{2}}\alpha ^{2}={\frac {1}{2}}(39+5\cdot {\sqrt {6}}1)^{2}={\frac {1}{2}}(39^{2}+5^{2}\times 61+2\times 5\times 39{\sqrt {6}}1)=1\,523+195\cdot {\sqrt {6}}1\;}$

Després calcula 1/8.α³ i la seva norma:

${\displaystyle {\frac {1}{8}}\alpha ^{3}={\frac {1}{4}}(39+5\cdot {\sqrt {6}}1)\cdot (1\,523+195\cdot {\sqrt {6}}1)=29\,718+3\,805\cdot {\sqrt {6}}1\quad {\text{i}}\quad {\mathcal {N}}({\frac {1}{8}}\alpha ^{3})=29\,718^{2}-61\times 3\,805^{2}=-1}$

La solució és per tant 1/64.α⁶, sigui:

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

El mètode és remarcablement econòmic per a un algorisme tan antic.

Aportació de Bhaskara II

Inici de l'algorisme

Una dificultat del mètode de Brahmagupta resideix en el fet que no sempre és fàcil trobar un nombre α de A de norma en el conjunt dels nombres amb valor absolut igual a 1, 2 o 4. L'aportació de Bhaskara II descrita en el Siddhanta Siroman consisteix a enriquir el mètode d'un algorisme que acaba infal·liblement proveint una quasisolució d'aquesta naturalesa.

Bhaskara II construeix una successió recurrent (α_n) d'elements de A de la següent manera:

El primer element α₁ de la successió és de la forma a₁ + √n. S'escull de tal manera que la norma de α₁, igual a a₁² - n, sigui la més petita possible en valor absolut.

Emprant j per subíndex dels elements de la successió. Es nota α_j = a_j + b_j.√n. Es construeix un element β_j = m_j + √n. El nombre enter m_j és tal que a_j + m_j.b_j sigui un múltiple de la norma de α_j i m_j minimitza el valor absolut de la norma de β_j. L'element α_{j + 1} es defineix de la manera següent:

${\displaystyle \alpha _{j+1}=a_{j+1}+b_{j+1}{\sqrt {n}}={\frac {1}{|{\mathcal {N}}(\alpha _{j})|}}\alpha _{j}\beta _{j}={\frac {1}{|{\mathcal {N}}(\alpha _{j})|}}\left(a_{j}m_{j}+nb_{j}+{\sqrt {n}}(a_{j}+m_{j}b_{j})\right)\;}$

Exemples

Desafiament de Fermat

S'escull altra vegada d igual a 61. El valor de a ₁ és igual a 8 per minimitzar la norma de α₁, en efecte:

${\displaystyle {\mathcal {N}}(\alpha _{1})={\mathcal {N}}(8+{\sqrt {6}}1)=8^{2}-61=3\;}$

Per determinar el valor de α₂ cal calcular m ₁. Es disposa de la igualtat següent:

${\displaystyle \alpha _{2}=a_{2}+b_{2}\cdot {\sqrt {6}}1={\frac {1}{{\mathcal {N}}(\alpha _{1})}}\cdot \alpha _{1}\cdot \beta _{1}\;={\frac {1}{3}}(8+{\sqrt {6}}1)\cdot (m_{1}+{\sqrt {6}}1)={\frac {8m_{1}+61}{3}}+{\frac {8+m_{1}}{3}}{\sqrt {6}}1\;}$

Com que α₂ és un element de A, 8 + m ₁ és un múltiple de 3, per tant m ₁ és de la forma 3. k + 1. Per minimitzar la norma de β₁, cal escollir k igual a 2. Se'n dedueix que m ₁ és igual a 7, el que dona:

${\displaystyle \alpha _{2}={\frac {8\times 7+61}{3}}+{\frac {8+7}{3}}{\sqrt {6}}1=39+5\cdot {\sqrt {6}}1\quad {\text{i}}\quad {\mathcal {N}}(\alpha _{2})=-4\;}$

La successió del mètode és la de Brahmagupta. El mètode chakravala permet ara resoldre sense tempteig i amb un mínim de càlcul el desafiament de Fermat.

Exemple de Narayana

Aquest segon exemple també s'ha extret del Siddhanta Siroman de Bhaskara II, anotat per Narayana. Si d és igual a 103, el valor de a ₁ és igual a 10 i:

${\displaystyle {\mathcal {N}}(\alpha _{1})={\mathcal {N}}(10+{\sqrt {1}}03)=10^{2}-103=-3\;}$

El càlcul de α₂ dona:

${\displaystyle \alpha _{2}=a_{2}+b_{2}\cdot {\sqrt {1}}03={\frac {1}{3}}(10+{\sqrt {1}}03)\cdot (m_{1}+{\sqrt {1}}03)={\frac {10\cdot m_{1}+103}{3}}+{\frac {10+m_{1}}{3}}{\sqrt {1}}03\;}$

Aquesta vegada aquí, m ₁ és de la forma 3.k - 1. Per minimitzar la norma de β₁, cal escollir m ₁ igual a 11. S'obté:

${\displaystyle \alpha _{2}={\frac {10\times 11+103}{3}}+{\frac {10+11}{3}}{\sqrt {1}}03=71+7\cdot {\sqrt {1}}03\quad {\text{i}}\quad {\mathcal {N}}(\alpha _{2})=-6\;}$

El càlcul de α₃ dona:

${\displaystyle \alpha _{3}={\frac {1}{6}}(71+7\cdot {\sqrt {1}}03)\cdot (m_{2}+{\sqrt {1}}03)={\frac {71\cdot m_{2}+7\times 103}{6}}+{\frac {71+7\cdot m_{2}}{6}}{\sqrt {1}}03\;}$

Ara, m ₂ és de la forma 6.k - 5. Per minimitzar la norma de β₂, cal escollir m ₂ igual a 7. S'obté:

${\displaystyle \alpha _{3}=203+20\cdot {\sqrt {1}}03\quad {\text{et}}\quad {\mathcal {N}}(\alpha _{3})=9\;}$

El càlcul de α₄ dona:

${\displaystyle \alpha _{4}={\frac {203\cdot m_{3}+20\times 103}{9}}+{\frac {203+20\cdot m_{3}}{9}}{\sqrt {1}}03\;}$

Aquesta vegada, m ₃ és de la forma 9.k + 2. Per minimitzar la norma de β₃, cal escollir m ₃ igual a 11. S'obté:

${\displaystyle \alpha _{4}=477+47\cdot {\sqrt {1}}03\quad {\text{et}}\quad {\mathcal {N}}(\alpha _{4})=2\;}$

El càlcul de Brahmagupta permet concloure, el valor buscat és igual a 1/2.α₄²:

${\displaystyle \alpha ={\frac {1}{2}}\alpha _{4}^{2}={\frac {1}{2}}(477+47\cdot {\sqrt {1}}03)^{2}=227\,528+22\;419\cdot {\sqrt {1}}03}$

Demostracions associades a l'aportació de Bhaskara II

Lemes

Hi ha dos lemes que demostren l'existència de la successió utilitzada per Bhaskara II. Amb les notacions dels paràgrafs precedents i si k_j designa el valor absolut de la norma de α_j, es fan servir els següents elements:

${\displaystyle \forall j\in \mathbb {N} \quad k_{j}\cdot \alpha _{j+1}=\beta _{j}\cdot \alpha _{j}\quad {\text{amb}}\quad \alpha _{j}=a_{j}+b_{j}\cdot {\sqrt {n}}\quad {\text{i}}\quad \beta _{j}=m_{j}+{\sqrt {n}}}$

S'ha escollit m_j de tal manera que:

${\displaystyle k_{j}\cdot b_{j+1}=a_{j}+b_{j}\cdot m_{j}\quad {\text{amb}}\quad \beta _{j}\cdot \alpha _{j}=a_{j}\cdot m_{j}+n\cdot b_{j}+(a_{j}+b_{j}\cdot m_{j})\cdot {\sqrt {n}}\;}$

Els dos exemples precedents il·lustren el fet que α_j.β_j és un múltiple de k_j. Aquesta propietat és l'objecte dels dos lemes següents:

• Amb les notacions precedents, si a_j + b_j.m_j s'escull múltiple de k_j i si a_j, b_j són primers entre ells llavors, α_j.β_j és un múltiple de k_j .

• Depenent de les hipòtesis del lema precedent i si la norma de β _j s'escull mínima en valor absolut, a_j+1, b_j+1 són primers entre ells.

Una vegada demostrats aquests lemes, s'observa que sempre és possible trobar un valor convenient per a m _j. En efecte, com que a _j i b _j són primers entre ells, la identitat de Bézout mostra que existeix un enter c _j tal que c _j.b _j - 1 sigui un múltiple de k _j. Se'n dedueix que si x és un enter, x.k _j + c _j.b _j.a _j és un múltiple de k _j, llavors sempre és possible escollir x de tal manera que el valor absolut de la norma de β_j sigui mínim. Trobar c _j significa resoldre la identitat de Bézout, el que els indis ja sabien fer amb l'algorisme d'Euclides.

Els lemes mostren que si m _j s'escull segons el mètode del paràgraf precedent, α_j._j és un múltiple de k _j, α_j+1 és un element de A i a _j+1 i b _j+1 són primers entre ells, el que permet reiterar el pas.

Demostracions dels lemes

.

• El valor α_j.β_j és un element de A múltiple de k _j:

Utilitzem les notacions següents:

${\displaystyle \alpha _{i}\cdot \beta _{j}=a'_{j+1}+b'_{j+1}\cdot {\sqrt {n}}\;}$

Els elements a' _j+1 i b' _j+1 són elements de Z . A aquest efecte poden ser vistos com elements de l'anell A. Dir que b' _j+1 és divisible entre k _j és equivalent a dir que b' _j+1 és divisible entre _j.(_j), en efecte:

${\displaystyle k_{j}=|{\mathcal {N}}(\alpha _{j})|=|\alpha _{j}\cdot \varphi (\alpha _{j})|\quad {\text{per tant}}\quad \alpha _{i}\cdot \beta _{j}=a'_{j+1}+b_{j+1}\cdot \alpha _{j}\cdot \varphi (\alpha _{j})\cdot {\sqrt {n}}\;}$

Se'n dedueix l'existència d'un nombre δ_j de A tal que: α_j.δ_j = a' _j+1. Si e _j i f _j són dos elements de Z tals que:

${\displaystyle \delta _{j}=e_{j}+f_{j}{\sqrt {n}}\quad {\text{llavors}}\quad \alpha _{j}\delta _{j}\in \mathbb {Z} \Rightarrow a_{j}f_{j}+b_{j}e_{j}=0\quad {\text{ja que}}\quad \alpha _{j}\delta _{j}=a_{j}e_{j}+nb_{j}f_{j}+(a_{j}f_{j}+b_{j}e_{j}){\sqrt {n}}\;}$

L'última igualtat expressa el fet que els parells (e _j, f _j) i (a _j, - b _j) són proporcionals. Com que a _j i b _j són primers entre ells, existeix un enter a _j+1 tal que:

${\displaystyle (e_{j},f_{j})=a_{j+1}(a_{j},-b_{j})\quad {\text{et}}\quad \delta _{j}=a_{j}+f_{j}{\sqrt {n}}=a_{j+1}(a_{j}-b_{j}{\sqrt {n}})=a_{j+1}\cdot \varphi (\alpha _{j})\;}$

Reemplaçant δ_j pel seu valor en l'expressió α_j.δ_j s'obté:

${\displaystyle \alpha _{i}\cdot \beta _{j}=\alpha _{j}\cdot \varphi (\alpha _{j})\cdot a_{j+1}+b_{j+1}\cdot \alpha _{j}\cdot \varphi (\alpha _{j})\cdot {\sqrt {n}}=k_{j}(a_{j+1}+b_{j+1}\cdot {\sqrt {n}})\;}$

• Els valors a _j+1 , b _j+1 són primeres entre elles si el valor absolut de la norma de _j s'escull mínima:

Es verifica la següent igualtat:

${\displaystyle \alpha _{j}\beta _{j}=\alpha _{j}\varphi (\alpha _{j})(a_{j+1}+b_{j+1}{\sqrt {n}})\quad {\text{per tant}}\quad \beta _{j}=\varphi (\alpha _{j})(a_{j+1}+b_{j+1}{\sqrt {n}})\;}$ Un enter divisor comú de a _j+1 i b _j+1 divideix β _j així com la seva norma. Com que la norma de β_j s'ha escollit mínima en valor absolut, no existeix cap divisor comú a a _j+1 i b _j+1 altre que 1 i -1.

Caràcter cíclic

Una vegada demostrat que la successió (α_j) està ben definida, s'estudia el seu comportament. La successió és cíclica en un cert sentit. Més precisament, observant que la relació R definida per α R β si i només si existeix un element inversible ε de A tal que α = ε.β és una relació d'equivalència. Es nota cl(α) la classe d'equivalència per la relació R:

• La successió (cl(α_j)) és cíclica.

Aquesta propietat és la conseqüència de tres proposicions:

• La successió α(_j) està definida de manera unívoca i la successió (Nα(_j)) és fitada.

La igualtat N (ε.β) = N (ε).N(β) = N(β) mostra que tots els elements d'una mateixa classe tenen igual norma. Llavors és possible parlar de la norma d'una classe d'equivalència, el que permet expressar la proposició següent:

• No existeix més que un nombre finit de classes d'equivalència de norma inferior a un enter estrictament positiu.

Finalment:

• Siguin i i j dos enters positius i ε un element de A inversible. Si α_i = ε.α_j llavors α_i+1 = ε.α_j+1.

Amb aquestes tres propietats, és senzill comprendre que la successió (cl (α_j) és periòdica al final d'un cert rang. En efecte, la successió (N(α_j)) és fitada, no pren aquests valors més que en un nombre finit de classes d'equivalència segons la proposició dos. Al final d'un cert rang, la successió té per a imatge una classe d'equivalència repetida. La tercera proposició mostra que llavors la successió és necessàriament periòdica.

Aquestes propietats només demostren que la periodicitat a partir d'un cert rang. El paràgraf següent demostra que aquest rang és igual a zero i la successió és periòdica des del subíndex zero.

Demostracions

.

• La successió (α_j) està definida de manera unívoca i la successió (N(α_j)) és fitada:

Es nota r la part entera de la arrel quadrada de n. Es demostra per recurrència que α_j és inferior o igual a 2.r i que la successió està definida de manera unívoca.

Si j és igual a un, es disposa dels augments següents:

${\displaystyle r^{2}<n<(r+1)^{2}=r^{2}+2r+1\;}$

La distància entre els dos quadrats perfectes més propers entre si tals que n sigui entre mig dels dos és igual a 2.r+1 el que demostra que el quadrat més proper és a una distància inferior o igual a r ja que cada terme de la majorant és enter. El fet que el quadrat més proper sigui a una distància inferior o igual a r i per tant a 2.r mostra que la norma de α₁ és inferior a 2.r .

Com que n és enter, no pot ser exactament enmig de r ² i (r + 1)². No existeix per tant més que un únic valor possible per a m ₀ i a fortiori per a α₁.

Se suposa la propietat demostrada fins a l'ordre j i es demostra per a l'ordre j + 1. Sigui m' _j el major enter inferior o igual a r i de la forma a _j + m' _j.b_j sigui un múltiple de k_j. Es disposa dels majorants següents:

${\displaystyle m_{j}^{\prime 2}<n<(m^{\prime }+k_{j})^{2}=m_{j}^{\prime 2}+2m_{j}^{\prime }k_{j}+k_{j}^{2}\;}$

Altra vegada n no es pot situar exactament enmig de les dues fites de la majorant, si no √n seria una fracció, el que és contrari a la hipòtesi que indica que n és sense factor quadrat. Se'n dedueix que m_j està definit de manera unívoca i que n és a una distància de m _j² inferior o igual a m' _j. k_j + 1/2.k_j². Aquesta majoració i el fet que m _j sigui inferior o igual a r, demostren que la norma de β_j és inferior o igual a r.k_j + 1/2.k_j².

El paràgraf precedent i la hipòtesi de recurrència estableixen que:

${\displaystyle {\mathcal {N}}(\alpha _{j+1})={\frac {{\mathcal {N}}(\beta _{j})}{{\mathcal {N}}(\alpha _{j})}}\leq {\frac {rk_{j}+1/2\cdot k_{j}^{2}}{k_{j}}}=r+{\frac {1}{2}}k_{j}\leq 2r\;}$

El que demostra que la successió està majorada i que un valor del majorant eatà donat per 2.r si r designa la part entera de l'arrel quadrada de n.

Es demostra que la successió les classes dels α_k és periòdica. S'observa que dos elements d'una mateixa classe posseeixen la mateixa norma ja que la norma d'una unitat és igual a 1 en valor absolut, el que permet donar un sentit a la proposició següent:

• Sigui C una de constant estrictament positiva. No existeix més que un nombre finit de classes d'equivalències d'elements de A amb norma inferior a C:

Aquest resultat és la conseqüència d'un lema, que indica que no existeix més que un nombre finit de ideals principals generats per un element de norma en valor absolut inferior a una constant donada. Un ideal principal engendrat per un element α de A és el conjunt dels múltiples de α en A. Per això, n'hi ha prou amb establir la proposició següent: Sigui J un ideal principal engendrat per un element α de norma C un enter estrictament positiu i B el quocient de A per J .

(1) L'anell unitari quocient B és de cardinal finit:

Aquesta proposició es demostrarà en el paràgraf ideal primer, ideal màxim de l'article ideal de l'anell dels enters d'un cos quadràtic.

(3) No existeix més que un nombre finit de classes d'equivalència de norma inferior a C:

Un ideal no conté més que una única classe d'equivalència de generadors. En efecte, siguin α i β dos generadors de tal ideal. L'element β és generat per β i recíprocament, el que demostra l'existència d'elements γ i δ tals que:

${\displaystyle \beta =\gamma \cdot \alpha {\text{ i }}\alpha =\delta \cdot \beta \quad {\text{per tant}}\quad \alpha =\delta \cdot \beta =\delta \cdot \gamma \cdot \alpha \quad {\text{o sigui}}\quad \delta \cdot \gamma =1\;}$

El caràcter finit del nombre d'ideals i el fet que un ideal no conté més que una classe d'equivalència permet concloure la demostració.

• Siguin i i j dos enters positius i ε un element de A inversible. Si α_i = ε.α_j llavors α_i+1 = ε.α_j+1:

Si α_i = ε.α_j llavors les normes de α_i i α_j són iguals en valor absolut ja que la norma és multiplicativa i la de ε és igual a +/- 1. El lema mostra que:

${\displaystyle |{\mathcal {N}}(\alpha _{i})|\alpha _{i+1}=\alpha _{i}\cdot \beta _{i}\quad {\text{per tant}}\quad |{\mathcal {N}}(\alpha _{j})|\alpha _{i+1}=\epsilon ^{-1}\cdot \alpha _{j}\cdot \beta _{i}\;}$

Ce qui montre que β_i est un multiple de la norme de α_j et comme la norme de β_i est choisi minimale, on a bien β_i = β_j et ceci termine la démonstration.

El que demostra que β_i és un múltiple de la norma de α_j i com que la norma de β_i s'ha escollit mínima, es té β_i = β_j i això acaba la demostració.

Estructura de la successió

El fet que la successió sigui periòdica no indica a priori que attibi a un punt de norma igual a u en valor absolut. Tanmateix aquest és sempre el cas:

• Existeix un valor j estrictament superior a zero i tal que la norma de α_j és igual a 1 en valor absolut.

La successió (α_k) forma una espècie de palíndrom, més precisament, si G designa el grup de les unitats:

• Segons que el primer valor j estrictament positiu tal que α_j tingui de norma igual a u en valor absolut sigui parell o senar, es produeix una de les dues configuracions següents:

${\displaystyle {\text{Si j}}\ {\text{ }}\!\!{\acute {\mathrm {e} }}\!\!{\text{ s parell: }}\exists k\in \mathbb {N} \quad j=2k{\text{ i }}\exists (\epsilon _{l})\in G^{k}\quad \alpha _{k+1}=\epsilon _{1}\varphi (\alpha _{k-1}),\;\alpha _{k+2}=\epsilon _{2}\varphi (\alpha _{k-2}),\cdots ,\alpha _{2k-1}=\epsilon _{k-1}\varphi (\alpha _{1}),\;\alpha _{j}=\epsilon _{k}}$

i:

${\displaystyle {\text{Si j}}\ {\text{ }}\!\!{\acute {\mathrm {e} }}\!\!{\text{ s senar: }}\exists k\in \mathbb {N} \quad j=2k+1{\text{ i }}\exists (\epsilon _{l})\in G^{k}\quad \alpha _{k+1}=\epsilon _{1}\varphi (\alpha _{k}),\;\alpha _{k+2}=\epsilon _{2}\varphi (\alpha _{k-1}),\cdots ,\alpha _{2k}=\epsilon _{k-1}\varphi (\alpha _{1}),\;\alpha _{j}=\epsilon _{k}}$

Una conseqüència directa és que la successió (α_k) conté una solució de l'equació de Pell per a m igual a 1:

• Sigui j el valor més petit estrictament positiu tal que la norma de α_j sigui igual a 1 en valor absolut, la norma de α_2j és estrictament positiva i igual a 1.

Demostracions

Sigui ψ la funció de A - {0} en A - {0} que a α_k li associa α_k+1. Més precisament a un element α de A li associa un element de forma m + √n amb m natural tal que β.α sigui un múltiple de la norma de α, de norma mínima i tal que la igualtat N(α).ψ(α) = α.β. Els lemes i el paràgraf precedent mostren que l'aplicació ψ està ben definida i que, si α₀ sha escollit igual a 1: ${\displaystyle \forall k\in \mathbb {N} ,\quad \psi (\alpha _{k})=\alpha _{k+1}}$

Aquesta funció té una simetria respecte a la funció φ, si G designa el agrup de les unitats de A:

• Es verifica la següent propietat:

${\displaystyle \forall \alpha ,\gamma \in \mathbb {A} -\{0\},\quad \psi (\alpha )=\gamma \Rightarrow \exists \epsilon \in G,\;\psi \circ \varphi (\gamma )=\epsilon \varphi (\alpha )\;}$

En altres paraules, si α té per imatge per ψ el valor γ, llavors γ té per imatge per ψ el valor α, tret d'un factor inversible.

En efecte, si α té per a imatge per ψ el valor γ, existeix un únic element β de la forma m + √n amb m natural tal que, si ε₁ (resp. ε₂) és el signe de la norma de ε (resp. γ):

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

L'element β és de forma m + √n amb m natural tal que β.γ és un múltiple de la norma de γ, ja que φ(α) és enter. Sigui β' un element que verifica aquestes propietats i de norma inferior a β, la igualtat γ = α.β'/N(β') mostra que β' és de norma superior a β. Se'n dedueix que les normes de β i β' són iguals i el seu caràcter mínim es verifica. La igualtat (1) mostra que φ(α), tret d'un element inversible és la imatge de φ(γ) per ψ. La proposició queda demostrada.

Se'n dedueix que la funció ψ és una bijection de A - {0} en A - {0}.

• Existeix un valor j tal que la norma de α_j és igual a u en valor absolut:

Fixem-nos al principi que es pot definir α₀ com a igual a 1, ja que ψ(1) = α₁. Sigui j el major valor tal que la successió d'elements α₀, α₁ ., α_j-1 no contingui més que elements de classes diferents per la relació d'equivalència R. Tal definició té sentit ja que les classes d'equivalències de norma inferiors a 2r són en nombre finit, per tant la successió de les classes d'equivalència es repeteix necessàriament a partir d'un cert rang. El valor α_j és a la llista α₀, α₁ ., α_j-1 tret d'un factor multiplicatiu inversible. No pot ser igual a un element pres en α₁ ., α_j-1 ja que tal element tindria dos antecedents el que l'última proposició a demostrat impossible. Se'n dedueix que la classe de α_j és igual a la de α₀. N'hi ha prou amb fixar-se que la successió dels valors (a_k) i (b_k) és estrictament creixent per a concloure que la solució trobada no és trivial.

• La successió (α_j) forma un palíndrom:

La igualtat ψ(1) = α₁ mostra que ψoφ(α₁) és de la classe de φ(1) = 1. Se'n dedueix que cl (α_j-1) = cl (φ(α₁)). La igualtat ψ(α₁) = α₂ mostra que l'antecedent de la classe de φ (α₂) és la classe de φ(α₁) el que demostra que cl(α_j-2) = cl(φ(α₂)). Una recurrència fundada en aquest principi permet establir la proposició.

Fracció continua

La part recursiva del mètode chakravala és molt proper del de la fracció continua. Aquí, l'objectiu és d'aproximar l'arrel de n per una expressió òptima de la naturalesa següent:

${\displaystyle {\sqrt {n}}=f_{0}+{\cfrac {1}{f_{1}+{\cfrac {1}{f_{2}+{\frac {1}{f_{3}+\,\cdots }}}}}}\quad {\text{amb}}\quad f_{i}\in \mathbb {Z} \;}$

Introducció amb un exemple

S'estudia el cas on n és igual a 19.

A l'ordre 0, l'objectiu és de trobar el valor f₀ més proper possible de √19. S'obté la igualtat:

${\displaystyle {\sqrt {1}}9=4+(-4+{\sqrt {1}}9)\quad {\text{i}}\quad f_{0}=4,\quad \omega _{0}=-4+{\sqrt {1}}9}$

Aquí, ω_k designa el residu de la fracció continua, sovint anomenat quocient complet d'índex k .

A l'ordre 1, es busca una aproximació √19 de la forma f₀ + 1/f₁ millor possible, s'obté:

${\displaystyle -4+{\sqrt {1}}9={\frac {3}{4+{\sqrt {1}}9}}={\frac {1}{\frac {9-5+{\sqrt {1}}9}{3}}}={\frac {1}{3+{\frac {1}{3}}(-5+{\sqrt {1}}9)}}\quad {\text{i}}\quad {\sqrt {1}}9=4+{\frac {1}{3+\omega _{1}}},\;f_{1}=3,\;\omega _{1}={\frac {1}{3}}(-5+{\sqrt {1}}9)}$

A l'ordre 2:

${\displaystyle {\frac {1}{3}}(-5+{\sqrt {1}}9)={\frac {-6}{3(5+{\sqrt {1}}9)}}={\frac {1}{-{\frac {10-5+{\sqrt {1}}9}{2}}}}={\frac {1}{-5+{\frac {1}{2}}(5-{\sqrt {1}}9)}}\quad {\text{i}}\quad {\sqrt {1}}9=4+{\frac {1}{3+{\frac {1}{-5+\omega _{2}}}}},\;f_{2}=-5,\;\omega _{2}={\frac {1}{3}}(5-{\sqrt {1}}9)}$

A l'ordre 3:

${\displaystyle {\frac {1}{2}}(5-{\sqrt {1}}9)={\frac {6}{2(5+{\sqrt {1}}9)}}={\frac {1}{\frac {9-4+{\sqrt {1}}9}{3}}}={\frac {1}{3+{\frac {1}{3}}(-4+{\sqrt {1}}9)}}\quad {\text{i}}\quad {\sqrt {1}}9=4+{\frac {1}{3+{\frac {1}{-5+{\frac {1}{3+\omega _{3}}}}}}},\;f_{3}=3,\;\omega _{3}={\frac {1}{3}}(-4+{\sqrt {1}}9)}$

A l'ordre 4:

${\displaystyle {\frac {1}{3}}(-4+{\sqrt {1}}9)={\frac {3}{3(4+{\sqrt {1}}9)}}={\frac {1}{8-4+{\sqrt {1}}9}}\quad {\text{i}}\quad {\sqrt {1}}9=4+{\frac {1}{3+{\frac {1}{-5+{\frac {1}{3+{\frac {1}{8+\omega _{5}}}}}}}}},\;f_{4}=8,\;\omega _{4}=\omega _{1}=-4+{\sqrt {1}}9}$

El fet que ω₄ sigui igual a ω₀ mostra que la successió (f_k) és periòdica, aquests termes són: f₀, f₁, f₂, f₃, f₄, f₁, f₂, f₃, f₄, f₁ .... Una igualtat d'aquest tipus generalment es nota de la manera següent:

${\displaystyle {\sqrt {1}}9=[4,{\overline {3,-5,3,8}}]}$

Es determinen les fraccions parcials d'ordre k θ_k, habitualment anomenades residu d'índex k.

${\displaystyle \mu _{0}=f_{0}={\frac {4}{1}},\;\mu _{1}=f_{0}+{\frac {1}{f_{1}}}={\frac {13}{3}},\;\mu _{2}=f_{0}+{\cfrac {1}{f_{1}+{\frac {1}{f_{2}}}}}={\frac {61}{14}}=\;\mu _{3}=f_{0}+{\cfrac {1}{f_{1}+{\frac {1}{f_{2}+{\frac {1}{f_{3}}}}}}}={\frac {170}{39}}}$

El càlcul de la successió (α_k) del mètode chakravala dona:

${\displaystyle \alpha _{1}=4-{\sqrt {1}}9,\;\alpha _{2}=13-3\cdot {\sqrt {1}}9,\;\alpha _{3}=61-14\cdot {\sqrt {1}}9,\;\alpha _{4}=170-39\cdot {\sqrt {1}}9}$

En els dos casos es troben e les mateixes parelles (4,1), (13, 3), (61, 14) i (170, 39), el que no és obra de l'atzar. En els dos casos s'obté la solució següent:

${\displaystyle 170^{2}-19\times 39^{2}=28\,900-28\;899=1\;}$

Observació: La convenció escollida aquí per definir la fracció és que cada reduïda d'índex k ha de ser tan a prop com sigui possible de l'arrel. La convenció d'una fracció continua és una mica diferent. No només cada residu d'índex k ha de ser tan a prop com sigui possible de l'arrel sinó que a més la successió (f_k) no ha de prendre més que valors positius. La convenció de les fraccions contínues també es pot aplicar al mètode de chakravala, significa imposar a la successió de les normes dels (β_k) que sigui estrictament negativa. Totes les demostracions s'apliquen igualment amb aquesta convenció. En canvi, la longitud del cicle pot ser més llarga, per exemple:

${\displaystyle {\sqrt {1}}9=[4,{\overline {2,1,3,1,2,8}}]}$

Enfocament teòric

Siguin (f_k) i (θ_k) on k és un enter positiu, dues successions de les quals la primera és amb valors en Z i la segona en A. Les successions es defineixen per recurrència. El valor f₀ és igual a la part entera de √n, on n és un enter estrictament superior a 1 i sense factor quadrat, i θ₀ l'element de A definit per la igualtat:

${\displaystyle {\sqrt {n}}=f_{0}+{\frac {1}{\theta _{0}}}}$

El valor 1 / f_k+1 és la millor aproximació de θ_k i θ_k+1 és l'element de A que verifica la igualtat:

${\displaystyle \theta _{k}=f_{k+1}+{\frac {1}{\theta _{k+1}}}}$

Aquesta definició difereix lleugerament de la tradicional fracció continua, ja que f_k no s'escull necessàriament positiu. S'observa de f_k+1 i el major enter més petit que 1/θ_k. El fet que √n sigui irracional mostra que θ_k és sempre irracional, les successions (f_k) i (θ_k) no prenen mai el valor 0 i per estan així ben definides.

Siguin (c_k) i (d _k) les dues successions de Z tals que per a tot k ', c _k i c _d siguin primers entre ells i la fracció c _k / d _k sigui igual a la fracció reduïda d'índex k .

• Per a tot nombre enter k , si (α_k) i (β_k) designen les successions del mètode chakravala definides anteriorment, es verifiquen les igualtats següents:

${\displaystyle \forall k\in \mathbb {N} \quad \alpha _{k+1}=c_{k}+d_{k}\cdot {\sqrt {n}}\quad {\text{i}}\quad \theta _{k}=(-1)^{k+1}{\frac {\varphi (\beta _{k})}{{\mathcal {N}}(\alpha _{k})}}\;}$

Així, el mètode chakravala permet demostrar el caràcter periòdic i la propietat de palíndrom d'una fracció continua. Si l'algorisme recursiu imposa en la successió (β_k) ser també norma sistemàticament negativa, llavors les demostracions de l'article continuen sent vàlides i les fraccions contínues associades corresponen a la definició usual, és a dir que les successions (f_k) i (θ_k) són amb valors estrictament positius.

Demostració

Hi ha un lema que és útil per establir la proposició d'aquest paràgraf:

• La condició de congruència sobre β_k és equivalent al fet que per a tot k estrictament positiu m_k-1 + m_k sigui un múltiple de la norma de α_k.

En Altres paraules, es verifica l'equivalència següent:

${\displaystyle \forall k\in \mathbb {N} -\{0\}\quad a_{k}+b_{k}m_{k}\equiv 0\mod |{\mathcal {N}}(\alpha _{k})|\Leftrightarrow m_{k-1}+m_{k}\equiv 0\mod |{\mathcal {N}}(\alpha _{k})|}$

En efecte, a _k i b _k són primers entre ells, aquesta propietats és demostrada en el paràgraf sobre els lemes. La igualtat següent mostra que b _k i la norma de α_k són també primers entre ells:

${\displaystyle \forall k\in \mathbb {N} \quad a_{k}^{2}-n\cdot b_{k}^{2}={\mathcal {N}}(\alpha _{k})}$

L'element b _k és en conseqüència inversible a l'anell Z / N(_k) Z. Sigui g _k el seu invers. La condició de congruència és equivalent a la següent:

${\displaystyle a_{k}g_{k}+m_{k}\equiv 0\mod |{\mathcal {N}}(\alpha _{k})|}$

La proposició a demostrar és equivalent a una de les dues formes següents:

${\displaystyle a_{k}g_{k}\equiv m_{k-1}\mod |{\mathcal {N}}(\alpha _{k})|\quad {\text{o}}\quad a_{k}-b_{k}m_{k-1}\equiv 0\mod |{\mathcal {N}}(\alpha _{k})|}$

Aquí es reconeix la segona coordenada de l'element α_k φ(β_k-1), en efecte:

${\displaystyle \alpha _{k}\varphi (\beta _{k-1})=(a_{k}+b_{k}{\sqrt {n}})(m_{k-1}-{\sqrt {n}})=a_{k}m_{k-1}-nb_{k}+(b_{k}m_{k-1}-a_{k}){\sqrt {n}}\;}$

N'hi ha prou per tant amb demostrar que α_k φ(β_k-1) és un múltiple de la norma de α_k per establir el lema, o també, com que la norma de α_k és igual al producte α_k. φ(α_k), n'hi ha prou amb mostrar que φ(α_k-1) és un múltiple de φ(α_k). Una manera més simple de provar el lema és demostrar que β_k-1 és un múltiple de α_k. Les igualtats següents, procedents de la definició de α_k permeten concloure:

${\displaystyle \alpha _{k}={\frac {\alpha _{k-1}\beta _{k-1}}{|{\mathcal {N}}(\alpha _{k-1})|}}=\epsilon {\frac {\alpha _{k-1}\beta _{k-1}}{\alpha _{k-1}\varphi (\alpha _{k-1})}}=\epsilon {\frac {\beta _{k-1}}{\varphi (\alpha _{k-1})}}\quad {\text{i}}\quad \beta _{k-1}=\epsilon \alpha _{k}\varphi (\alpha _{k-1})\quad {\text{amb}}\quad \epsilon \in \{-1,1\}}$

• Per a tot nombre enter k, θ_k = (-1)^k+1 φ(β_k) / N(α_k):

Es demostra aquest resultat per inducció, sobre k.

Si k és igual a zero:

${\displaystyle {\sqrt {n}}=f_{0}+\theta _{0}=m_{0}-m_{0}+{\sqrt {n}}=m_{0}-{\frac {\beta _{0}}{1}}=m_{0}-{\frac {\varphi (\beta _{0})}{{\mathcal {N}}(\alpha _{0})}}\quad {\text{i}}\quad \theta _{0}=-{\frac {\varphi (\beta _{0})}{{\mathcal {N}}(\alpha _{0})}}\;}$

Suposant el resultat establert a l'ordre k - 1, es demostra que és verdader a l'ordre k.

${\displaystyle \theta _{k-1}=(-1)^{k}{\frac {\varphi (\beta _{k-1})}{{\mathcal {N}}(\alpha _{k-1})}}\quad {\text{per tant}}\quad {\frac {1}{\theta }}_{k-1}=(-1)^{k}{\frac {{\mathcal {N}}(\alpha _{k-1})}{\varphi (\beta _{k-1})}}=(-1)^{k}{\frac {{\mathcal {N}}(\alpha _{k-1})\cdot \beta _{k-1}}{\varphi (\beta _{k-1})\cdot \beta _{k-1}}}=(-1)^{k}{\frac {{\mathcal {N}}(\alpha _{k-1})\cdot (m_{k-1}+{\sqrt {n}})}{{\mathcal {N}}(\beta _{k-1})}}\;}$

Una igualtat establerta en el lema mostra que β_k-1 és igual al producte de +/-1, α_k i de φ(α_k-1), se'n dedueix:

${\displaystyle {\frac {1}{\theta _{k-1}}}=(-1)^{k}{\frac {{\mathcal {N}}(\alpha _{k-1})\cdot (m_{k-1}+{\sqrt {n}})}{{\mathcal {N}}(\alpha _{k-1}){\mathcal {N}}(\alpha _{k})}}=(-1)^{k}{\frac {m_{k}+m_{k-1}}{{\mathcal {N}}(\alpha _{k})}}+(-1)^{k+1}{\frac {m_{k}-{\sqrt {n}}}{{\mathcal {N}}(\alpha _{k})}}=(-1)^{k}{\frac {m_{k}+m_{k-1}}{{\mathcal {N}}(\alpha _{k})}}+(-1)^{k+1}{\frac {\varphi (\beta _{k})}{{\mathcal {N}}(\alpha _{k})}}\;}$

El lema mostra que m_k s'ha escollit de tal manera que (-1)^k(m_k + m_k+1)/ N(α_k) sigui un enter i (-1)^k+1.β_k-1 / N(α_k) de valor absolut el més petit possible.

• Per a tot nombre enter k, α_k+1 és igual a c_k + d_k√n:

Per simplificar els càlculs, es modifica lleugerament la definició de α_k. En aquesta demostració, α_k+1 es defineix com el producte: 1/N (α_k).α_k.β_k. Així, si la norma de α_k és negativa, llavors les dues coordenades de α_k+1 són negatives. S'observa immediatament que la modificació dels signes de les coordenades de la successió (α_k) no modifica ni la successió (β_k) ni els valors absoluts de les coordenades de la successió (α_k). L'objectiu és ara de demostrar, amb aquestes noves convencions que α_k = (-1)^k(c _k + d_k√n). Es disposa de les igualtats següents:

${\displaystyle \alpha _{k+1}={\frac {\beta _{k}}{\varphi (\alpha _{k})}},\;\alpha _{k}={\frac {\beta _{k-1}}{\varphi (\alpha _{k-1})}}\quad {\text{per tant}}\;\varphi (\beta _{k-1})\alpha _{k+1}=\beta _{k}\alpha _{k-1}\quad {\text{i}}\;\varphi (\beta _{k-1})(\alpha _{k+1}+\alpha _{k-1})=(\beta _{k}+\varphi (\beta _{k-1}))\alpha _{k-1}}$

Reemplaçant α_k-1 per un valor equivalent i β_k + φ(β_k+1) per les seves coordenades, s'obté:

${\displaystyle \varphi (\beta _{k-1})(\alpha _{k+1}+\alpha _{k-1})=(m_{k}+m_{k-1}){\frac {\varphi (\beta _{k-1})}{\varphi (\alpha _{k})}}\quad {\text{i}}\quad \alpha _{k+1}+\alpha _{k-1}={\frac {m_{k}+m_{k-1}}{{\mathcal {N}}(\alpha _{k})}}\alpha _{k}}$

Hom reconeix el terme f _k de la fracció continua calculada per a la demostració precedent. Si α'_k es defineix com a igual a -(1)^kα_k:

${\displaystyle (-1)^{k}{\frac {m_{k}+m_{k-1}}{{\mathcal {N}}(\alpha _{k})}}=f_{k}\quad {\text{per tant}}\quad \alpha '_{k+1}=f_{k}\cdot \alpha '_{k}+\alpha '_{k-1}\;}$

Es nota α’’_k = c _k+1 + d_k+1√n i α’’₀ = 1. Les successions (α’_k) i (α’’_k) són iguals per a k igual a 0 o a 1 i verifiquen totes dues la relació de recurrència

${\displaystyle \forall k\in \mathbb {N} -\{0,1\}\quad u_{k+1}=f_{k}\cdot u_{k}+u_{k-1}\;}$

Les dues successions (α’_k) i (α’’_k) són per tant sempre iguals. La successió (α_k) és igual a la

successió (α’_k) tret del signe. Ara bé tenen totes dues els coeficients sempre estrictament positius, la successió (α_k) és per tant igual a la successió (α’’_k), el que demostra la proposició.

Mètode de càlcul

L'enfocament per les fraccions contínues ofereix un enriquiment del mètode algorítmic precedent per a l'equació de Pell-Fermat o la determinació de la fracció continua. S'il·lustren aquests mètodes amb l'ajuda de l'exemple n = 313 i es mostra com Brouncker podia efectivament resoldre aquest desafiament en una hora o dues. Per definició α₀ és igual a 1 i α₁ = β₀ = 18 + √313 ja que 18² és la millor aproximació de 313 en els quadrats perfectes, la norma de α₁ és igual a 11. Se'n dedueix el valor de f ₀ = 18.

Per al càlcul de m₁, n'hi ha prou amb fixar-se que m₁ + m₀ és un múltiple d'11 i que m₁² és la millor aproximació possible de 313, es troba m '₁ = 15. Es calcula llavors la β₁ igual a 15² - 313 = -88. Per al càlcul de la norma de α₂ n'hi ha prou amb fixar-se que és el quocient de la de β₁ entre la de α₁, es troba -8. Per al càlcul de f ₁ s'utilitza la fórmula del paràgraf precedent, es troba f ₁ = - 1/11 (18 + 15) = -3.

Per al càlcul dels valors a_k i b_k, s'utilitza la fórmula de recurrència. Es construeix així el quadre següent:

Aquest enfocament permet evitar els grans nombres, excepte per a les columnes a _k i b _k. S'observa que

la norma de α₇ és la oposada de la de α₈, el que mostra que aquests dos nombres són tret d'un factor inversible la imatge per la funció φ l'un de l'altre. La successió de les normes és per tant 1, 11, -8, 3, 16, -9, 13, -13, 9, -16, -3, 8, -11, -1.

Se'n dedueix que 1/13.α₇.₈ és un element de norma -1:

${\displaystyle \alpha _{13}={\frac {1}{13}}\cdot \alpha _{7}\cdot \alpha _{8}=(19\,001+1\,074\cdot {\sqrt {3}}13)\cdot (43\,398+2\,453\cdot {\sqrt {3}}13)=126\,862\,368+7\;170\;685\cdot {\sqrt {3}}13}$

Cal encara elevar aquest nombre α₁₃ al quadrat per obtenir la solució cercada:

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

El mètode chakravala permet així resoldre a mà aquest tipus de càlcul, fins i tot si la solució s'expressa de manera una mica pesada. El mateix funcionament, sense el càlcul de les columnes a _k i b _k, inútil per a aquest objectiu, permet determinar la fracció continua √313. Cercar la solució tal que la successió (f _k) no implica més que valors positius suposa de restringir la tria als m _k inferiors o iguals a 17. Es troba: 17, 1, 2, 4, 11, 1, 1, 3, 2 que acaba aquesta branca del palíndrom. Se'n dedueix que els termes següents són: 2, 3, 1, 1, 11, 4, 2, 1. És relativament simple demostrar que el terme de després és necessàriament 34, el doble del primer terme. El que dona:

${\displaystyle {\sqrt {3}}13=[17,{\overline {1,2,4,11,1,1,3,2,2,3,1,1,11,4,2,1,34}}]}$

Referències

Notes

Referències

• (anglès) L E Dickson History of the theory of numbers vol. II, Diophantine analysis 1920 réimpression Dover Publications 2005 ISBN 0486442330
• (anglès) J. Stillwell Mathematics and its History Springer Science segona edició 2004 pàg. 72-74 ISBN 0387953361
• (francès) J. Trignan Fractions continues & Différences finies Éditions du Choix 1994 ISBN 2-909028-16-X
• (anglès) A. A. Krishnaswami Ayyangar New light on Bhaskaras Chakravala or cyclic method of solving indeterminate equations of the second Degree in two Variables Journal of the Indian Mathematical Society Vol. 18 1929-1930 pàgines 225-248

Enllaços externs

• (anglès) Analitza el contingut matemàtic del Âryabhatîya
• (anglès) Pell's equation del lloc web de La Universitat de St. Andrew
• (anglès) Introducció to chakravala Arxivat 2011-07-07 a Wayback Machine. sel lloc web de La Universitat de St. Andrew
• (francès) Joseph Louis Lagrange Solució d'un Problema d'Arithmetica: La solució original per les fraccions continues.