Méthode chakravala

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 -ny^2 = 1 \quad \text{avec} \quad n\in\N\setminus\{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.

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

Objectif[modifier | modifier le code]

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

x^2 - ny^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és sont des couples de nombres 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 est connue des Indiens depuis avant notre ère[2] :

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

Histoire[modifier | modifier le code]

Mathématiques indiennes[modifier | modifier le code]

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 un 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 - 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 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 - 61y^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[modifier | modifier le code]

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, sont finalement résolues par Joseph Louis Lagrange en 1767[11].

Apports de Brahmagupta[modifier | modifier le code]

Décors[modifier | modifier le code]

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 - ny^2 = 1.

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

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 + nb 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 A \quad \varphi(\alpha\beta) = \varphi(\alpha)\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 A \quad \varphi \circ \varphi (\alpha) = \alpha.

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

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

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

\mathcal N(\alpha) = a^2 - nb^2 = (a + \sqrt n b)(a - \sqrt nb) = \alpha\varphi(\alpha).

Samasa[modifier | modifier le code]

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\beta) = \mathcal N(\alpha)\mathcal N(\beta).

Si α = a1 + na2 et β = b1 + nb2, cette égalité s'écrit :

(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).

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

\mathcal N(\alpha\beta) = \alpha \beta\varphi (\alpha \beta) = \alpha\varphi (\alpha)\beta \varphi(\beta) = \mathcal N(\alpha)\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)\mathcal N(\alpha)= k^2\mathcal N(\alpha).

Conséquences[modifier | modifier le code]

  • 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 suivantes :
    \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. Ce résultat 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. Soient k et l deux entiers tels que αk = αl alors αk – l est égal à 1 et comme α est différent de 1 et –1, k – l est nul.

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

  • 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(α) = ±2, alors α2/2 est un élément de A solution de (1).
    En effet, si α est égal à a + bn alors α2 = a2 + nb2 + 2abn. Comme a2 + nb2 = N(α) + 2nb2 et que N(α) et 2ab sont des multiples de 2, α2 l'est aussi. Le calcul suivant permet de conclure :
    4\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 α3/8 est un élément de A de norme égale à ±1.
    En effet :
    \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).
    En remarquant que N(α) = a2nb2 = ±4, on obtient :
    \alpha^3 = 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 = \pm 1.
    Comme ε est impair, il suffit de montrer que b est impair pour prouver que α3 est un multiple de 8. Si b est pair, nb 2 est un multiple de 4 et comme N(α) = a2nb2 est aussi un multiple de 4, a est pair. Or par hypothèse α n'est pas un multiple de 2 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 a2 est un multiple de 4, donc comme n n'a pas de facteur carré, n n'est pas un multiple de 4 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, α/2 est un élément de norme égale à ±1 et son carré est une solution. Sinon, α3/8 est un élément de norme égale à ±1, un passage au carré permet encore de déterminer une solution.

Exemples[modifier | modifier le code]

Exemple de Brahmagupta[modifier | modifier le code]

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

x^2 - 83y^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 + 983 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[modifier | modifier le code]

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 + 561 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/2 :

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

Puis il calcule α3/8 et sa norme :

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

La solution est donc α6/64, soit :

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

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

Apport de Bhāskara II[modifier | modifier le code]

Principe de la méthode[modifier | modifier le code]

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 manière à ce que la norme de α1, égale à a12n, soit la plus petite possible en valeur absolue.

Supposons la suite définie à l'ordre j. On note αj = aj + bjn. On construit un élément βj = mj + n. Le nombre entier mj est tel que aj + mjbj 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[modifier | modifier le code]

Défi de Fermat[modifier | modifier le code]

Choisissons encore d égal 61. La valeur de a1 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 m1. On dispose de l'égalité suivante :

\alpha_2 = a_2 + b_2\sqrt{61} = \frac 1{\mathcal N(\alpha_1)}\alpha_1\beta_1\; =\frac 13(8 +\sqrt{61})(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 + m1 est un multiple de 3, ou encore m1 est de la forme 3k + 1. Pour minimiser la norme de β1, il faut choisir k égal à 2. On en déduit que m1 est égal à 7, ce qui donne :

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

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[modifier | modifier le code]

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 a1 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\sqrt{103} = \frac 13(10 +\sqrt{103})(m_1 +\sqrt{103})=\frac {10 m_1 + 103}{3} + \frac{10 + m_1}{3}\sqrt{103}.

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

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

Le calcul de α3 donne :

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

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

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

Le calcul de α4 donne :

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

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

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

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

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

Démonstrations associées à l'apport de Bhāskara II[modifier | modifier le code]

Lemmes[modifier | modifier le code]

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\alpha_{j+1} = \beta_j\alpha_j \quad\text{avec}\quad \alpha_j = a_j + b_j\sqrt n\quad \text{et}\quad \beta_j = m_j + \sqrt n.

On a choisi mj de telle manière que :

 k_j b_{j+1} = a_j + b_j m_j \quad\text{avec}\quad  \beta_j\alpha_j = a_jm_j + nb_j + (a_j + b_jm_j)\sqrt n.

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

  • Avec les notations précédentes, si aj + bjmj est choisi multiple de kj et si aj, bj sont premiers entre eux alors, αjβj 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 aj et bj sont premiers entre eux, l'identité de Bézout montre qu'il existe un entier cj tel que cjbj - 1 soit un multiple de kj. On en déduit que si x est un entier, xkj + cjbjaj est un multiple de kj, 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 cj 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 mj est choisi selon la méthode du paragraphe précédent, αjβj est un multiple de kj, αj + 1 est un élément de A et aj + 1 et bj + 1 sont premiers entre eux deux, ce qui permet de réitérer la démarche.

Caractère cyclique[modifier | modifier le code]

Une fois montré 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 (Nj)) 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 (Nj)) est bornée, elle ne prend ces valeurs que dans un nombre fini de classes d'équivalence d'après la proposition 2. 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 à 0 et la suite est périodique dès l'indice 0.

Structure de la suite[modifier | modifier le code]

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 :

  • Il existe une valeur j strictement supérieure à 0 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 telle que αj soit de norme égale à 1 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[modifier | modifier le code]

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[modifier | modifier le code]

É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{-5 +\sqrt{19}}3.

À l'ordre 2 :

\frac{-5 +\sqrt{19}}3= \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{5 -\sqrt{19}}2.

À l'ordre 3 :

\frac{5 -\sqrt{19}}2= \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{-4 +\sqrt{19}}3.

À l'ordre 4 :

\frac{-4 +\sqrt{19}}3= \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_0 = -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 chakravala donne :

\alpha_1 = 4 -\sqrt{19},\; \alpha_2 = 13 - 3\sqrt{19},\; \alpha_3 = 61 - 14\sqrt{19},\; \alpha_4 = 170 - 39\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[modifier | modifier le code]

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 (ck) et (dk) les deux suites d'entiers relatifs telles que pour tout k, c k et dk soient premiers entre eux et la fraction ck/dk 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\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[modifier | modifier le code]

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 f0 = 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 f1, on utilise la formule du paragraphe précédent ; on trouve f1 = –(18 + 15)/11 = –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–1ak–1 + ak–2 bk = fk–1bk–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 ak et bk. 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 α7α8/13 est un élément de norme –1 :

 \alpha_{13}=\frac {\alpha_7\alpha_8}{13} = (19\,001 + 1\,074\sqrt{313})(43\,398 + 2\,453\sqrt{313})= 126\,862\,368 + 7\;170\;685\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\sqrt{313})^2 =   32\;188\;120\;829\;134\;849 + 1\;819\;380\;158\;564\;160\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 ak et bk, inutile pour cet objectif, permet de déterminer la fraction continue 313. Rechercher la solution telle que la suite (fk) ne comporte que des valeurs positives suppose de restreindre le choix aux mk 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[modifier | modifier le code]

Notes[modifier | modifier le code]

  1. (en) Clas-Olof Selenius, « Rationale of the chakravāla process of Jayadeva and Bhāskara II », Historia Mathematica, vol. 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, Mathematics and Its History [détail des éditions], 2010, 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[modifier | modifier le code]

(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[modifier | modifier le code]