En mathématiques et plus précisément en arithmétique, la méthode chakravala (sanskrit : चक्रवाल, « roue » + « crin/poil ») est un algorithme cyclique 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
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 avec Aryabhata, suivi par Brahmagupta. Initiée par , elle fut développée plus avant par Bhāskara II.
Selenius l'évalue par :
Il faut en effet attendre le 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.
vignette|Aryabhata établit les fondements de la méthode chakravala.
Objectif Une forme d'équation de Pell-Fermat s'exprime de la manière suivante :
où n est un entier naturel non carré. L'équation est diophantienne ce qui signifie que les couples 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 . :
Histoire Mathématiques indiennes Les mathématiques indiennes s'intéressent très tôt à l'arithmétique. Aryabhata, un mathématicien du , 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éroGeorges Ifrah, Histoire universelle des chiffres : L'intelligence des hommes racontée par les nombres et le calcul, Robert Laffont, 1994 .. 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 continuesUne analyse précise de son œuvre mathématique est disponible dans la thèse de doctorat d'A. Keller, Un commentaire indien du – Bhāskara et le ganita-pāda de l’Āryabhatīya ..
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, 2010, .. 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 B. L. van der Waerden, Pell's Equation in Greek and Hindu Mathematics, Russ. Math Surveys 31 (5), 1976, . Brahmagupta l'utilise en 628 dans son livre Brahmasphuta siddhanta pour résoudre l'équation suivante :
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 , 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 :
Le couple solution trouvé est :
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 . De nouveaux exemples sont traités plus tard, par les mathématiciens indiens. Au 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 de la même annéeVoir la page Pierre Fermat sur le site de la commune de Beaumont-de-Lomagne.), Pierre de Fermat défie Bernard Frénicle de BessyŒuvres de Fermat, . 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 trouverCes informations sont tirées des échanges épistolaires entre les différents acteurs, publiés dans John Wallis, , 1658.
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 1767Joseph-Alfred Serret, Œuvres de Lagrange, vol. I, : « Solution d'un problème d'arithmétique »., 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, 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é :
Soient A l'anneau des nombres de la forme a + b, 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é » :
La fonction N correspond à la norme de A au sens de la théorie algébrique des nombres. Un élément a + b de A est appelé racine de l'équation (1) si et seulement si sa norme vaut 1, c'est-à-dire si (a, b) est solution de (1).
La fonction φ possède aussi d'utiles propriétés. C'est un automorphisme de A :
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 :
Enfin, le produit de deux éléments conjugués est égal à leur norme commune :
Si l'on note α = a + b, cela est justifié par le calcul suivant :
Samasa
La première propriété utilisée est la suivante :
Si α = a1 + a2 et β = b1 + b2, cette égalité s'écrit :
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 φ :
Un cas particulier correspond à celui où β est un entier k, l'égalité prend la forme suivante :
Conséquences
En effet, N(α) = N(φ(α)) = αφ(α), et si α est une solution de (1) alors α 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 :
: immédiat. : si α = a + b alors α2 = a2 + nb2 + 2ab = N(α) + 2nb2 + 2ab est divisible par 2 (et 2N(α/2) = N(α) = (±2) donc N(α/2) = 1). : les deux premiers cas sont immédiats et dans le troisième, n, a et b sont impairs, si bien que α est divisible par 8 car
Exemples Exemple de Brahmagupta Traitons avec cette méthode l'exemple de Brahmagupta suivant :
Soit α = m + , l'entier m étant choisi tel que la norme N(α) = m – 83 soit la plus petite possible en valeur absolue : m = 9, α = 9 + , N(α) = –2. Une proposition précédente montre que α/2 est une solution. Effectivement :
et
Défi de Fermat Le défi de Fermat se résout de la même manière :
Brahmagupta s'y prend de la manière suivante : il remarque que si α = 39 + 5 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 :
Puis il calcule α3/8 et sa norme :
La solution est donc α6/64, soit :
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 α = a + b de A de la manière suivante. Le premier élément de la suite est α = 1, de norme k = 1. Supposons la suite définie à l'ordre j. On construit un élément βj = m + . L'entier naturel. m est tel que a + mb soit multiple de la norme k de α — autrement dit tel que bm soit congru à –a modulo k — et mj minimise la valeur absolue de la norme m – n de β. L'élément αj + 1 est alors défini par
ou encore
le ± correspondant au signe de N(α) .
On verra plus loin que la condition « a + mb multiple de k » équivaut à « m congru à –m modulo k », ce qui simplifie l'algorithme.
Exemples Défi de Fermat Choisissons encore n égal à 61 .. La valeur de m est égale à 8 pour minimiser |N(β)|. En effet, est compris entre 7 et 8 et 8 – 61 = 3 < 61 – 7. L'entier m est ensuite choisi parmi ceux congrus, modulo N(α) = N(8 + ) = 8 – 61 = 3, à –m = –8 donc à 1. Des deux termes consécutifs 7 et 10 de cette suite arithmétique qui encadrent , celui qui minimise |N(β)| est m = 7, ce qui donne :
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, m = 10. L'entier m est ensuite choisi congru à –10 modulo N(α) = N(10 + ) = 10 – 103 = –3. Comme 8 < < 11 et 11 – 103 = 18 < 103 – 8, on obtient m = 11 et
On choisit ensuite m congru à –11 modulo 6. Comme 7 < < 13 et 103 – 7 = 54 < 13 – 103, on obtient m = 7 puis
Puis, modulo 9, m doit être congru à –7. Pour minimiser |N(β)|, il faut choisir m égal à 11. On obtient
Le calcul de Brahmagupta permet de conclure : la valeur cherchée est
Non-unicité