Voir la source de Méthode chakravala

En [[mathématiques]] et plus précisément en [[arithmétique]], la '''méthode ''chakravala''''' est un [[algorithme]] pour résoudre l'[[équation de Pell-Fermat]]. Cette équation est un exemple d'[[équation diophantienne]], c'est-à-dire à coefficients [[entier relatif|entiers]] et dont on cherche les solutions entières. Plus précisément, c'est l'équation
<center><math>x^2 -ny^2 = 1</math></center>
où ''n'' est un [[entier naturel]] non [[Carré parfait|carré]].

Cette méthode fut développée en [[Inde]] et ses racines peuvent être retracées jusqu'au {{VIe siècle}} avec [[Aryabhata]], suivi par [[Brahmagupta]]. Initiée par {{Lien|langue=en|trad=Jayadeva (mathematician)|fr=Jayadeva (mathématicien)|texte=Jayadeva}}, elle fut développée plus avant par [[Bhāskara II]].

Selenius l'évalue par : {{Citation| La méthode représente un algorithme de meilleure approximation de longueur minimale qui, en raison de plusieurs propriétés de minimisation, produit automatiquement […], à moindre coût […] et en évitant les grands nombres, les plus petites solutions de l'équation […] La méthode ''chakravāla'' précéda les méthodes européennes de plus de mille ans. Mais aucune performance européenne dans le champ entier de l'[[algèbre]], beaucoup plus tard après Bhāskara […], n'égala la merveilleuse complexité et l'ingéniosité de ''chakravāla''<ref name=Selenius>{{article|lang=en|prénom=Clas-Olof|nom=Selenius|titre=Rationale of the chakravāla process of Jayadeva and Bhāskara II|revue=[[Historia Mathematica]]|volume=2|année=1975|p.=167-184|url=http://www.sciencedirect.com/science/article/pii/0315086075901433/pdf?md5=78a3c5f68dacd76c61ffa232e5e5daa3&pid=1-s2.0-0315086075901433-main.pdf}}.</ref>.}}

Il faut en effet attendre le {{s-|XVII}} pour que les Européens, qui ignoraient les travaux des mathématiciens indiens, découvrent des algorithmes — moins performants<ref name=Selenius/> — résolvant le même problème.

[[Fichier:2064 aryabhata-crp.jpg|vignette|[[Aryabhata]] établit les fondements de la méthode ''chakravala''.]]

== Objectif ==
Une forme d'équation de Pell-Fermat s'exprime de la manière suivante :
<center><math>x^2 - ny^2 = 1,</math></center>
où ''n'' est un entier naturel non carré. L'équation est diophantienne ce qui signifie que les [[Couple (mathématiques)|couples]] {{nobr|(''x'', ''y'')}} recherchés sont des couples d'entiers.
Toutes les solutions s'expriment à partir du couple solution formé de deux entiers minimaux en [[valeur absolue]] dans l'ensemble des solutions. La méthode ''chakravala'' permet d'obtenir un couple de cette nature.

L'égalité suivante est un exemple de solution ; elle était connue des Indiens du {{s-|VII}}<ref>{{Ouvrage|langue=en|auteur1=[[Victor J. Katz]]|auteur2=[[Karen Parshall]]|titre=Taming the Unknown|éditeur=[[Princeton University Press|PUP]]|année=2014|pages totales=504|passage=122-123|isbn=978-1-4008-5052-5|lire en ligne=https://books.google.fr/books?id=nQLHAgAAQBAJ&pg=PA122}}.</ref> :
<center><math>1151^2-92\times 120^2=1.</math></center>

== Histoire ==
=== Mathématiques indiennes ===
Les [[mathématiques indiennes]] s'intéressent très tôt à l'arithmétique. [[Aryabhata]], un mathématicien du {{VIe siècle}}, en établit les bases. Il développe un [[système de numération]] montrant qu'il connaissait probablement la [[notation positionnelle]] ainsi que l'existence du ''zéro''<ref>[[Georges Ifrah]], ''Histoire universelle des chiffres : L'intelligence des hommes racontée par les nombres et le calcul'', Robert Laffont, 1994 {{ISBN|978-2-70284212-6}}.</ref>. Il travaille sur les équations diophantiennes et pour résoudre l'[[Théorème de Bachet-Bézout|identité de Bézout]], met au point un [[algorithme]] équivalent à celui [[algorithme d'Euclide|d'Euclide]] qu'il appelle ''ku{{prononciation API|ṭ}}{{prononciation API|ṭ}}aka'' (कूटटक) et qui signifie ''pulvérisateur'' car il casse les nombres en entiers plus petits. Il travaille aussi sur les [[fraction continue d'un nombre quadratique|fractions continues]]<ref>Une analyse précise de son œuvre mathématique est disponible dans la thèse de doctorat d'A. Keller, ''Un commentaire indien du {{s-|VII}} – Bhāskara et le ''ganita-pāda'' de l’''Āryabhatīya'' '' {{lire en ligne|url=http://halshs.ccsd.cnrs.fr/docs/00/04/96/19/PDF/Analyse.pdf}}.</ref>.

Le mathématicien indien [[Brahmagupta]] <small>([[598]] – [[668]])</small> semble être le premier à analyser en profondeur cette question. Il comprend comment, à partir de deux solutions, il est possible d'en construire une nouvelle. En réitérant, il obtient ainsi un nombre de solutions distinctes aussi élevé que souhaité. Cette méthode est appelée ''samasa'' par les mathématiciens indiens<ref>{{Stillwell}}, 2010, {{p.|75-80}}.</ref>. Brahmagupta en déduit trois algorithmes. Le premier lui permet de trouver une solution s'il dispose d'un couple d'entiers (''x'', ''y'') dont l'image par l'équation est –1. Il en trouve un deuxième traitant le cas où l'image est 2 en [[valeur absolue]]. Il en trouve un troisième donnant le même résultat si l'image est égale à ±4. Une ébauche de méthode voit le jour. Elle commence par un tâtonnement jusqu'à trouver un couple ayant pour image 1, 2 ou 4 en valeur absolue, elle continue par l'un des trois algorithmes<ref>{{en}} [[Bartel Leendert van der Waerden|B. L. van der Waerden]], ''Pell's Equation in Greek and Hindu Mathematics'', Russ. Math Surveys '''31''' (5), 1976, {{p.|210-225}}</ref>. Brahmagupta l'utilise en 628 dans son livre ''Brahmasphuta siddhanta'' pour résoudre l'équation suivante<ref name="Pell">{{MacTutor|class=~history/HistTopics|id=Pell|title=Pell's equation}}</ref> :

<center><math>x^2 - 83y^2 = 1.</math></center>
Cette approche est insuffisante pour traiter les cas complexes, il peut être difficile de trouver par tâtonnement un couple donnant une des six valeurs qui permettent de conclure. Au {{s|XII}}, [[Bhāskara II]] s'inspire de traités antérieurs et propose la forme définitive de la méthode ''chakravala''. Elle correspond à l'adjonction d'un algorithme cyclique, c'est-à-dire donnant une [[suite périodique]] de couples contenant nécessairement une solution. L'algorithme cyclique est équivalent à celui des [[fraction continue|fractions continues]]. La méthode ''chakravala'' termine par les calculs de Brahmagupta si l'une des valeurs –1, ±2 et ±4 apparaît. Bhāskara II l'utilise en 1150 dans son traité ''Bijaganita''<ref name="Pell"/> pour trouver une solution minimale à l'équation suivante déjà trouvée par Brahmagupta :
<center><math>x^2 - 61y^2 = 1.</math></center>
Le couple solution trouvé est :
<center><math>x= 1\, 766 \, 319 \, 049\quad \text{et}\quad y = 226\, 153\, 980.</math></center>

Il est peu probable que Bhāskara II ait démontré le fait que l'algorithme offre toujours une solution, c'est-à-dire pour n'importe quelle valeur de ''n'' car la démonstration, longue et technique, demande une sophistication de loin supérieure aux mathématiques du {{s-|XII}}<ref name="Pell"/>.
De nouveaux exemples sont traités plus tard, par les mathématiciens indiens. Au {{s|XIV}} un mathématicien du nom de Narayana étudie le cas où ''n'' est égal à 103 dans ses commentaires sur le livre ''Bijaganita'' de Bhāskara II.

=== Europe ===
En février [[1657]] (à la suite d'un autre défi plus célèbre datant du 3 janvier de la même année<ref>Voir la [http://www.beaumont-de-lomagne.fr/fr/pierre-fermat/ses-correspondances.html page Pierre Fermat] sur le site de la commune de [[Beaumont-de-Lomagne]].</ref>), [[Pierre de Fermat]] défie [[Bernard Frénicle de Bessy]]<ref>''[https://archive.org/stream/oeuvresdefermat02ferm#page/334/mode/2up Œuvres de Fermat]'', {{p.|334}}.</ref> et, à travers lui tous mathématiciens européens, de résoudre (entre autres) le problème pour ''n'' = 61. La réaction des Anglais est rapide : [[William Brouncker]] trouve un algorithme. Frénicle de Bessy propose alors une table contenant toutes les solutions pour les valeurs de ''n'' inférieures à 150, qui sera finalement perdue, puis [[John Wallis]] redécouvre les résultats de Brahmagupta et les démontre rigoureusement. Frénicle de Bessy défie Brouncker avec la valeur ''n'' = 313 ; il reçoit en réponse non seulement la solution mais l'affirmation que son auteur n'a pas eu besoin de plus « d'une heure ou deux » pour trouver<ref>Ces informations sont tirées des échanges épistolaires entre les différents acteurs, publiés dans {{la}} John Wallis, {{Lang|la|''Commercium epistolicum de quæstionibus quibusdam mathematicis nuper habitum'' Oxonii : Excudebat A. Lichfield, Impensis Tho. Robinson}}, 1658</ref>.

Les deux questions théoriques sous-jacentes, à savoir si pour tout entier naturel ''n'' non carré il existe une solution et si la solution trouvée engendre bien toutes les autres, sont finalement résolues par [[Joseph-Louis Lagrange|Lagrange]] en 1767<ref>[[Joseph-Alfred Serret]], ''Œuvres de Lagrange'', [http://gdz.sub.uni-goettingen.de/no_cache/dms/load/img/?IDDOC=41029 vol. I, {{p.|671-731}}] : « Solution d'un problème d'arithmétique ».</ref>, par un algorithme moins performant que celui — alors ignoré des Européens — dû à Bhāskara, mais dont la correction est plus simple à démontrer. En 1930, {{Lien|langue=en|fr=A. A. Krishnaswami Ayyangar}} affirme être le premier à prouver celle de ''chakravala''<ref>{{Article|lang=en|prénom=A. A. Krishnaswami|nom=Ayyangar|titre=New light on Bhaskara's Chakravala or cyclic method of solving indeterminate equations of the second degree in two variables|revue=J. [[Indian Mathematical Society|Indian Math. Soc.]]|vol=18|année=1929-30|p.=225-248|url=http://www.ms.uky.edu/~sohum/aak/pdf%20files/chakravala.pdf}}.</ref>.

== Apports de Brahmagupta ==
=== Décors ===
Les méthodes proposées ici utilisent la puissance du formalisme actuel. Si le contenu mathématique est analogue à celui de Brahmagupta, les techniques d'exposition ainsi que les démonstrations ne reflètent pas la pensée du mathématicien indien.
Les notations suivantes sont utilisées dans tout le reste de l'article. On considère l'équation diophantienne suivante, où ''n'' est un entier naturel non carré :
<center><math>(1) \quad x^2 - ny^2 = 1.</math></center>
Soient ''A'' l'[[anneau unitaire|anneau]] des nombres de la forme ''a'' + ''{{racine|n}}b'', où ''a'' et ''b'' désignent deux nombres entiers, ''N'' l'application qui à un élément de ''A'' associe sa « [[Entier quadratique#Conjugué et norme|norme]] » et φ l'application qui à un élément de ''A'' associe son « [[Entier quadratique#Conjugué et norme|conjugué]] » :
<center><math>\mathcal N(a+\sqrt n b)=a^2-nb^2,\quad\varphi(a+\sqrt n b)=a-\sqrt n b.</math></center>

La fonction ''N'' correspond à la [[norme (arithmétique)|norme]] de ''A'' au sens de la [[théorie algébrique des nombres]]. Un élément ''a'' + ''{{racine|n}}b'' de ''A'' est appelé '''racine''' de l'équation (1) si et seulement si sa norme vaut 1, c'est-à-dire si (''a'', ''b'') est solution de (1).

La fonction φ possède aussi d'utiles propriétés. C'est un [[Morphisme d'anneaux#Composition de morphismes|automorphisme]] de ''A'' :
<center><math display="inline">\forall \alpha, \beta \in A \quad \varphi (\alpha+\beta) = \varphi (\alpha)+\varphi (\beta),\quad\varphi(\alpha\beta) = \varphi(\alpha)\varphi(\beta),\quad \varphi(1)=1.</math></center>

La conjugaison φ est [[involution (mathématiques)|involutive]] c'est-à-dire que composée deux fois de suite avec elle-même, elle est égale à l'identité, ou encore sa [[bijection réciproque]] est égale à elle-même :
<center><math>\forall \alpha \in A \quad (\varphi\circ\varphi)(\alpha)= \alpha.</math></center>

Enfin, le produit de deux éléments conjugués est égal à leur norme commune :
<center><math>\forall \alpha \in A \quad \mathcal N(\alpha) = \alpha\varphi(\alpha).</math></center>
Si l'on note α = ''a'' + ''{{racine|n}}b'', cela est justifié par le calcul suivant :
<center><math>\mathcal N(\alpha) = a^2 - nb^2 = (a + \sqrt n b)(a - \sqrt nb) = \alpha\varphi(\alpha).</math></center>

=== Samasa ===
{{Article détaillé|Identité de Brahmagupta}}

La première propriété utilisée est la suivante :
{{énoncé|Soit α et β deux éléments de ''A'', alors :
<center><math>\mathcal N(\alpha\beta) = \mathcal N(\alpha)\mathcal N(\beta).</math></center>}}

Si α = ''a''<sub>1</sub> + ''{{racine|n}}a''<sub>2</sub> et β = ''b''<sub>1</sub> + ''{{racine|n}}b''<sub>2</sub>, cette égalité s'écrit :
<center><math>(a_1b_1 + na_2b_2)^2 - n(a_1b_2+a_2b_1)^2 = (a_1^2 - na_2^2)(b_1^2 - nb_2^2).</math></center>

Cette égalité, connue sous le nom d'[[identité de Brahmagupta]], était appelée ''Samasa'' par les Indiens. Pour se convaincre de son exactitude, il suffit d'exprimer ''N'' en fonction de l'automorphisme φ :
<center><math>\mathcal N(\alpha\beta) = \alpha \beta\varphi (\alpha \beta) = \alpha\varphi (\alpha)\beta \varphi(\beta) = \mathcal N(\alpha)\mathcal N(\beta).</math></center>

Un cas particulier correspond à celui où β est un entier ''k'', l'égalité prend la forme suivante :

{{énoncé|Soit α un élément de ''A'' et ''k'' un entier, alors :
<center><math>\mathcal N(k \alpha) = \mathcal N(k)\mathcal N(\alpha)= k^2\mathcal N(\alpha).</math></center>}}

=== Conséquences ===
{{énoncé|1=
*Soit α un élément de ''A'' de norme 1, alors φ(α) est inverse de α et de norme 1.
*Si l'équation (1) admet une solution différente de ±1, alors elle admet une infinité de solutions distinctes.}}
En effet, ''N''(α) = ''N''(φ(α)) = αφ(α), et si α est une solution de (1) alors α{{exp|''k''}} aussi pour tout entier naturel ''k'' (car la norme d'un produit est égale au produit des normes), or les puissances d'un réel différent de 0, 1 et –1 sont toutes distinctes.

Comprendre comment fait Brahmagupta pour résoudre l'équation (1) dépend de trois propositions :
{{énoncé|1=Soit α un élément de A.
#Si ''N''(α) = ±1 alors α{{2}} est une solution de (1).
#Si ''N''(α) = ±2 alors α{{2}}/2 est une solution de (1).
#Si ''N''(α) = 4ε avec ε = ±1 alors une solution de (1) est :
#*si α est divisible par 2 : (α/2){{exp|(3–ε)/2}} ;
#*si ''n'' est pair<ref>Ce cas, appliqué à α = (10 + {{sqrt|92}}){{2}}/4 = 48 + 5{{sqrt|92}}, de norme 8{{2}}/4{{2}} = 4, permet à Brahmagupta de résoudre [[#Objectif|son premier exemple]] : {{Harvsp|Stillwell|p=[https://books.google.fr/books?id=V7mxZqjs5yUC&pg=PA77 77]}}.</ref> : α{{2}}/4 ;
#*sinon : (α{{3}}/8){{exp|(3–ε)/2}}.
}}

{{Démonstration/début}}
# : immédiat.
# : si α = ''a'' + ''b{{racine|n}} ''alors α<sup>2</sup> = ''a''<sup>2</sup> + ''nb''<sup>2</sup> + 2''ab{{racine|n}} = N''(α) + 2''nb''<sup>2</sup> + 2''ab{{racine|n}}'' est divisible par 2 (et 2{{2}}''N''(α{{2}}/2) = ''N''(α{{2}}) = (±2){{2}} donc ''N''(α{{2}}/2) = 1).
# : les deux premiers cas sont immédiats et dans le troisième, ''n'', ''a'' et ''b'' sont impairs, si bien que α{{3}} est divisible par 8 car<center><math>\begin{align}\alpha^3&=(a+b\sqrt n)^3=a^3+3ab^2n+\sqrt n(nb^3+3a^2b)=a(a^2-nb^2+4nb^2)+b\sqrt n(3a^2-3nb^2+4nb^2)\\&=a\left(\mathcal N(\alpha)+4nb^2\right)+b\sqrt n\left(3\mathcal N(\alpha)+4nb^2\right)=4a\left(\varepsilon+nb^2\right)+4b\sqrt n\left(3\varepsilon+nb^2\right)\quad\text{avec}\quad\varepsilon=\pm1.\end{align}</math></center>
{{Démonstration/fin}}

=== Exemples ===
==== Exemple de Brahmagupta ====
Traitons avec cette méthode l'exemple de Brahmagupta suivant :
<center><math>x^2 - 83y^2 = 1.</math></center>
Soit α = ''m'' + {{racine|83}}, l'entier ''m'' étant choisi tel que la norme ''N''(α) = ''m''{{2}} – 83 soit la plus petite possible en valeur absolue : ''m'' = 9, α = 9 + {{racine|83}}, ''N''(α) = –2. Une proposition précédente montre que α{{2}}/2 est une solution. Effectivement :
<center><math>\alpha^2 = (9^2 + 83\cdot 1) + \sqrt{83}\cdot 2\times 9 \times 1 = 164 +\sqrt{83}\cdot 18 = 2\left(82 +\sqrt{83} \cdot 9\right)</math></center>
et
<center><math>82^2 - 83\times 9^2 = 6\,724- 6\,723 = 1.</math></center>

==== Défi de Fermat ====
Le défi de Fermat se résout de la même manière :
<center><math>x^2 - 61y^2 = 1.</math></center>

Brahmagupta s'y prend de la manière suivante : il remarque que si α = 39 + 5{{racine|61}} alors ''N''(α) est égal à –4. Bien évidemment le formalisme de Brahmagupta n'a rien à voir avec celui utilisé ici, même si les calculs sont les mêmes. Il calcule α<sup>2</sup>/2 :
<center><math>\frac{\alpha^2}2 = \frac 12 (39 + 5\sqrt{61})^2 = \frac 12 (39^2 + 5^2\times 61 + 2\times 5 \times 39\sqrt{61}) = 1\,523 + 195\sqrt{61}.</math></center>

Puis il calcule α<sup>3</sup>/8 et sa norme :
<center><math>\frac{\alpha^3}{8} = \frac 14 (39 + 5\sqrt{61})(1\,523 + 195\sqrt{61}) = 29\,718 + 3\,805\sqrt{61}\quad \text{et}\quad \mathcal N (\frac{\alpha^3}8) = 29\,718^2 - 61\times 3\,805^2 = -1.</math></center>

La solution est donc α<sup>6</sup>/64, soit :
<center><math>\frac{\alpha^6}{64}=(29\,718 + 3\,805\sqrt{61})^2 = 29\,718^2 + 61\times 3\,805^2 + 2\times 29\,718\times 3\,805\sqrt{61} = 1\,766\,319\,049 + 226\,153\,980\sqrt{61}.</math></center>

La méthode est remarquablement économique pour un algorithme aussi ancien.

== Apport de Bhāskara II ==
=== Principe de la méthode ===
Une difficulté de la méthode de Brahmagupta réside dans le fait qu'il n'est pas toujours simple de trouver un nombre α de ''A'' dont la norme soit égale à ±1, ±2 ou ±4. L'apport de Bhāskara II décrit dans le ''Siddhanta Siroman'' consiste à enrichir la méthode d'un algorithme qui finit infailliblement par fournir une « quasi-solution » de cette nature.

Bhāskara II [[Suite définie par récurrence|construit par récurrence une suite]] d'éléments α''{{ind|j}} = a{{ind|j}} + b{{ind|j}}{{sqrt|n}}'' de ''A'' de la manière suivante. Le premier élément de la suite est α{{ind|0}} = 1, de norme ''k''{{ind|0}} = 1. Supposons la suite définie à l'ordre ''j''. On construit un élément β<sub>''j''</sub> = ''m{{ind|j}} + {{racine|n}}''. L'entier naturel<ref>{{Ouvrage|langue=en|prénom1=Harold|nom1=Edwards|lien auteur1=Harold Edwards|titre=Fermat's Last Theorem : A Genetic Introduction to Algebraic Number Theory|éditeur=Springer|collection=[[Graduate Texts in Mathematics|GTM]]|numéro dans collection=50|année=2000|numéro d'édition=3|pages totales=407|passage=25-36|isbn=978-0-387-95002-0|lire en ligne=https://books.google.fr/books?id=_IxN-5PW8asC&pg=PA25|numéro chapitre=I, § 9|titre chapitre=Pell's equation }}.</ref> ''m{{ind|j}}'' est tel que ''a{{ind|j}} + m{{ind|j}}b{{ind|j}} ''soit multiple de la norme ''k{{ind|j}}'' de α{{ind|''j''}} — autrement dit tel que ''b{{ind|j}}m{{ind|j}}'' soit [[Congruence sur les entiers|congru à –''a{{ind|j}}'' modulo ''k{{ind|j}}'']] — et ''m<sub>j</sub> ''minimise la valeur absolue de la norme ''m{{ind|j}}''{{2}} – ''n'' de β{{ind|''j''}}. L'élément α<sub>''j ''+ 1</sub> est alors défini par
<center><math>\alpha_{j+1}=a_{j+1}+b_{j+1}\sqrt n=\frac{\alpha_j\beta_j}{|\mathcal N(\alpha_j)|}=\frac{a_jm_j + nb_j + \sqrt n(a_j + m_jb_j)}{|\mathcal N(\alpha_j)|}</math></center>
ou encore
<center><math>\alpha_{j+1}\varphi(\alpha_j)=\pm\beta_j,</math></center>
le ± correspondant au signe de ''N''(α''{{ind|j}}'') {{---|l'avantage de prendre en compte ce signe<ref>{{Harvsp|Selenius|1975}} ajoute cette valeur absolue au dénominateur, tout en précisant à deux reprises que Bhāskara ne le faisait pas. {{Harvsp|Edwards|2000}} intègre cette valeur absolue dans sa formulation, sans même cette précision.</ref> est qu'ainsi, ''a{{ind|j}}'' et ''b{{ind|j}}'' sont toujours positifs|stop}}.

On verra [[#Lemme|plus loin]] que la condition « ''a{{ind|j}} + m{{ind|j}}b{{ind|j}}'' multiple de ''k{{ind|j}}'' » équivaut à « ''m{{ind|j}}'' congru à –''m''{{ind|''j''–1}} modulo ''k{{ind|j}}'' », ce qui simplifie l'algorithme.

=== Exemples ===
==== Défi de Fermat ====
Choisissons encore ''n'' égal à 61<ref>{{en}} {{Harvsp|Stillwell|p=[https://books.google.fr/books?id=V7mxZqjs5yUC&pg=PA79 79]}}.</ref>. La valeur de ''m''{{ind|0}} est égale à 8 pour minimiser |''N''(β{{ind|0}})|. En effet, {{sqrt|61}} est compris entre 7 et 8 et 8{{2}} – 61 = 3 < 61 – 7{{2}}. L'entier ''m''{{ind|1}} est ensuite choisi parmi ceux congrus, modulo ''N''(α{{ind|1}}) = ''N''(8 + {{sqrt|61}}) = 8{{2}} – 61 = 3, à –''m''{{ind|0}} = –8 donc à 1. Des deux termes consécutifs 7 et 10 de cette [[suite arithmétique]] qui encadrent {{sqrt|61}}, celui qui minimise |''N''(β{{ind|1}})| est ''m''{{ind|1}} = 7, ce qui donne :
<center><math>\alpha_2 = \frac {8\times 7 + 61}3+ \frac{8 + 7}3\sqrt{61} = 39 + 5\sqrt{61} \quad \text{et}\quad \mathcal N(\alpha_2) = -4.</math></center>

La suite de la méthode est [[#Défi de Fermat|celle de Brahmagupta]]. La méthode ''chakravala'' permet maintenant de résoudre sans tâtonnement et avec un minimum de calcul le défi de Fermat.

==== Exemple de Narayana ====
Ce deuxième exemple est aussi extrait du ''Siddhanta Siroman'' de Bhāskara II, annoté par Narayana. Pour ''n'' = 103, ''m''{{ind|0}} = 10. L'entier ''m''{{ind|1}} est ensuite choisi congru à –10 modulo ''N''(α{{ind|1}}) = ''N''(10 + {{sqrt|103}}) = 10{{2}} – 103 = –3. Comme 8 < {{sqrt|103}} < 11 et 11{{2}} – 103 = 18 < 103 – 8{{2}}, on obtient ''m''{{ind|1}} = 11 et
<center><math>\alpha_2 = \frac {10\times 11 + 103}{3} + \frac{10 + 11}{3}\sqrt{103} = 71 + 7\sqrt{103} \quad \text{et}\quad \mathcal N(\alpha_2) = -6.</math></center>
On choisit ensuite ''m''{{ind|2}} congru à –11 modulo 6. Comme 7 < {{sqrt|103}} < 13 et 103 – 7{{2}} = 54 < 13{{2}} – 103, on obtient ''m''{{ind|2}} = 7 {{---|remarquons à cette occasion que « minimiser {{!}}''m''{{2}} – ''n''{{!}} » ne coïncide pas toujours avec « minimiser {{!}}''m – {{sqrt|n}}''{{!}} »}} puis
<center><math>\alpha_3 = 203 + 20\sqrt{103} \quad \text{et}\quad \mathcal N(\alpha_3) = 9.</math></center>
Puis, modulo 9, ''m''{{ind|3}} doit être congru à –7. Pour minimiser |''N''(β{{ind|3}})|, il faut choisir ''m''{{ind|3}} égal à 11. On obtient
<center><math>\alpha_4 = 477 + 47\sqrt{103} \quad \text{et}\quad \mathcal N(\alpha_4) = 2.</math></center>

Le calcul de Brahmagupta permet de conclure : la valeur cherchée est
<center><math>\frac{\alpha_4^2}2=\frac{(477 + 47\sqrt{103})^2}2 = 227\,528 + 22\;419\sqrt{103}.</math></center>

==== Non-unicité ====
L'exemple suivant montre que le nombre [[#Principe de la méthode|α{{ind|''j''+1}} défini à partir de α{{ind|''j''}}]] n'est pas toujours unique : pour ''n'' = 58, α{{ind|1}} est égal à 8 + {{sqrt|58}}, de norme 6 puis, pour ''m''{{ind|1}} congru à –2 modulo 6, le minimum de {{nobr|{{!}}''m''{{ind|1}}{{2}} – 58{{!}}}} est 42, atteint pour les deux valeurs 4 et 10 de ''m''{{ind|1}}. Les deux valeurs correspondantes pour α{{ind|2}} sont 15 + 2{{sqrt|58}}, de norme –7, et 23 + 3{{sqrt|58}}, de norme 7. Cependant, pour la première on trouve ensuite {{nobr|1=''m''{{ind|2}} = 10}} et pour la seconde, ''m''{{ind|2}} = 4 donc pour les deux, α{{ind|3}} = 38 + 5{{sqrt|58}}, de norme –6, puis ''m''{{ind|3}} = 8 et α{{ind|4}} = 99 + 13{{sqrt|58}}, de norme –1. La bifurcation n'était donc que passagère et les deux suites donnent la même solution.

== Démonstrations associées à l'apport de Bhāskara II ==
=== Lemme ===
Un lemme démontre l'existence de la suite utilisée par Bhāskara II, sachant que si ''k'' et ''b'' sont des [[nombres premiers entre eux]] alors pour tout entier ''a'', il existe des entiers ''m'' pour lesquels {{nobr|''a + bm''}} est divisible par ''k''. En effet, en résolvant l'[[Théorème de Bachet-Bézout|identité de Bézout]] — ce que les Indiens savaient déjà faire avec l'[[algorithme d'Euclide]] — on trouve des entiers ''v'' pour lesquels 1 – ''bv'' est multiple de ''k'', et il suffit alors de poser ''m = –av''.

{{énoncé|1=Soient ''a'', ''b'' premiers entre eux et ''m'', ''n'' deux entiers quelconques. On pose ''k = a''{{2}} – ''nb''{{2}}, ''c = am + bn'' et ''d = a + bm''.

Si ''d'' est multiple de ''k'' alors ''c'' aussi, et les deux entiers ''c''/''k'' et ''d''/''k'' sont premiers entre eux.}}

Ce lemme est immédiat en remarquant que ''ad – bc = k'' et que ''b'' est premier avec ''k''. Appliqué — avec les notations du [[#Principe de la méthode|§ « Principe de la méthode »]] — à ''a = a{{ind|j}}'' et ''b = b{{ind|j}}'', il montre qu'à chaque étape de la construction de la suite (α{{ind|''j''}}), si ''m{{ind|j}}'' est choisi selon la méthode indiquée alors α{{ind|''j''}}β{{ind|''j''}} est un multiple de ''N''(α{{ind|''j''}}), α{{ind|''j''+1}} est un élément de ''A'' et ''a''{{ind|''j''+1}} et ''b''{{ind|''j''+1}} sont premiers entre eux, ce qui permet d'itérer la construction.

On peut remarquer de plus que la contrainte (dans le choix de ''m{{ind|j}}'') « ''a{{ind|j}} + b{{ind|j}}m'' divisible par ''N''(α{{ind|''j''}}) » est équivalente à « ''m'' congru à –''m''{{ind|''j''–1}} modulo ''N''(α{{ind|''j''}}) ». En effet, ''b{{ind|j}}'' est premier avec ''N''(α{{ind|''j''}}) et ''a{{ind|j}} + b{{ind|j}}''(–''m''{{ind|''j''–1}}) est divisible par ''N''(α{{ind|''j''}}) puisque φ(α{{ind|''j''}})β{{ind|''j''–1}} = ±''N''(α{{ind|''j''}})φ(α{{ind|''j''–1}}).

=== Caractère cyclique ===
Une fois montré que la suite (α<sub>''j''</sub>) est bien définie, étudions son comportement. Elle est « cyclique » en un certain sens. Plus précisément, en notant '''cl'''(α) la [[Relation d'équivalence|classe d'équivalence]] de α pour la relation « être [[Éléments associés dans un anneau|associés]] » (c'est-à-dire multiple l'un de l'autre par un [[élément inversible]] — si bien que tous les éléments d'une classe ont même norme en valeur absolue), la suite ('''cl'''(α<sub>''j''</sub>)) est [[Suite périodique|périodique]] à partir d'un certain rang. Cette propriété est la conséquence immédiate de trois propositions :
{{énoncé|1=
#La suite ({{!}}''N''(α<sub>''j''</sub>){{!}}) est majorée par {{sqrt|''n''}}<ref>La méthode chakravala est, en cela aussi, supérieure à celles d'Euler et de Brouncker : en plus d'atteindre le résultat en moins d'étapes, elle met en jeu des calculs sur des nombres plus petits {{Harv|Selenius|1975}}.</ref>.
#Pour tout réel ''C'' > 0, il n'existe qu'un nombre fini de classes d'équivalence de norme en valeur absolue inférieure à ''C''.
#Si, pour deux indices ''i'' et ''j'', α{{ind|''i''}} = εα{{ind|''j''}} avec ε inversible dans ''A'', alors α{{ind|''i''+1}} = εα{{ind|''j''+1}}.
}}

{{Démonstration/début}}
* '''''k{{ind|j}}'' := |''N''(α<sub>''j''</sub>)| < {{sqrt|''n''}} :''' montrons-le par récurrence. On a bien ''k''{{ind|0}} = 1 < {{sqrt|''n''}}. Supposons que ''k{{ind|j}}'' < {{sqrt|''n''}}. Alors, il existe un entier ''m'' (nécessairement positif) tel que ''m < {{sqrt|n}} < m + k{{ind|j}}'' et tel que ''m{{ind|j}}'' soit égal à ''m'' ou à ''m + k{{ind|j}}'', selon que ''n – m''{{2}} est inférieur ou supérieur à (''m + k{{ind|j}}''){{2}} – ''n'', autrement dit selon que ''m''{{2}} + ''k{{ind|j}}m'' + ''k{{ind|j}}''{{2}}/2 – ''n'' est positif ou négatif. Par comparaison de ''m'' avec la racine positive de ce [[polynôme du second degré]], on en déduit facilement que dans les deux cas, |''m{{ind|j}}''{{2}} – ''n''| ≤ ''k{{ind|j}}''{{sqrt|''n'' – ''k{{ind|j}}''{{2}}/4}} < ''k{{ind|j}}{{sqrt|n}}'', d'où ''k''{{ind|''j''+1}} = |''m{{ind|j}}''{{2}} – ''n''|/''k{{ind|j}}'' < {{sqrt|''n''}}.
* '''Il n'existe qu'un nombre fini de classes d'équivalences de norme en valeur absolue inférieure à ''C'' :''' il suffit de montrer que pour tout entier ''N'' > 0, il n'existe qu'un nombre fini de classes de norme en valeur absolue égale à ''N''. Pour cela, remarquons d'abord que deux éléments ont même classe si et seulement si l'[[idéal principal]] qu'ils engendrent est le même, et que tout idéal engendré par un élément dont la valeur absolue de la norme vaut ''N'' est un sous-groupe additif de ''A'' contenant ''NA''. Il suffit donc de prouver que les sous-groupes additifs de ''A'' contenant ''NA'' sont en nombre fini. Or ils sont en bijection avec les sous-groupes du [[groupe quotient]] ''A''/''NA'', qui est fini (de cardinal ''N''<sup>2</sup>), ce qui conclut.
* '''Si α{{ind|''i''}} = εα{{ind|''j''}} avec ε inversible dans ''A'' alors α{{ind|''i''+1}} = εα{{ind|''j''+1}}''' car |''N''(α{{ind|''i''}})| = |''N''(α{{ind|''j''}})| et les β divisibles par φ(α{{ind|''i''}}) {{---|qui sont les mêmes que ceux divisibles par φ(α{{ind|''j''}})}} vérifient α{{ind|''i''}}β = εα{{ind|''j''}}β.
{{Démonstration/fin}}

Ces propriétés ne démontrent que la périodicité à partir d'un certain rang. Le paragraphe suivant {{Douteux|date=mai 2014|montre}} que ce rang est 0.

=== Structure de la suite ===
Le fait que la suite soit périodique n'indique a priori pas qu'elle atteint un point de norme égale à 1 en valeur absolue. Tel est pourtant toujours le cas :
{{énoncé|1=
*Il existe un indice ''j'' > 0 tel que ''N''(α<sub>''j''</sub>) = ±1 (donc ''N''(α<sub>2''j''</sub>) = 1).
*La suite ('''cl'''(α{{ind|''k''}})) forme un « [[palindrome]] à conjugaison près » : '''cl'''(α{{ind|''j''–1}}) = '''cl'''(φ(α{{ind|1}})), '''cl'''(α{{ind|''j''–2}}) = '''cl'''(φ(α{{ind|2}})){{etc.}}
}}
{{Démonstration/début|titre=Démonstration partielle}}
Soient ''B'' l'ensemble des éléments ''a + b{{sqrt|n}}'' de ''A'' pour lesquels ''a'' et ''b'' sont premiers entre eux, et ψ la fonction de ''B'' dans ''B'' définie par : à un élément α de ''B'' on associe un élément β de forme ''m'' + {{racine|''n''}} avec ''m'' entier naturel tel que βα soit un multiple de la norme de α, de norme minimale (on a vu [[#Non-unicité|plus haut]] qu'il pouvait y en avoir deux : on peut par exemple<ref>{{Harvsp|Edwards|2000|p=35}}.</ref> choisir systématiquement dans ce cas celui qui correspond à la plus petite des deux valeurs de ''m''), puis on pose ψ(α) = αβ/|''N''(α)|. Le lemme et le paragraphe précédent montrent que l'application ψ est bien définie et que
<center><math>\forall k\in\N,\quad \psi(\alpha_k) = \alpha_{k+1}.</math></center>

Cette fonction possède une symétrie par rapport à la fonction φ :
:* '''La propriété suivante est vérifiée :'''
<center><math>\forall \alpha, \gamma \in B\quad \psi (\alpha) = \gamma \Rightarrow \psi(\varphi(\gamma))=\pm\varphi(\alpha).</math></center>
Plus précisément : ψ(φ(γ)) = ε{{ind|1}}ε{{ind|2}}φ(α), où ε{{ind|1}} (resp. ε{{ind|2}}) désigne le signe de la norme de α (resp. γ).

En effet, si α possède pour image par ψ la valeur γ, il existe un unique élément β de la forme ''m'' + {{racine|''n''}} avec ''m'' entier naturel tel que
<center><math> \gamma = \frac {\alpha\beta}{|\mathcal N (\alpha)|} = \epsilon_1\frac {\alpha\beta}{\alpha\varphi(\alpha)}=\epsilon_1 \frac {\beta}{\varphi(\alpha)} \quad \text{et}\quad (1) \quad \varphi(\alpha) = \epsilon_1 \frac {\beta}{\gamma} =\epsilon_1\epsilon_2 \frac {\varphi(\gamma)\beta}{|\mathcal N (\varphi(\gamma))|}.</math></center>
L'élément β est bien de la forme ''m'' + {{racine|''n''}} avec ''m'' entier naturel tel que βφ(γ) est un multiple de la norme de φ(γ), car φ(α) appartient à ''A''. Soit β' un élément vérifiant ces propriétés et de norme inférieure à β, {{Douteux|date=mai 2014|l'égalité γ {{=}} αβ'/''N''(β') montre que β' est de norme supérieure à β}}. On en déduit que les normes de β et β' sont égales et son caractère minimal est vérifié. L'égalité (1) montre alors que ε{{ind|1}}ε{{ind|2}}φ(α) est bien l'image de φ(γ) par ψ. {{Douteux|date=mai 2014|La proposition est démontrée.}}

On en déduit que la fonction ψ est une bijection de ''B'' dans ''B''.

:* '''Il existe un indice ''j'' > 0 tel que ''N''(α<sub>''j''</sub>) = ±1 :'''
D'après le § « Caractère cyclique » précédent, il existe deux indices 0 ≤ ''k < k + j'' tels que '''cl'''(α{{ind|''k+j''}}) = '''cl'''(α{{ind|''k''}}). Par la bijectivité de ψ {{Douteux|date=mai 2014|démontrée ci-dessus}}, on en déduit que '''cl'''(α{{ind|''j''}}) = '''cl'''(α{{ind|0}}), c'est-à-dire que ''N''(α{{ind|''j''}}) = ±1. De plus, comme ''b{{ind|j}}'' > 0, la solution trouvée n'est pas [[trivial]]e.

:* '''La suite (α<sub>''j''</sub>) forme un palindrome :'''
De '''cl'''(ψ(α{{ind|''j''–1}})) = '''cl'''(φ(α{{ind|0}})) on déduit par récurrence, par la propriété de ψ {{Douteux|date=mai 2014|démontrée ci-dessus}}, que '''cl'''(ψ(α{{ind|''j''–1–''k''}})) = '''cl'''(φ(α{{ind|''k''}})).
{{Démonstration/fin}}

== Fraction continue ==
{{Article détaillé|Fraction continue}}

La méthode ''chakravala'' est très proche de celle de la fraction continue. Ici, l'objectif est d'approcher la racine de ''n'' par une expression optimale de la nature suivante :

<center><math>\sqrt n = f_0 + \cfrac1{f_1 + \cfrac{1}{f_2 + \frac1{f_3+\,\cdots}}}\quad \text{avec}\quad f_i\in\Z.</math></center>
<!--

=== Introduction par l'exemple ===
{{Travail inédit|date=octobre 2013|Cette sous-section semble contenir}}
Étudions le cas où ''n'' est égal à 19.

À l'ordre 0, {{Douteux|date=mai 2014|l'objectif est de trouver la valeur ''f''<sub>0</sub> la plus proche possible de {{racine|19}}.}} On obtient l'égalité :
<center><math>\sqrt{19} = 4 + (-4 +\sqrt{19}) \quad\text{et}\quad f_0 = 4,\quad \omega_0 = -4 +\sqrt{19}.</math></center>

Ici, ω<sub>''k''</sub> désigne le ''reste'' de la fraction continue. Son inverse est appelé « quotient complet d'indice ''k'' ».

À l'ordre 1, on cherche une approximation {{racine|19}} de la forme ''f''<sub>0</sub> + 1/''f''<sub>1</sub> (avec ''f''{{ind|1}} entier) {{Quoi|date=mai 2014|la meilleure possible}}, on obtient :
<center><math>\frac1{\omega_0}=\frac{4 +\sqrt{19}}3=\frac{9 - 5 +\sqrt{19}}3=3 + \frac13(-5 +\sqrt{19})\quad\text{et}\quad\sqrt{19}= 4 + \frac 1{3 + \omega_1},\; f_1 = 3,\; \omega_1 = \frac{-5 +\sqrt{19}}3.</math></center>

À l'ordre 2 :
<center><math>\frac1{\omega_1}=\frac{5 + \sqrt{19}}{-2}=\frac{10 - 5 +\sqrt{19}}{-2}=-5 + \frac12(5 -\sqrt{19})\quad\text{et}\quad\sqrt{19}= 4 + \frac 1{3 + \frac 1{-5 + \omega_2}},\; f_2 = -5,\; \omega_2 = \frac{5 -\sqrt{19}}2.</math></center>

À l'ordre 3 :
<center><math>\frac1{\omega_2}=\frac{5 +\sqrt{19}}3=\frac{9 - 4 +\sqrt{19}}3=3 + \frac13(-4 +\sqrt{19})\quad\text{et}\quad\sqrt{19}= 4 + \frac 1{3 + \frac 1{-5 + \frac 1{3 +\omega_3}}},\; f_3 = 3,\; \omega_3 = \frac{-4 +\sqrt{19}}3. </math></center>

À l'ordre 4 :
<center><math>\frac1{\omega_3}=4 +\sqrt{19}=8 - 4 +\sqrt{19}\quad\text{et}\quad\sqrt{19}= 4 + \frac 1{3 + \frac 1{-5 + \frac 1{3 +\frac 1{8 +\omega_5}}}},\; f_4 = 8,\; \omega_4=-4 +\sqrt{19}=\omega_0</math></center>

donc la suite (''f<sub>k</sub>'') est périodique et ses termes sont : ''f''<sub>0</sub>, ''f''<sub>1</sub>, ''f''<sub>2</sub>, ''f''<sub>3</sub>, ''f''<sub>4</sub>, ''f''<sub>1</sub>, ''f''<sub>2</sub>, ''f''<sub>3</sub>, ''f''<sub>4</sub>, ''f''<sub>1</sub>, … On note généralement une égalité de ce type de la manière suivante :
<center><math>\sqrt{19}= [4, \overline{3,-5,3,8}].</math></center>

Déterminons les fractions partielles μ{{ind|''k''}}, habituellement appelées « réduites d'indice ''k'' ».
<center><math>\mu_0 = f_0 = \frac41,\; \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}.</math></center>

Le calcul de la suite (α<sub>''k''</sub>) de la méthode ''chakravala'' donne :
<center><math>\alpha_1=4+\sqrt{19},\; \alpha_2=13+3\sqrt{19},\; \alpha_3=61+14\sqrt{19},\; \alpha_4=170+39\sqrt{19}.</math></center>

On trouve dans les deux cas les mêmes couples (4, 1), (13, 2), (61, 14) et (170, 39), ce qui n'est pas l'œuvre du hasard. Dans les deux cas on obtient la solution suivante :
<center><math>170^2 - 19\times 39^2 = 28\,900 - 28\;899 = 1.</math></center>

''Remarque :'' la convention choisie ici pour définir la fraction est que {{refnec|date=mai 2014|chaque réduite d'indice ''k'' doit être aussi proche que possible de la racine.}} La convention d'une fraction continue est un peu différente : chaque réduite d'indice ''k'' doit être aussi proche que possible de la racine mais seulement dans le cadre d'une suite (''f<sub>k</sub>'') ne prenant que des valeurs positives. Transcrite dans la méthode ''chakravala'', cette convention revient à ne considérer que des β<sub>''k''</sub> de normes négatives. Toutes les démonstrations s'appliquent encore avec cette convention. En revanche, la  longueur du cycle peut être plus longue, par exemple :
<center><math>\sqrt{19}= [4, \overline{2,1,3,1,2,8}].</math></center>
-->

=== Approche théorique ===
Soit ''n'' un entier naturel non carré. On définit par récurrence deux suites, (''f{{ind|j}}''){{ind|''j''≥0}} à valeurs dans ℤ et (θ{{ind|''j''}}){{ind|''j''≥–1}} dans [[Corps quadratique|ℚ({{sqrt|''n''}})]] par : θ{{ind|–1}} = {{sqrt|''n''}} et pour tout ''j'' ≥ –1, ''f''{{ind|''j''+1}} est l'entier (ou le plus petit des deux entiers) pour lequel |''N''(θ{{ind|''j''}} – ''f''{{ind|''j''+1}})| est minimal<!-- {{---|ce qui ne correspond pas à la convention du § précédent}}--> et θ{{ind|''j''+1}} = 1/(θ{{ind|''j''}} – ''f''{{ind|''j''+1}}). Le fait que {{racine|''n''}} soit irrationnel montre que θ{{ind|''j''}} est toujours irrationnel ; les suites (''f{{ind|j}}'') et (θ{{ind|''j''}}) sont ainsi bien définies.

Cette définition diffère de la traditionnelle fraction continue car ici, les θ{{ind|''j''}} et les ''f{{ind|j}}'' ne sont pas nécessairement positifs.

Soient (''h{{ind|j}}'') et (''k{{ind|j}}'') les suites des [[Fraction continue#Réduites d'une fraction continue|numérateurs et dénominateurs des réduites]].

{{énoncé|1=Si (α{{ind|''j''}}) et (β{{ind|''j''}}) désignent [[#Principe de la méthode|les suites définies précédemment]], les égalités suivantes sont vérifiées (avec, par convention, ''m''{{ind|–1}} = 0) :
<center><math> \forall j\in\N \quad f_j=(-1)^j\frac{m_{j-1}+m_j}{\mathcal N(\alpha_j)},\quad\theta_j=(-1)^{j+1}\frac {\varphi(\beta_j)}{\mathcal N(\alpha_j)}\quad\text{et}\quad\alpha_j=\pm(h_{j-1}+k_{j-1}\sqrt n).</math></center>}}

Ainsi, le caractère cyclique et la propriété de palindrome de cette fraction continue permettent de démontrer ceux de la méthode ''chakravala'', et inversement. Si l'algorithme récursif impose aux β{{ind|''j''}} d'être de norme systématiquement négative, alors les démonstrations de l'article restent valables et les fractions continues associées correspondent à la définition usuelle.

{{Démonstration/début}}
*'''''f{{ind|j}}'' = (–1){{exp|''j''}}(''m''{{ind|''j''–1}} + ''m{{ind|j}}'')/''N''(α{{ind|''j''}}) et  θ{{ind|''j''}} = (–1){{exp|''j''+1}}''N''(α{{ind|''j''}})/φ(β{{ind|''j''}}) :''' montrons ce résultat par récurrence sur ''j''. Par définition, ''f''{{ind|0}} = ''m''{{ind|0}} et<center><math>\theta_0=\frac1{\sqrt n-m_0}=\frac1{-\varphi(\beta_0)}=-\frac{\mathcal N (\alpha_0)}{\varphi(\beta_0)}.</math></center>Supposons le résultat établi à l'ordre ''j'' – 1 et montrons qu'il est vrai à l'ordre ''j''.<center><math>(-1)^j\left(f_j+\frac1{\theta_j}\right)=(-1)^j\theta_{j-1}=\frac{\mathcal N(\alpha_{j-1})}{\varphi(\beta_{j-1})}=\frac{\mathcal N(\alpha_{j-1})\beta_{j-1}}{\varphi(\beta_{j-1})\beta_{j-1}}=\frac{\mathcal N(\alpha_{j-1})\beta_{j-1}}{\mathcal N(\pm\alpha_j\varphi(\alpha_{j-1}))}=\frac{\beta_{j-1}}{\mathcal N(\alpha_j)}=\frac{m_{j-1}+m_j}{\mathcal N(\alpha_j)}-\frac{\varphi(\beta_j)}{\mathcal N(\alpha_j)}</math></center>et [[#Lemme|par choix de β{{ind|''j''}}, l'entier ''f'' = (''m''{{ind|''k''–1}} + ''m{{ind|k}}'')/''N''(α{{ind|''k''}})]] est celui pour lequel la valeur absolue de la norme de (β{{ind|''j''–1}}/''N''(α{{ind|''j''}})) – ''f'' est minimale. Il est donc égal à (–1){{exp|''j''}}''f{{ind|j}}'' et le reste, –φ(β{{ind|''j''}})/''N''(α{{ind|''j''}}), à (–1){{exp|''j''}}/θ{{ind|''j''}}.
* '''α{{ind|''j''}} = ±(''h''{{ind|''j''–1}} + ''k''{{ind|''j''–1}}{{sqrt|''n''}}) :''' en notant ε{{ind|''j''}} le signe de ''N''(α{{ind|''j''}}) on a, pour tout ''j'' > 0 :<center><math>(-1)^jf_j\mathcal N(\alpha_j)=m_j+m_{j-1}=\beta_j+\varphi(\beta_{j-1})=\varepsilon_j\alpha_{j+1}\varphi(\alpha_j)+\varepsilon_{j-1}\varphi(\alpha_j)\alpha_{j-1}</math></center>c'est-à-dire<center><math>(-1)^jf_j\alpha_j=\varepsilon_j\alpha_{j+1}+\varepsilon_{j-1}\alpha_{j-1}</math></center>ou encore, en posant<center><math>\varepsilon'_j=(-1)^{j(j-1)/2}\prod_{0\le i<j}\varepsilon_i~:\quad\varepsilon'_{j+1}\alpha_{j+1}=f_j\varepsilon'_j\alpha_j+\varepsilon'_{j-1}\alpha_{j-1}.</math></center>Les deux suites (ε'{{ind|''j''}}α{{ind|''j''}}) et (''h''{{ind|''j''–1}} + ''k''{{ind|''j''–1}}{{sqrt|''n''}}) vérifient donc la même relation de récurrence d'ordre 2. Comme elles coïncident pour ''j'' = 0 et pour ''j'' = 1, elles sont égales.
{{Démonstration/fin}}

=== Méthode de calcul ===
L'approche par les fractions continues offre un enrichissement de la méthode algorithmique précédente pour l'équation de Pell-Fermat ou la détermination de la fraction continue. Illustrons ces méthodes à l'aide de l'exemple ''n'' = 313 et montrons comment Brouncker pouvait effectivement résoudre ce défi en une heure ou deux. Par définition, ''m''{{ind|–1}} = 0 et ''N''(α{{ind|0}}) = 1 puis, pour tout indice ''j'' ≥ 0 :
*''m{{ind|j}}'' est congru à –''m''{{ind|''j''–1}} modulo ''N''(α{{ind|''j''}}) et son carré est le plus proche possible de 313 ;
*''N''(β{{ind|''j''}}) = ''m{{ind|j}}''{{2}} – 313 ;
*''N''(α{{ind|''j''+1}}) = ''N''(β{{ind|''j''}})/''N''(α{{ind|''j''}}).
On trouve ainsi ''m''{{ind|0}} = 18, ''N''(β{{ind|0}}) = 11, ''N''(α{{ind|1}}) = 11, ''m''{{ind|1}} = 15, ''N''(β{{ind|1}}) = –88, ''N''(α{{ind|2}}) = –8{{etc.}}

On en déduit les ''f{{ind|j}}'' par la formule du paragraphe précédent : ''f''{{ind|0}} = ''m''{{ind|0}} = 18, ''f''{{ind|1}} = –(18 + 15)/11 = –3{{etc.}}

Cette approche permet d'éviter les grands nombres, sauf pour ''h''{{ind|''j''–1}} et ''k''{{ind|''j''–1}}, dont ''a''{{ind|''j''}} et ''b''{{ind|''j''}} sont les valeurs absolues. On les calcule pour ''j'' ≥ 1 par la [[Fraction continue#Réduites d'une fraction continue|formule de récurrence]] à partir des ''f{{ind|j}}''.

En outre, si les normes de deux α consécutifs sont égales ou opposées, il résulte aussitôt de l'algorithme que les β et les normes des α forment un palindrome. Plus précisément : si ''N''(α{{ind|''r''+1}}) = ε''N''(α{{ind|''r''}}) avec ε = ±1 alors, par récurrence sur ''k'', β{{ind|''r+k''}} = β{{ind|''r–k''}} et ''N''(α{{ind|''r+k''+1}}) = ε''N''(α{{ind|''r–k''}}). Par conséquent, α{{ind|2''r''+1}} est alors inversible (de norme ε) et {{---|d'après l'expression de la [[#Principe de la méthode|suite des α en fonction de celle des β]]}} égal à ε{{exp|''r''}}α{{ind|''r''+1}}/φ(α{{ind|''r''}}) = ε{{exp|''r''}}α{{ind|''r''}}α{{ind|''r''+1}}/''N''(α{{ind|''r''}}).

On construit ainsi le tableau suivant, où l'on constate que la situation mentionnée survient pour ''r'' = 6 et ε = –1 :

<center>
{| class="wikitable"
|
{| border="1"
| '''j''' || '''m<sub>j</sub>''' ||  '''N(β<sub>j</sub>) = m<sub>j</sub><sup>2</sup> – 313''' || '''N(α<sub>j</sub>) = N(β<sub>j–1</sub>)/N(α<sub>j–1</sub>)''' || '''f<sub>j</sub> = (–1)<sup>j</sup>(m<sub>j</sub> + m<sub>j–1</sub>)/N(α<sub>j</sub>)''' ||  '''h<sub>j–1</sub> = f<sub>j–1</sub>h<sub>j–2</sub> + h<sub>j–3</sub>''' || '''k<sub>j–1</sub> = f<sub>j–1</sub>k<sub>j–2</sub> + k<sub>j–3</sub>'''
|-
| '''0''' || 18 ||  11  || 1  || 18 || 1   ||   0
|-
| '''1''' || 15 || –88  || 11 || –3  ||  18      || 1
|-
| '''2''' || 17 || –24  || –8 || –4  || –53      || –3
|-
| '''3''' || 19 ||  48  ||  3 || –12 || 230      || 13
|-
| '''4''' || 13 || –144 || 16 || 2   || –2 813   || –159
|-
| '''5''' || 14 || –117 || –9 || 3   || –5 396   || –305
|-
| '''6''' || 12 || –169 || 13 || 2   || –19 001  || –1 074
|-
| '''7''' || 14 || –117 || –13|| 2   || –43 398  || –2 453
|}
|}
</center>
La suite des normes des α est donc 1, 11, –8, 3, 16, –9, 13, –13, 9, –16, –3, 8, –11, –1, ce qui fournit un élément de norme –1 :
<center><math> \alpha_{13}=\frac {\alpha_6\alpha_7}{13} = (19\,001 + 1\,074\sqrt{313})(43\,398 + 2\,453\sqrt{313})= 126\,862\,368 + 7\;170\;685\sqrt{313}.</math></center>

(Ce nombre est d'ailleurs aussi égal à α{{ind|3}}{{2}}α{{ind|5}}/9.) Il ne reste plus qu'à l'élever au carré pour obtenir la solution recherchée :
<center><math>\alpha_{26} =\alpha_{13}^2 = (126\,862\,368 + 7\;170\;685\sqrt{313})^2 =   32\;188\;120\;829\;134\;849 + 1\;819\;380\;158\;564\;160\sqrt{313}.</math></center>

La méthode ''chakravala'' permet ainsi de résoudre à la main ce type de calcul. La même démarche, sans le calcul des colonnes ''h''{{ind|''j''–1}} et ''k''{{ind|''j''–1}}, inutile pour cet objectif, permet de déterminer ''une'' fraction continue de {{racine|313}}. Rechercher la solution telle que la suite (''f<sub>k</sub>'') ne comporte que des valeurs positives suppose de restreindre le choix aux ''m<sub>k</sub> ''inférieurs ou égaux à 17. On trouverait alors ''la'' [[fraction continue d'un irrationnel quadratique|fraction continue de cet irrationnel quadratique]] : [17, {{surligner|1, 2, 4, 11, 1, 1, 3, 2, 2, 3, 1, 1, 11, 4, 2, 1, 34}}]<ref>Suite {{OEIS2C|id=A040295}} de l'[[OEIS]].</ref>.

== Notes et références ==
{{Références|colonnes=2}}

== Voir aussi ==
=== Lien externe ===
{{MacTutor|class=~history/Miscellaneous/Pearce/Lectures|id=Ch8_6|title=Indian Mathematics: Redressing the balance, 8 VI. Pell's equation}}

=== Bibliographie ===
* {{Dickson1}}, ''vol. II, Diophantine analysis''
* Jean Trignan, ''Introduction aux problèmes d'approximation : fractions continues, différences finies'', Éditions du Choix, 1994 {{ISBN|978-2-909028-16-3}}

{{Portail|arithmétique}}

[[Catégorie:Équation diophantienne]]
[[Catégorie:Algorithme]]
[[Catégorie:Arithmétique modulaire]]
[[Catégorie:Entier quadratique]]
[[Catégorie:Histoire de l'algèbre]]