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 entiers et dont on cherche les solutions entières. Plus précisément, c'est l'équation

$x^2-n{y}^2=1$

où n est un entier naturel non carré.

Cette méthode fut développée en Inde et ses racines peuvent être retracées jusqu'au Modèle:VIe siècle avec Aryabhata, suivi par Brahmagupta. Initiée par Modèle:Lien, elle fut développée plus avant par Bhāskara II.

Selenius l'évalue par : Modèle:Citation

Il faut en effet attendre le Modèle:S- pour que les Européens, qui ignoraient les travaux des mathématiciens indiens, découvrent des algorithmes — moins performants — résolvant le même problème.

Aryabhata établit les fondements de la méthode chakravala.

Objectif

Une forme d'équation de Pell-Fermat s'exprime de la manière suivante :

$x^2-n{y}^2=1,$

où n est un entier naturel non carré. L'équation est diophantienne ce qui signifie que les couples Modèle:Nobr 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 Modèle:S- :

$1151^2-92\times 120^2=1.$

Histoire

Mathématiques indiennes

Les mathématiques indiennes s'intéressent très tôt à l'arithmétique. Aryabhata, un mathématicien du Modèle: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. Il travaille sur les équations diophantiennes et pour résoudre l'identité de Bézout, met au point un algorithme équivalent à celui d'Euclide qu'il appelle kuModèle:Prononciation APIModèle:Prononciation APIaka (कूटटक) et qui signifie pulvérisateur car il casse les nombres en entiers plus petits. Il travaille aussi sur les fractions continues.

Le mathématicien indien Brahmagupta (598 – 668) 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. 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. Brahmagupta l'utilise en 628 dans son livre Brahmasphuta siddhanta pour résoudre l'équation suivante :

$x^2-83y^2=1.$

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 Modèle:S, 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 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 pour trouver une solution minimale à l'équation suivante déjà trouvée par Brahmagupta :

$x^2-61y^2=1.$

Le couple solution trouvé est :

$x=1766319049\text{et}y=226153980.$

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 Modèle:S-. De nouveaux exemples sont traités plus tard, par les mathématiciens indiens. Au Modèle:S 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), Pierre de Fermat défie Bernard Frénicle de Bessy 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.

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 Lagrange en 1767, 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, Modèle:Lien affirme être le premier à prouver celle de chakravala.

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é :

$(1)x^2-n{y}^2=1.$

Soient A l'anneau des nombres de la forme a + Modèle:Racineb, où a et b désignent deux nombres entiers, N l'application qui à un élément de A associe sa « norme » et φ l'application qui à un élément de A associe son « conjugué » :

$𝒩(a+\sqrt{n}b)=a^2-n{b}^2,\phi (a+\sqrt{n}b)=a-\sqrt{n}b.$

La fonction N correspond à la norme de A au sens de la théorie algébrique des nombres. Un élément a + Modèle:Racineb 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 automorphisme de A :

$\mathrm{\forall }\alpha ,\beta \in A\phi (\alpha +\beta )=\phi (\alpha )+\phi (\beta ),\phi (\alpha \beta )=\phi (\alpha )\phi (\beta ),\phi (1)=1.$

La conjugaison φ est 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 :

$\mathrm{\forall }\alpha \in A(\phi \circ \phi )(\alpha )=\alpha .$

Enfin, le produit de deux éléments conjugués est égal à leur norme commune :

$\mathrm{\forall }\alpha \in A𝒩(\alpha )=\alpha \phi (\alpha ).$

Si l'on note α = a + Modèle:Racineb, cela est justifié par le calcul suivant :

$𝒩(\alpha )=a^2-n{b}^2=(a+\sqrt{n}b)(a-\sqrt{n}b)=\alpha \phi (\alpha ).$

Samasa

La première propriété utilisée est la suivante : Modèle:Énoncé

Si α = a₁ + Modèle:Racinea₂ et β = b₁ + Modèle:Racineb₂, cette égalité s'écrit :

$(a_1{b}_1+n{a}_2{b}_2{)}^2-n(a_1{b}_2+a_2{b}_1{)}^2=(a_1^2-n{a}_2^2)(b_1^2-n{b}_2^2).$

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 φ :

$𝒩(\alpha \beta )=\alpha \beta \phi (\alpha \beta )=\alpha \phi (\alpha )\beta \phi (\beta )=𝒩(\alpha )𝒩(\beta ).$

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

Conséquences

Modèle:Énoncé En effet, N(α) = N(φ(α)) = αφ(α), et si α est une solution de (1) alors αModèle:Exp 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 : Modèle:Énoncé

1. : immédiat.
2. : si α = a + bModèle:Racine alors α² = a² + nb² + 2abModèle:Racine = N(α) + 2nb² + 2abModèle:Racine est divisible par 2 (et 2Modèle:2N(αModèle:2/2) = N(αModèle:2) = (±2)Modèle:2 donc N(αModèle:2/2) = 1).
3. : les deux premiers cas sont immédiats et dans le troisième, n, a et b sont impairs, si bien que αModèle:3 est divisible par 8 car$\begin{array}{cc}{\alpha }^3& =(a+b\sqrt{n}{)}^3=a^3+3a{b}^{2}n+\sqrt{n}(n{b}^3+3a^{2}b)=a(a^2-n{b}^2+4n{b}^2)+b\sqrt{n}(3a^2-3n{b}^2+4n{b}^2)\\ & =a(𝒩(\alpha )+4n{b}^2)+b\sqrt{n}(3𝒩(\alpha )+4n{b}^2)=4a(\epsilon +n{b}^2)+4b\sqrt{n}(3\epsilon +n{b}^2)\text{avec}\epsilon =\pm 1.\end{array}$

Exemples

Exemple de Brahmagupta

Traitons avec cette méthode l'exemple de Brahmagupta suivant :

$x^2-83y^2=1.$

Soit α = m + Modèle:Racine, l'entier m étant choisi tel que la norme N(α) = mModèle:2 – 83 soit la plus petite possible en valeur absolue : m = 9, α = 9 + Modèle:Racine, N(α) = –2. Une proposition précédente montre que αModèle:2/2 est une solution. Effectivement :

${\alpha }^2=(9^2+83\cdot 1)+\sqrt{83}\cdot 2\times 9\times 1=164+\sqrt{83}\cdot 18=2(82+\sqrt{83}\cdot 9)$

et

$82^2-83\times 9^2=6724-6723=1.$

Défi de Fermat

Le défi de Fermat se résout de la même manière :

$x^2-61y^2=1.$

Brahmagupta s'y prend de la manière suivante : il remarque que si α = 39 + 5Modèle:Racine 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 α²/2 :

$\frac{{\alpha }^2}{2}=\frac{1}{2}(39+5\sqrt{61}{)}^2=\frac{1}{2}(39^2+5^2\times 61+2\times 5\times 39\sqrt{61})=1523+195\sqrt{61}.$

Puis il calcule α³/8 et sa norme :

$\frac{{\alpha }^3}{8}=\frac{1}{4}(39+5\sqrt{61})(1523+195\sqrt{61})=29718+3805\sqrt{61}\text{et}𝒩(\frac{{\alpha }^3}{8})=29718^2-61\times 3805^2=-1.$

La solution est donc α⁶/64, soit :

$\frac{{\alpha }^6}{64}=(29718+3805\sqrt{61}{)}^2=29718^2+61\times 3805^2+2\times 29718\times 3805\sqrt{61}=1766319049+226153980\sqrt{61}.$

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 construit par récurrence une suite d'éléments αModèle:Ind = aModèle:Ind + bModèle:IndModèle:Sqrt de A de la manière suivante. Le premier élément de la suite est αModèle:Ind = 1, de norme kModèle:Ind = 1. Supposons la suite définie à l'ordre j. On construit un élément β_j = mModèle:Ind + Modèle:Racine. L'entier naturel mModèle:Ind est tel que aModèle:Ind + mModèle:IndbModèle:Ind soit multiple de la norme kModèle:Ind de αModèle:Ind — autrement dit tel que bModèle:IndmModèle:Ind soit [[Congruence sur les entiers|congru à –aModèle:Ind modulo kModèle:Ind]] — et m_j minimise la valeur absolue de la norme mModèle:IndModèle:2 – n de βModèle:Ind. L'élément α_{j + 1} est alors défini par

${\alpha }_{j+1}=a_{j+1}+b_{j+1}\sqrt{n}=\frac{{\alpha }_j{\beta }_j}{|𝒩({\alpha }_j)|}=\frac{a_j{m}_j+n{b}_j+\sqrt{n}(a_j+m_j{b}_j)}{|𝒩({\alpha }_j)|}$

ou encore

${\alpha }_{j+1}\phi ({\alpha }_j)=\pm {\beta }_j,$

le ± correspondant au signe de N(αModèle:Ind) Modèle:---.

On verra plus loin que la condition « aModèle:Ind + mModèle:IndbModèle:Ind multiple de kModèle:Ind » équivaut à « mModèle:Ind congru à –mModèle:Ind modulo kModèle:Ind », ce qui simplifie l'algorithme.

Exemples

Défi de Fermat

Choisissons encore n égal à 61. La valeur de mModèle:Ind est égale à 8 pour minimiser |N(βModèle:Ind)|. En effet, Modèle:Sqrt est compris entre 7 et 8 et 8Modèle:2 – 61 = 3 < 61 – 7Modèle:2. L'entier mModèle:Ind est ensuite choisi parmi ceux congrus, modulo N(αModèle:Ind) = N(8 + Modèle:Sqrt) = 8Modèle:2 – 61 = 3, à –mModèle:Ind = –8 donc à 1. Des deux termes consécutifs 7 et 10 de cette suite arithmétique qui encadrent Modèle:Sqrt, celui qui minimise |N(βModèle:Ind)| est mModèle:Ind = 7, ce qui donne :

${\alpha }_2=\frac{8\times 7+61}{3}+\frac{8+7}{3}\sqrt{61}=39+5\sqrt{61}\text{et}𝒩({\alpha }_2)=-4.$

La suite de la méthode est 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, mModèle:Ind = 10. L'entier mModèle:Ind est ensuite choisi congru à –10 modulo N(αModèle:Ind) = N(10 + Modèle:Sqrt) = 10Modèle:2 – 103 = –3. Comme 8 < Modèle:Sqrt < 11 et 11Modèle:2 – 103 = 18 < 103 – 8Modèle:2, on obtient mModèle:Ind = 11 et

${\alpha }_2=\frac{10\times 11+103}{3}+\frac{10+11}{3}\sqrt{103}=71+7\sqrt{103}\text{et}𝒩({\alpha }_2)=-6.$

On choisit ensuite mModèle:Ind congru à –11 modulo 6. Comme 7 < Modèle:Sqrt < 13 et 103 – 7Modèle:2 = 54 < 13Modèle:2 – 103, on obtient mModèle:Ind = 7 Modèle:--- puis

${\alpha }_3=203+20\sqrt{103}\text{et}𝒩({\alpha }_3)=9.$

Puis, modulo 9, mModèle:Ind doit être congru à –7. Pour minimiser |N(βModèle:Ind)|, il faut choisir mModèle:Ind égal à 11. On obtient

${\alpha }_4=477+47\sqrt{103}\text{et}𝒩({\alpha }_4)=2.$

Le calcul de Brahmagupta permet de conclure : la valeur cherchée est

$\frac{{\alpha }_4^2}{2}=\frac{(477+47\sqrt{103}{)}^2}{2}=227528+22419\sqrt{103}.$

Non-unicité

L'exemple suivant montre que le nombre [[#Principe de la méthode|αModèle:Ind défini à partir de αModèle:Ind]] n'est pas toujours unique : pour n = 58, αModèle:Ind est égal à 8 + Modèle:Sqrt, de norme 6 puis, pour mModèle:Ind congru à –2 modulo 6, le minimum de Modèle:Nobr est 42, atteint pour les deux valeurs 4 et 10 de mModèle:Ind. Les deux valeurs correspondantes pour αModèle:Ind sont 15 + 2Modèle:Sqrt, de norme –7, et 23 + 3Modèle:Sqrt, de norme 7. Cependant, pour la première on trouve ensuite Modèle:Nobr et pour la seconde, mModèle:Ind = 4 donc pour les deux, αModèle:Ind = 38 + 5Modèle:Sqrt, de norme –6, puis mModèle:Ind = 8 et αModèle:Ind = 99 + 13Modèle:Sqrt, 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 Modèle:Nobr est divisible par k. En effet, en résolvant l'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.

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 » — à a = aModèle:Ind et b = bModèle:Ind, il montre qu'à chaque étape de la construction de la suite (αModèle:Ind), si mModèle:Ind est choisi selon la méthode indiquée alors αModèle:IndβModèle:Ind est un multiple de N(αModèle:Ind), αModèle:Ind est un élément de A et aModèle:Ind et bModèle:Ind sont premiers entre eux, ce qui permet d'itérer la construction.

On peut remarquer de plus que la contrainte (dans le choix de mModèle:Ind) « aModèle:Ind + bModèle:Indm divisible par N(αModèle:Ind) » est équivalente à « m congru à –mModèle:Ind modulo N(αModèle:Ind) ». En effet, bModèle:Ind est premier avec N(αModèle:Ind) et aModèle:Ind + bModèle:Ind(–mModèle:Ind) est divisible par N(αModèle:Ind) puisque φ(αModèle:Ind)βModèle:Ind = ±N(αModèle:Ind)φ(αModèle:Ind).

Caractère cyclique

Une fois montré que la suite (α_j) est bien définie, étudions son comportement. Elle est « cyclique » en un certain sens. Plus précisément, en notant cl(α) la classe d'équivalence de α pour la relation « être 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(α_j)) est périodique à partir d'un certain rang. Cette propriété est la conséquence immédiate de trois propositions : Modèle:Énoncé

• kModèle:Ind := |N(α_j)| < Modèle:Sqrt : montrons-le par récurrence. On a bien kModèle:Ind = 1 < Modèle:Sqrt. Supposons que kModèle:Ind < Modèle:Sqrt. Alors, il existe un entier m (nécessairement positif) tel que m < Modèle:Sqrt < m + kModèle:Ind et tel que mModèle:Ind soit égal à m ou à m + kModèle:Ind, selon que n – mModèle:2 est inférieur ou supérieur à (m + kModèle:Ind)Modèle:2 – n, autrement dit selon que mModèle:2 + kModèle:Indm + kModèle:IndModèle: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, |mModèle:IndModèle:2 – n| ≤ kModèle:IndModèle:Sqrt < kModèle:IndModèle:Sqrt, d'où kModèle:Ind = |mModèle:IndModèle:2 – n|/kModèle:Ind < Modèle:Sqrt.
• 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²), ce qui conclut.
• Si αModèle:Ind = εαModèle:Ind avec ε inversible dans A alors αModèle:Ind = εαModèle:Ind car |N(αModèle:Ind)| = |N(αModèle:Ind)| et les β divisibles par φ(αModèle:Ind) Modèle:--- vérifient αModèle:Indβ = εαModèle:Indβ.

Ces propriétés ne démontrent que la périodicité à partir d'un certain rang. Le paragraphe suivant Modèle:Douteux 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 : Modèle:Énoncé Modèle:Démonstration/début Soient B l'ensemble des éléments a + bModèle:Sqrt 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 + Modèle:Racine avec m entier naturel tel que βα soit un multiple de la norme de α, de norme minimale (on a vu plus haut qu'il pouvait y en avoir deux : on peut par exemple 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

$\mathrm{\forall }k\in \mathbb{N},\psi ({\alpha }_k)={\alpha }_{k+1}.$

Cette fonction possède une symétrie par rapport à la fonction φ :

• La propriété suivante est vérifiée :

$\mathrm{\forall }\alpha ,\gamma \in B\psi (\alpha )=\gamma \Rightarrow \psi (\phi (\gamma ))=\pm \phi (\alpha ).$

Plus précisément : ψ(φ(γ)) = εModèle:IndεModèle:Indφ(α), où εModèle:Ind (resp. εModèle:Ind) 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 + Modèle:Racine avec m entier naturel tel que

$\gamma =\frac{\alpha \beta }{|𝒩(\alpha )|}={ϵ}_1\frac{\alpha \beta }{\alpha \phi (\alpha )}={ϵ}_1\frac{\beta }{\phi (\alpha )}\text{et}(1)\phi (\alpha )={ϵ}_1\frac{\beta }{\gamma }={ϵ}_1{ϵ}_2\frac{\phi (\gamma )\beta }{|𝒩(\phi (\gamma ))|}.$

L'élément β est bien de la forme m + Modèle:Racine 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 à β, Modèle:Douteux. 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 εModèle:IndεModèle:Indφ(α) est bien l'image de φ(γ) par ψ. Modèle:Douteux

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

• Il existe un indice j > 0 tel que N(α_j) = ±1 :

D'après le § « Caractère cyclique » précédent, il existe deux indices 0 ≤ k < k + j tels que cl(αModèle:Ind) = cl(αModèle:Ind). Par la bijectivité de ψ Modèle:Douteux, on en déduit que cl(αModèle:Ind) = cl(αModèle:Ind), c'est-à-dire que N(αModèle:Ind) = ±1. De plus, comme bModèle:Ind > 0, la solution trouvée n'est pas triviale.

• La suite (α_j) forme un palindrome :

De cl(ψ(αModèle:Ind)) = cl(φ(αModèle:Ind)) on déduit par récurrence, par la propriété de ψ Modèle:Douteux, que cl(ψ(αModèle:Ind)) = cl(φ(αModèle:Ind)). Modèle:Démonstration/fin

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 :

$\sqrt{n}=f_0+\frac{1}{f_1+\frac{1}{f_2+\frac{1}{f_3+\cdots }}}\text{avec}{f}_i\in \mathbb{Z}.$

Approche théorique

Soit n un entier naturel non carré. On définit par récurrence deux suites, (fModèle:Ind)Modèle:Ind à valeurs dans ℤ et (θModèle:Ind)Modèle:Ind dans [[Corps quadratique|ℚ(Modèle:Sqrt)]] par : θModèle:Ind = Modèle:Sqrt et pour tout j ≥ –1, fModèle:Ind est l'entier (ou le plus petit des deux entiers) pour lequel |N(θModèle:Ind – fModèle:Ind)| est minimal et θModèle:Ind = 1/(θModèle:Ind – fModèle:Ind). Le fait que Modèle:Racine soit irrationnel montre que θModèle:Ind est toujours irrationnel ; les suites (fModèle:Ind) et (θModèle:Ind) sont ainsi bien définies.

Cette définition diffère de la traditionnelle fraction continue car ici, les θModèle:Ind et les fModèle:Ind ne sont pas nécessairement positifs.

Soient (hModèle:Ind) et (kModèle:Ind) les suites des numérateurs et dénominateurs des réduites.

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 βModèle:Ind 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.

• fModèle:Ind = (–1)Modèle:Exp(mModèle:Ind + mModèle:Ind)/N(αModèle:Ind) et θModèle:Ind = (–1)Modèle:ExpN(αModèle:Ind)/φ(βModèle:Ind) : montrons ce résultat par récurrence sur j. Par définition, fModèle:Ind = mModèle:Ind et${\theta }_0=\frac{1}{\sqrt{n}-m_0}=\frac{1}{-\phi ({\beta }_0)}=-\frac{𝒩({\alpha }_0)}{\phi ({\beta }_0)}.$Supposons le résultat établi à l'ordre j – 1 et montrons qu'il est vrai à l'ordre j.$(-1{)}^j(f_j+\frac{1}{{\theta }_j})=(-1{)}^j{\theta }_{j-1}=\frac{𝒩({\alpha }_{j-1})}{\phi ({\beta }_{j-1})}=\frac{𝒩({\alpha }_{j-1}){\beta }_{j-1}}{\phi ({\beta }_{j-1}){\beta }_{j-1}}=\frac{𝒩({\alpha }_{j-1}){\beta }_{j-1}}{𝒩(\pm {\alpha }_j\phi ({\alpha }_{j-1}))}=\frac{{\beta }_{j-1}}{𝒩({\alpha }_j)}=\frac{m_{j-1}+m_j}{𝒩({\alpha }_j)}-\frac{\phi ({\beta }_j)}{𝒩({\alpha }_j)}$et [[#Lemme|par choix de βModèle:Ind, l'entier f = (mModèle:Ind + mModèle:Ind)/N(αModèle:Ind)]] est celui pour lequel la valeur absolue de la norme de (βModèle:Ind/N(αModèle:Ind)) – f est minimale. Il est donc égal à (–1)Modèle:ExpfModèle:Ind et le reste, –φ(βModèle:Ind)/N(αModèle:Ind), à (–1)Modèle:Exp/θModèle:Ind.
• αModèle:Ind = ±(hModèle:Ind + kModèle:IndModèle:Sqrt) : en notant εModèle:Ind le signe de N(αModèle:Ind) on a, pour tout j > 0 :$(-1{)}^j{f}_j𝒩({\alpha }_j)=m_j+m_{j-1}={\beta }_j+\phi ({\beta }_{j-1})={\epsilon }_j{\alpha }_{j+1}\phi ({\alpha }_j)+{\epsilon }_{j-1}\phi ({\alpha }_j){\alpha }_{j-1}$c'est-à-dire$(-1{)}^j{f}_j{\alpha }_j={\epsilon }_j{\alpha }_{j+1}+{\epsilon }_{j-1}{\alpha }_{j-1}$ou encore, en posant$\epsilon {\text{'}}_j=(-1{)}^{j(j-1)/2}\prod _{0\le i<j}{\epsilon }_i:\epsilon {\text{'}}_{j+1}{\alpha }_{j+1}=f_j\epsilon {\text{'}}_j{\alpha }_j+\epsilon {\text{'}}_{j-1}{\alpha }_{j-1}.$Les deux suites (ε'Modèle:IndαModèle:Ind) et (hModèle:Ind + kModèle:IndModèle:Sqrt) 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.

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, mModèle:Ind = 0 et N(αModèle:Ind) = 1 puis, pour tout indice j ≥ 0 :

• mModèle:Ind est congru à –mModèle:Ind modulo N(αModèle:Ind) et son carré est le plus proche possible de 313 ;
• N(βModèle:Ind) = mModèle:IndModèle:2 – 313 ;
• N(αModèle:Ind) = N(βModèle:Ind)/N(αModèle:Ind).

On trouve ainsi mModèle:Ind = 18, N(βModèle:Ind) = 11, N(αModèle:Ind) = 11, mModèle:Ind = 15, N(βModèle:Ind) = –88, N(αModèle:Ind) = –8Modèle:Etc.

On en déduit les fModèle:Ind par la formule du paragraphe précédent : fModèle:Ind = mModèle:Ind = 18, fModèle:Ind = –(18 + 15)/11 = –3Modèle:Etc.

Cette approche permet d'éviter les grands nombres, sauf pour hModèle:Ind et kModèle:Ind, dont aModèle:Ind et bModèle:Ind sont les valeurs absolues. On les calcule pour j ≥ 1 par la formule de récurrence à partir des fModèle:Ind.

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(αModèle:Ind) = εN(αModèle:Ind) avec ε = ±1 alors, par récurrence sur k, βModèle:Ind = βModèle:Ind et N(αModèle:Ind) = εN(αModèle:Ind). Par conséquent, αModèle:Ind est alors inversible (de norme ε) et Modèle:--- égal à εModèle:ExpαModèle:Ind/φ(αModèle:Ind) = εModèle:ExpαModèle:IndαModèle:Ind/N(αModèle:Ind).

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

j mj N(βj) = mj2 – 313 N(αj) = N(βj–1)/N(αj–1) fj = (–1)j(mj + mj–1)/N(αj) hj–1 = fj–1hj–2 + hj–3 kj–1 = fj–1kj–2 + kj–3 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

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 :

${\alpha }_{13}=\frac{{\alpha }_6{\alpha }_7}{13}=(19001+1074\sqrt{313})(43398+2453\sqrt{313})=126862368+7170685\sqrt{313}.$

(Ce nombre est d'ailleurs aussi égal à αModèle:IndModèle:2αModèle:Ind/9.) Il ne reste plus qu'à l'élever au carré pour obtenir la solution recherchée :

${\alpha }_{26}={\alpha }_{13}^2=(126862368+7170685\sqrt{313}{)}^2=32188120829134849+1819380158564160\sqrt{313}.$

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 hModèle:Ind et kModèle:Ind, inutile pour cet objectif, permet de déterminer une fraction continue de Modèle:Racine. Rechercher la solution telle que la suite (f_k) ne comporte que des valeurs positives suppose de restreindre le choix aux m_k inférieurs ou égaux à 17. On trouverait alors la fraction continue de cet irrationnel quadratique : [17, Modèle:Surligner].

Voir aussi

Bibliographie

• Modèle:Dickson1, vol. II, Diophantine analysis
• Jean Trignan, Introduction aux problèmes d'approximation : fractions continues, différences finies, Éditions du Choix, 1994 Modèle:ISBN