Méthode chakravala

Méthode chakravala
Âryabhata s'intéresse à l'arithmétique. Il établit les fondements de la méthode chakravala.

En mathématiques et plus précisément en arithmétique, la méthode chakravala est un algorithme pour résoudre les équations diophantiennes équivalentes à celles de Pell-Fermat. Une équation diophantienne est une équation à coefficients choisis dans les nombres entiers et les solutions recherchées sont entières. L'équation traitée est équivalente à :

x^2 -n\cdot y^2 = 1 \quad \text{avec} \quad n\in\N - \{0, 1\} .

Cette méthode fut développée en Inde et ses racines peuvent être retracées jusqu'au Ve siècle. Initiée par Âryabhata, elle est développée plus avant par Brahmagupta et Bhāskara II.

Selenius, pour son évaluation de la méthode chakravala, énonce : «  La méthode représente un algorithme de meilleure approximation de longueur minimale qui, en raison de plusieurs propriétés de minimisation, avec un effort minimal et évitant les grands nombres produit automatiquement les meilleures solutions de l'équation. La méthode chakravala anticipa les méthodes européennes de plus d'un milliers d'années. Mais aucune performance européenne dans le champ entier de l'algèbre beaucoup plus tard après Bhāskara, n'égala la complexité merveilleuse et ingénieuse de chakravala[1]. »

Il faut en effet attendre de XVIIe siècle pour que l'Europe redécouvre de manière indépendante les résultats des travaux des mathématiciens indiens.

Sommaire

Objectif

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

x^2 - n\cdot y^2 = 1~.

Ici n désigne un entier strictement plus grand que 1 et sans facteur carré, ce qui signifie que le seul carré parfait qui divise n est égal à un. L'équation est diophantienne ce qui signifie que les couples (x0, y0) recherchée sont des couples de nombres entiers. Toutes les solutions s'expriment à partir du couple solution formée 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 est connue des indiens depuis avant notre ère[2] :

1151^2 - 92\cdot 120^2 = 1 \;.

Histoire

Mathématiques indiennes

Les mathématiques indiennes s'intéressent très tôt à l'arithmétique. Âryabhata, un mathématicien du VIe siècle, établit les bases de l'arithmétique indienne. Il développe un système de numération montrant qu'il connaissait probablement la notation positionnelle ainsi que l'existence du zéro[3]. 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 kuaka (कूटटक) et qui signifie pulvérisateur car il casse les nombres en entiers plus petits. Il travaille aussi sur les fractions continues[4].

Le mathématicien indien Brahmagupta (598668) 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[5]. Brahmagupta en déduit trois algorithmes. Le premier lui permet de trouver une solution s'il dispose d'un couple d'entiers (x0, y0) 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 une troisième donnant le même résultat si l'image est égale à +/- 4. Une première version de la méthode chakravala 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[6]. Brahmagupta l'utilise en 628 dans son livre Brahmasphuta siddhanta pour résoudre l'équation suivante[7] :

x^2 - 83\cdot y^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 XIIe siècle, Bhāskara II innove 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[7] pour trouver une solution minimale à l'équation suivante déjà trouvée par Brahmagupta :

x^2 - 61\cdot y^2 = 1\;.

Le couple solution trouvé est :

x= 1\, 766 \, 319 \, 049\quad \text{et}\quad y = 226\, 153\, 980.

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 quel valeur de n. Deux raisons le laissent penser, tout d'abord la démonstration, longue et technique, demande une sophistication de loin supérieure aux mathématiques du XIIe siècle, ensuite si la preuve avait été trouvée il aurait paru clair que le passage par la méthode de Brahmagupta n'est pas nécessaire, même s'il accélère la convergence de l'algorithme[7]. De nouveaux exemples sont traités plus tard, par les mathématiciens indiens. Au XIVe siècle 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

Pierre de Fermat lance le 3 janvier 1658 un défi aux mathématiciens européens[8]. Il contient la recherche d'une solution au problème indien avec pour valeur de n 61, déjà traité par Brahmagupta et Bhāskara II. À cette époque l'Europe n'a pas connaissance des résultats de leurs prédécesseurs. Piqué au vif[9], la réaction anglaise est rapide, William Brouncker trouve un algorithme équivalent à celui de Bhāskara II, Bernard Frénicle de Bessy propose une table contenant toutes les solutions pour les valeurs de n inférieures à 150, qui sera finalement perdue, John Wallis redécouvre les résultats de Brahmagupta et les démontre rigoureusement. Frenicle de Bessy défie Brouncker avec la valeur n égal à 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[10].

Les deux questions théoriques sous-jacentes, à savoir si pour toute valeur de n strictement positive et sans facteur carré il existe une solution et si la solution trouvée génère bien toutes les autres est finalement résolue par Joseph Louis Lagrange en 1767[11].

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 plus grand que 1 et sans facteur carré :

(1) \quad x^2 - n\cdot y^2 = 1 \;.

Soient A l'anneau des nombres de la forme a + n.b, où a et b désignent deux nombres entiers, N l'application qui au nombre a + n.b associe a2 - n.b2 et φ l'application qui à a + n.b associe φ(a + n.b) = a - n.b.

La fonction N correspond à la norme de A au sens de la théorie algébrique des nombres. Elle possède une propriété bien utile. Un nombre α de A égal à a +n.b correspond à une solution (a, b) de l'équation (1) si et seulement si N(α) est égale à 1. Ainsi, l'équation (1) peut encore s'écrire N(ξ ) = 1. Pour cette raison si α est un élément de A vérifiant N(α) = 1, on dit que α est racine de l'équation (1).

La fonction φ possède aussi d'utiles propriétés. C'est un automorphisme de A :

\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'application φ est involutive c'est-à-dire que composée deux fois de suite avec elle-même, elle est égale à l'identité, ou encore son application inverse est égale à elle-même :

\forall \alpha \in \mathbb A \quad \varphi \circ \varphi (\alpha) = \alpha \;.

Enfin, l'application φ offre une expression de la norme :

\forall \alpha \in \mathbb A \quad \mathcal N(\alpha) = \alpha\cdot \varphi(\alpha).

Si l'on note α = a + n.b, elle provient du calcul suivant :

\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

Article détaillé : Identité de Brahmagupta.

La première propriété utilisée est la suivante :

  • Soit α et β deux éléments de A, alors :
\mathcal N(\alpha\cdot \beta) = \mathcal N(\alpha)\cdot \mathcal N(\beta)\;.

Si α = a1 + n.a2 et β = b1 + n.b2 cette égalité s'écrit :

(a_1b_1 + na_2b_2)^2 - n\cdot(a_1b_2+a_2b_1)^2 = (a_1^2 - na_2^2)\cdot(b_1^2 - nb_2^2)\;.

Cette égalité est connue sous le nom de Identité de Brahmagupta que les indiens l'appelaient Samasa. Pour se convaincre de son exactitude, il suffit d'exprimer N en fonction de l'automorphisme φ :

\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 particulier correspond à celui où β est un entier k, l'égalité prend la forme suivante :

  • Soit α un élément de A et k un entier, alors :
\mathcal N(k \alpha) = \mathcal N(k)\cdot \mathcal N(\alpha)= k^2\cdot \mathcal N(\alpha)\;.

Conséquences

  • Soit α un élément de A tel que N(α) = 1, alors α -1 est un élément de A et il vérifie N(α -1) = 1 et α -1 = φ(α).

En effet, dire que N(α) = 1, c'est dire que α.φ(α) = 1, ce qui montre que φ(α) est l'inverse de α et en appliquant φ à l'égalité α.φ(α) = 1, on obtient en remplaçant φ(α) par α -1 : α -1.φ(α -1) = 1

  • Si l'équation (1) admet une solution différente de +/- 1, alors elle admet une infinité de solutions distinctes.

En effet, si α est une solution, α -1 en est une aussi, d'après la proposition précédente et comme la norme d'un produit est égal au produit des normes, on dispose des égalités suivante :

\forall k \in\Z  \quad \mathcal N(u^k) = 1  \quad\text{et}\quad \mathcal N(-u^k) = 1\;.

Il suffit de démontrer que les puissances de α sont toutes distinctes. Cette réalité provient du fait que si un nombre réel x vérifie xk = 1, où k est un entier différent de 0, alors x est égal à +/- 1. Soit k et l deux entiers tel que αk = αl alors αk-l est égal à 1 et comme α est différent de 1 et -1, k - l est égal à 0.

Comprendre comment fait Brahmagupta pour résoudre l'équation (1) dépend de trois propositions, maintenant simples à démonter :

  • Soit α un élément de A tel que N(α) = -1, α 2 est solution de (1).

Il suffit de remarquer que la norme de α 2 est le carré de la norme de α et est égal à 1.

  • Soit α un élément de A tel que N(α) soit égal à +/- 2, alors 1/2.α2 est un élément de A solution de (1).

En effet, si α est égal à a + b.n alors un calcul montre que α2 = a2 + n.b2 + 2ab.n. Comme a2 + n.b2 = N(α) + 2.n.b2 et que N(α) et 2ab sont des multiples de 2, α2 l'est aussi. Le calcul suivant permet de conclure :

4\cdot \mathcal N \left(\frac {\alpha^2}2\right) =  \mathcal N \left(\alpha^2\right) = 4 \quad \text{et}\quad  \mathcal N \left(\frac {\alpha^2}2\right) = 1 \;.
  • Soit α un élément de A tel que N(α) soit égal à +/- 4 et tel que 2 ne divise pas α, alors 1/8.α3 est un élément de A de norme égale à +/- 1.

En effet, calculons α3 :

\alpha^3 = (a + b\cdot \sqrt n)^3 = a^3 + 3ab^2n + \sqrt n\cdot(nb^3 + 3a^2b) = a(a^2 -nb^2 + 4nb^2) + b\sqrt n\cdot(3a^2 - 3nb^2 + 4nb^2) \;.

En remarquant que N(α) = a 2 - n.b 2 = +/- 4, on obtient :

\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{avec}\quad \epsilon = \pm 1 \;.

Comme \epsilon est impair, il suffit de montrer que b est impair pour prouver que α3 est un multiple de 8. Si b est pair, n.b 2 est un multiple de quatre et comme N(α) = a 2 - n.b 2 est aussi un multiple de quatre, a est pair. Or par hypothèse α n'est pas un multiple de deux et a et b ne peuvent être pairs simultanément. En conséquence, b est impair et ε + nb2 ainsi que 3ε + nb2 sont pairs si n est impair. Ceci montre que α3 est bien un multiple de 8 si n est impair.

Or n est toujours impair. En effet, si n est pair, comme N(α) est pair, a l'est aussi et a 2 est un multiple de quatre, donc comme n n'a pas de facteur carré, n n'est pas un multiple de quatre donc b est pair et α est un multiple de 2, ce qui est contraire à l'hypothèse et termine la démonstration.

Ainsi la connaissance d'un élément α de norme égale à +/- 4 permet de trouver une solution. Si α est divisible par 2 dans A, 1/2.α est un élément de norme égale à +/- 1 et son carré est une solution. Sinon, 1/8.α3 est un élément de norme égale à +/- 1, un passage au carré permet encore de déterminer une solution.

Exemples

Exemple de Brahmagupta

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

x^2 - 83\cdot y^2 = 1 \;.

Choisissons comme premier essai α = 9 + 83 On remarque que N(α) = -2. Il est judicieux de calculer α2 :

\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)\;.

Une proposition précédente montre que 82 + 83.9 possède pour norme 1 et (82, 9) est solution de l'équation, en effet :

82^2 - 83\times 9^2 = 6\,724- 6\,723 = 1\;.

Défi de Fermat

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

x^2 - 61\cdot y^2 = 1 \;.

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

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

Puis il calcule 1/8.α3 et sa norme :

\frac 18\alpha^3 = \frac 14 (39 + 5\cdot\sqrt{61})\cdot(1\,523 + 195 \cdot\sqrt{61}) = 29\,718 + 3\,805 \cdot\sqrt{61}\quad \text{et}\quad \mathcal N (\frac 18\alpha^3) = 29\,718^2 - 61\times 3\,805^2 = -1.

La solution est donc 1/64.α6, soit :

\frac 1{64}\alpha^6=(29\,718 + 3\,805 \cdot\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\;.

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 de norme dans l'ensemble des nombres en valeur absolue égales à 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 une suite récurrente (αn) d'éléments de A de la manière suivante :

Le premier élément α1 de la suite est de la forme a1 + n. Il est choisi de telle manière à ce que la norme de α1, égale à a12 - n, soit la plus petite possible en valeur absolue.

Supposons la suite définie à l'ordre j. On note αj = aj + bj.n. On construit un élément βj = mj + n. Le nombre entier mj est tel que aj + mj.bj soit dans un multiple de la norme de αj et mj minimise la valeur absolue de la norme de βj. L'élément αj + 1 est défini de la manière suivante :

\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_jm_j + nb_j + \sqrt n(a_j + m_jb_j)\right)\;.

Exemples

Défi de Fermat

Choisissons encore d égal 61. La valeur de a 1 est égale à 8 pour minimiser la norme de α1, en effet :

\mathcal N(\alpha_1) = \mathcal N(8 +\sqrt{61}) = 8^2 - 61 = 3\;.

Pour déterminer la valeur de α2 il est nécessaire de calculer m 1. On dispose de l'égalité suivante :

\alpha_2 = a_2 + b_2\cdot\sqrt{61} = \frac 1{\mathcal N(\alpha_1)}\cdot \alpha_1\cdot \beta_1\; =\frac 13(8 +\sqrt{61})\cdot (m_1 +\sqrt{61}) = \frac {8m_1 + 61}{3} + \frac{8 + m_1}{3}\sqrt{61} \;.

Comme α2 est un élément de A, 8 + m 1 est un multiple de 3, ou encore m 1 est de la forme 3.k + 1. Pour minimiser la norme de β1, il faut choisir k égal à 2. On en déduit que m 1 est égal à 7, ce qui donne :

\alpha_2 = \frac {8\times 7 + 61}3+ \frac{8 + 7}3\sqrt{61} = 39 + 5\cdot\sqrt{61} \quad \text{et}\quad \mathcal N(\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. Si d est égal à 103, la valeur de a 1 est égale à 10 et :

\mathcal N(\alpha_1) = \mathcal N(10 + \sqrt{103}) = 10^2 - 103 = -3\;.

Le calcul de α2 donne :

\alpha_2 = a_2 + b_2\cdot\sqrt{103} = \frac 13(10 +\sqrt{103})\cdot (m_1 +\sqrt{103})=\frac {10\cdot m_1 + 103}{3} + \frac{10 + m_1}{3}\sqrt{103}\;.

Cette fois-ci, m 1 est de la forme 3.k - 1. Pour minimiser la norme de β1, il faut choisir m 1 égal à 11. On obtient :

\alpha_2 = \frac {10\times 11 + 103}{3} + \frac{10 + 11}{3}\sqrt{103} = 71 + 7\cdot\sqrt{103} \quad \text{et}\quad \mathcal N(\alpha_2) = -6\;.

Le calcul de α3 donne :

\alpha_3 = \frac 16(71 + 7\cdot\sqrt{103})\cdot (m_2 +\sqrt{103})=\frac {71\cdot m_2 + 7\times 103}{6} + \frac{71 + 7\cdot m_2}{6}\sqrt{103}\;.

Cette fois ci, m 2 est de la forme 6.k - 5. Pour minimiser la norme de β2, il faut choisir m 2 égal à 7. On obtient :

\alpha_3 = 203 + 20\cdot\sqrt{103} \quad \text{et}\quad \mathcal N(\alpha_3) = 9\;.

Le calcul de α4 donne :

\alpha_4 = \frac {203\cdot m_3 + 20\times 103}{9} + \frac{203 + 20\cdot m_3}{9}\sqrt{103}\;.

Cette fois-ci, m 3 est de la forme 9.k + 2. Pour minimiser la norme de β3, il faut choisir m 3 égal à 11. On obtient :

\alpha_4 = 477 + 47\cdot\sqrt{103} \quad \text{et}\quad \mathcal N(\alpha_4) = 2\;.

Le calcul de Brahmagupta permet de conclure, la valeur α cherchée est égal à 1/2.α42 :

\alpha = \frac 12 \alpha_4^2 =\frac 12 (477 + 47\cdot\sqrt{103})^2 = 227\,528 + 22\;419\cdot\sqrt{103}.

Démonstrations associées à l'apport de Bhāskara II

Lemmes

Deux lemmes démontrent l'existence de la suite utilisée par Bhāskara II. Avec les notations des paragraphes précédents et si kj désigne la valeur absolue de la norme de αj, on utilise les éléments suivants :

\forall j\in\N \quad k_j\cdot\alpha_{j+1} = \beta_j\cdot\alpha_j \quad\text{avec}\quad \alpha_j = a_j + b_j\cdot \sqrt n\quad \text{et}\quad \beta_j = m_j + \sqrt n.

On a choisi mj de telle manière que :

 k_j\cdot b_{j+1} = a_j + b_j\cdot m_j \quad\text{avec}\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\;.

Les deux exemples précédents illustrent le fait que αjj est bien un multiple de kj. Cette propriété est l'objet des deux lemmes suivants :

  • Avec les notations précédentes, si aj + bj.mj est choisi multiple de kj et si aj , bj sont premiers entre eux alors , αjj est un multiple de kj.
  • Sous réserve des hypothèses du lemme précédent et si la norme de βj est choisie minimale en valeur absolue, aj+1, bj+1 sont premiers entre eux.

Une fois ces lemmes démontrés, on remarque qu'il est toujours possible de trouver une valeur convenable pour m j. En effet, comme a j et b j sont premiers entre eux, l'identité de Bézout montre qu'il existe un entier c j tel que c j.b j - 1 soit un multiple de k j. On en déduit que si x est un entier, x.k j + c j.b j.a j est un multiple de k j, il est alors toujours possible de choisir x de telle manière à ce que la valeur absolue de la norme de β j soit minimale. Trouver c j revient à résoudre l'identité de Bézout, ce que les indiens savent déjà faire avec l'algorithme d'Euclide.

Les lemmes montrent que si m j est choisi selon la méthode du paragraphe précédent, αjj est un multiple de k j, αj+1 est un élément de A et a j+1 et b j+1 sont premiers entre eux deux, ce qui permet de réitérer la démarche.

Caractère cyclique

Une fois montrée que la suite (αj) est bien définie, étudions son comportement. Il est cyclique en un certain sens. Plus précisément, remarquons que la relation R définie par α R β si et seulement s'il existe un élément inversible ε de A tel que α = ε.β est une relation d'équivalence. On note cl(α) la classe d'équivalence de α par la relation R :

  • La suite (clj)) est cyclique.

Cette propriété est la conséquence de trois propositions :

  • La suitej) est définie de manière univoque et la suite (N(αj)) est bornée.

L'égalité N (ε.β) = N(ε).N(β) = ±N(β) montre que tous les éléments d'une même classe ont même norme en valeur absolue. Il est alors possible de parler de la norme en valeur absolue d'une classe d'équivalence, ce qui permet l'expression de la proposition suivante :

  • Il n'existe qu'un nombre fini de classes d'équivalence de norme en valeur absolue inférieure à un entier strictement positif.

Enfin :

  • Soient i et j deux entiers positifs et ε un élément de A inversible. Si αi = ε.αj alors αi+1 = ε.αj+1.

Avec ces trois propriétés, il devient simple de comprendre que la suite (clj) est périodique au bout d'un certain rang. En effet, la suite (N(αj)) est bornée, elle ne prend ces valeurs que dans un nombre fini de classes d'équivalence d'après la proposition deux. Au bout d'un certain rang, la suite a pour image une classe d'équivalence déjà atteinte. La troisième proposition montre que la suite est alors nécessairement périodique.

Ces propriétés ne démontrent que la périodicité à partir d'un certain rang. Le paragraphe suivant montre que ce rang est égal à zéro et la suite est périodique dès l'indice zéro.

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 à un en valeur absolue. Tel est pourtant toujours le cas :

  • Il existe une valeur j strictement supérieure à zéro et telle que la norme de αj soit égale à 1 en valeur absolue.

La suite (αk) forme une espèce de palindrome, plus précisément si G désigne le groupe des unités :

  • Selon que la première valeur j strictement positive tel que αj soit de norme égale à un en valeur absolue est paire ou impaire, l'une des deux configurations suivantes se réalise :
\text{Si j est pair : } \exists k\in\N \quad j=2k \text{ et } \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

et :

\text{Si j est impair : } \exists k\in\N \quad j=2k+1 \text{ et } \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 .

Une conséquence directe est que la suite (αk) contient une solution de l'équation de Pell pour m égal à 1 :

  • Soit j la plus petite valeur strictement positive telle que la norme de αj soit égale à 1 en valeur absolue, la norme de α2j est strictement positive et égale à 1.


Fraction continue

Article détaillé : Fraction continue.

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

\sqrt n = f_0 + \cfrac1{f_1 + \cfrac{1}{f_2 + \frac1{f_3+\,\cdots}}}\quad \text{avec}\quad f_i\in\Z \;.

Introduction par l'exemple

Étudions le cas où n est égal à 19.

À l'ordre 0, l'objectif est de trouver la valeur f0 la plus proche possible de 19. On obtient l'égalité :

\sqrt{19} = 4 + (-4 +\sqrt{19}) \quad\text{et}\quad f_0 = 4,\quad \omega_0 = -4 +\sqrt{19}.

Ici, ωk désigne le reste de la fraction continue, souvent appelé quotient complet d'indice k.

À l'ordre 1, on cherche une approximation 19 de la forme f0 + 1/f1 la meilleure possible, on obtient :

-4 +\sqrt{19}= \frac 3{4 +\sqrt{19}} = \frac 1{\frac{9 - 5 +\sqrt{19}}3} = \frac 1{3 + \frac13(-5 +\sqrt{19})}\quad\text{et}\quad\sqrt{19}= 4 + \frac 1{3 + \omega_1},\; f_1 = 3,\; \omega_1 = \frac 13(-5 +\sqrt{19}).

À l'ordre 2 :

\frac 13(-5 +\sqrt{19}) = \frac {-6}{3(5 + \sqrt{19})} = \frac 1{-\frac{10 - 5 +\sqrt{19}}2} = \frac 1{-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 13(5 -\sqrt{19}) .

À l'ordre 3 :

\frac 12(5 -\sqrt{19}) = \frac6{2(5 +\sqrt{19})} = \frac 1{\frac{9 - 4 +\sqrt{19}}3} = \frac 1{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 13(-4 +\sqrt{19}) .

À l'ordre 4 :

\frac 13(-4 +\sqrt{19}) = \frac3{3(4 +\sqrt{19})} = \frac 1{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 = \omega_1 = -4 +\sqrt{19}.

Le fait que ω4 soit égal à ω0 montre que la suite (fk) est périodique, ces termes sont : f0, f1, f2, f3, f4, f1, f2, f3, f4, f1, … On note généralement une égalité de ce type de la manière suivante :

\sqrt{19}= [4, \overline{3,-5,3,8}].

Déterminons les fractions partielles à l'ordre k θk, habituellement appelées réduite d'indice k.

\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}.

Le calcul de la suite (αk) de la méthode chakrala donne :

\alpha_1 = 4 -\sqrt{19},\; \alpha_2 = 13 - 3\cdot\sqrt{19},\; \alpha_3 = 61 - 14\cdot\sqrt{19},\; \alpha_4 = 170 - 39\cdot\sqrt{19}.

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 :

170^2 - 19\times 39^2 = 28\,900 - 28\;899 = 1\;.

Remarque : La convention choisie ici pour définir la fraction est que 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. Non seulement chaque réduite d'indice k doit être aussi proche que possible de la racine mais de plus la suite (fk) doit ne prendre que des valeurs positives. La convention des fractions continues peut aussi s'appliquer à la méthode de chakravala, elle revient à imposer à la suite des normes des (βk) d'être strictement négative. Toutes les démonstrations s'appliquent encore avec cette convention. En revanche, la longueur du cycle peut être plus longue, par exemple :

\sqrt{19}= [4, \overline{2,1,3,1,2,8}].

Approche théorique

Soit (fk) et (θk) où k est un entier positif, deux suites dont la première est à valeur dans Z et la deuxième dans A. Les suites sont définies par récurrence. La valeur f0 est égale à la partie entière de n, où n est un entier strictement supérieur à 1 et sans facteur carré, et θ0 l'élément de A défini par l'égalité :

\sqrt n = f_0 + \frac 1{\theta_0}.

La valeur 1 / fk+1 est la meilleure approximation de θk et θk+1 est l'élément de A vérifiant l'égalité :

\theta_k = f_{k+1} + \frac 1{\theta_{k+1}}.

Cette définition diffère légèrement de la traditionnelle fraction continue car fk n'est pas nécessairement choisi positif. On remarque de fk+1 et le plus grand entier plus petit que 1/θk. Le fait que n soit irrationnel montre que θk est toujours irrationnel, les suites (fk) et (θk) ne prennent jamais la valeur 0 et sont ainsi bien définies.

Soit (c k) et (d k) les deux suites de Z telles que pour tout k, c k et c d soient premiers entre eux et la fraction c k / d k soit égale à la fraction réduite d'indice k.

  • Pour tout nombre entier k, sik) etk) désignent les suites de la méthode chakravala définies précédemment, les égalités suivantes sont vérifiées :
 \forall k\in\N \quad \alpha_{k+1} = c_k + d_k\cdot \sqrt n \quad \text{et}\quad \theta_k = (-1)^{k+1}\frac {\varphi(\beta_k)}{\mathcal N(\alpha_k)}\;.

Ainsi, la méthode chakravala permet de démontrer le caractère périodique et la propriété de palindrome d'une fraction continue. Si l'algorithme récursif impose à la suite (βk) d'être aussi 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, c'est-à-dire que les suites (fk) et (θk) sont à valeurs strictement positives.

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 α0 est égal à 1 et α1 = β0 = 18 + 313 car 182 est la meilleure approximation de 313 dans les carrés parfaits, la norme de α1 est égal à 11. On en déduit la valeur de f 0 = 18.

Pour le calcul de m1, il suffit de remarquer que m1 + m0 est un multiple de 11 et que m12 est la meilleure approximation possible de 313, on trouve m1 = 15. On calcule ensuite celle β1 égale à 152 - 313 = -88. Pour le calcul de la norme de α2 il suffit de remarquer qu'elle est le quotient de celle de β1 par celle de α1, on trouve -8. Pour le calcul de f 1 on utilise la formule du paragraphe précédent, on trouve f 1 = - 1/11 (18 + 15) = -3.

Pour le calcul des valeurs ak et bk, on utilise la formule de récurrence. On construit ainsi le tableau suivant :

Indice mk N(βk) = mk2 - 313 N(αk) = N(βk-1)/N(αk-1) fk = (-1)k(mk + mk-1)/N(αk) ak = fk-1.ak-1 + ak-2 bk = fk-1.bk-1 + bk-2
0 18 11 1 m0 = 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


Cette approche permet d'éviter les grands nombres, sauf pour les colonnes a k et b k. On remarque que la norme de α7 est l'opposée de cette de α8, ce qui montre que ces deux nombres sont à un facteur inversible près l'image par la fonction φ l'un de l'autre. La suite des normes est donc 1, 11, -8, 3, 16, -9, 13, -13, 9, -16, -3, 8, -11, -1. On en déduit que 1/13.α78 est un élément de norme -1 :

 \alpha_{13}=\frac 1{13}\cdot \alpha_7\cdot \alpha_8 = (19\,001 + 1\,074\cdot \sqrt 313)\cdot(43\,398 + 2\,453\cdot\sqrt 313)= 126\,862\,368 + 7\;170\;685\cdot\sqrt 313 .

Il faut encore mettre ce nombre α13 au carré pour obtenir la solution recherchée :

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

La méthode chakravala permet ainsi de résoudre à la main ce type de calcul, même si la solution s'exprime de manière un peu fastidieuse. La même démarche, sans le calcul des colonnes a k et b k, inutile pour cet objectif, permet de déterminer la fraction continue 313. 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 trouve : 17, 1, 2, 4, 11, 1, 1, 3, 2 qui termine cette branche du palindrome. On en déduit que les termes suivants sont : 2, 3, 1, 1, 11, 4, 2, 1. Il est relativement simple de montrer que le terme d'après est nécessairement 34, le double du premier terme. Ce qui donne :

\sqrt{313} = [17, \overline{1,2,4,11,1,1,3,2,2,3,1,1,11,4,2,1,34}].

Références

Notes

  1. (en) Clas-Olof Selenius, Rationale of the chakravāla process of Jayadeva and Bhāskara II in Historia Mathematica 2 (1975), p. 167-184
  2. (en) Harold Edwards, Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory, Springer, 3e éd., 2000 (ISBN 978-0-387-95002-0)
  3. 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)
  4. Une analyse précise de son œuvre mathématique est disponible dans la thèse de doctorat d'A. Keller, Un commentaire indien du VIIe siècle – Bhāskara et le ganita-pāda de l’Āryabhatīya [lire en ligne].
  5. (en) John Stillwell (en), Mathematics and its History, Springer, 3e éd., 2010 (ISBN 978-1-44196052-8), p. 75-80
  6. (en) B. L. van der Waerden, Pell's Equation in Greek and Hindu Mathematics, Russ. Math Surveys 31 (5), 1976, p. 210-225
  7. a, b et c (en) John J. O’Connor et Edmund F. Robertson, « Pell's equation », dans MacTutor History of Mathematics archive, université de St Andrews [lire en ligne] .
  8. Laurent Hua et Jean Rousseau, Fermat a-t-il démontré son grand théorème ? l'hypothèse "Pascal", L'Harmattan, 2002 (ISBN 978-2-74752836-8), p. 113
  9. John Wallis, un mathématicien anglais, rétorqua : il ne trouvera pas mauvais, je crois, que nous lui rendions la pareille, et cela, non pas sur une bagatelle. Ces informations sont extraites du site : Pierre de Fermat de la commune de Beaumont-de-Lomagne.
  10. Ces informations proviennent de la compilation des échanges épistolaires entre les différents acteur. Ils sont publiés sous la référence : (la) John Wallis, Commercium epistolicum de quæstionibus quibusdam mathematicis nuper habitum Oxonii : Excudebat A. Lichfield, Impensis Tho. Robinson, 1658
  11. Le texte original de la solution de Lagrange par les fractions continuées est disponible : Solution d'un problème d'arithmétique

Lien externe

(en) John J. O’Connor et Edmund F. Robertson, « Indian Mathematics: Redressing the balance, 8 VI. Pell's equation », dans MacTutor History of Mathematics archive, université de St Andrews [lire en ligne] .

Références

  • (en) Leonard Eugene Dickson, History of the Theory of Numbers [détail des éditions] 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)

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Méthode chakravala de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Methode chakravala — Méthode chakravala Aryabhata s intéresse à l arithmétique. Il établit les fondements de la méthode chakravala. En mathématiques et plus précisément en arithmétique, la méthode chakravala est un algorithme pour résoudre les équations… …   Wikipédia en Français

  • Méthode Chakravala — Aryabhata s intéresse à l arithmétique. Il établit les fondements de la méthode chakravala. En mathématiques et plus précisément en arithmétique, la méthode chakravala est un algorithme pour résoudre les équations diophantiennes équivalentes à… …   Wikipédia en Français

  • Chakravala method — The chakravala method (Hindi: चक्रवाल विधि) is a cyclic algorithm to solve indeterminate quadratic equations, including Pell s equation. It is commonly attributed to Bhāskara II, (c. 1114 – 1185 CE)[1][2] although some attribute it to Jayadeva (c …   Wikipedia

  • Equation de Pell — Équation de Pell Fermat Pierre de Fermat montre que l équation de Pell Fermat possède toujours une infinité de solutions si m est égal à un en valeur absolue. En mathématiques et plus précisément en arithmétique, l équation de Pell Fermat est une …   Wikipédia en Français

  • Équation de Pell — Fermat Pierre de Fermat montre que l équation de Pell Fermat possède toujours une infinité de solutions si m est égal à un en valeur absolue. En mathématiques et plus précisément en arithmétique, l équation de Pell Fermat est une équation… …   Wikipédia en Français

  • Équation de Pell-Fermat — Pierre de Fermat montre que l équation de Pell Fermat possède toujours une infinité de solutions si m est égal à un en valeur absolue. En mathématiques et plus précisément en arithmétique, l équation de Pell Fermat est une équation diophantienne… …   Wikipédia en Français

  • Équation de pell — Fermat Pierre de Fermat montre que l équation de Pell Fermat possède toujours une infinité de solutions si m est égal à un en valeur absolue. En mathématiques et plus précisément en arithmétique, l équation de Pell Fermat est une équation… …   Wikipédia en Français

  • Theorie des nombres — Théorie des nombres Traditionnellement, la théorie des nombres est une branche des mathématiques qui s occupe des propriétés des nombres entiers, qu ils soient entiers naturels ou entiers relatifs, et contient beaucoup de problèmes ouverts qu il… …   Wikipédia en Français

  • Théorie des nombres — Traditionnellement, la théorie des nombres est une branche des mathématiques qui s occupe des propriétés des nombres entiers, qu ils soient entiers naturels ou entiers relatifs, et contient beaucoup de problèmes ouverts qu il est facile de… …   Wikipédia en Français

  • Fraction continue d'un nombre quadratique — Joseph Louis Lagrange établit de manière rigoureuse les propriétés des fractions continues des nombres quadratiques. En mathématiques, et plus précisément en arithmétique, la fraction continue d un nombre quadratique correspond à la… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”