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
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 VIe siècle avec Aryabhata, suivi par Brahmagupta. Initiée par Jayadeva (en), elle fut développée plus avant par Bhāskara II.
Selenius l'évalue par : « La méthode représente un algorithme de meilleure approximation de longueur minimale qui, en raison de plusieurs propriétés de minimisation, produit automatiquement […], à moindre coût […] et en évitant les grands nombres, les plus petites solutions de l'équation […] La méthode chakravāla précéda les méthodes européennes de plus de mille ans. Mais aucune performance européenne dans le champ entier de l'algèbre, beaucoup plus tard après Bhāskara […], n'égala la merveilleuse complexité et l'ingéniosité de chakravāla[1]. »
Il faut en effet attendre le XVIIe siècle pour que les Européens, qui ignoraient les travaux des mathématiciens indiens, découvrent des algorithmes — moins performants[1] — résolvant le même problème.
![](http://up.wiki.x.io/wikipedia/commons/thumb/a/af/2064_aryabhata-crp.jpg/220px-2064_aryabhata-crp.jpg)
Objectif
modifierUne 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 (x, y) recherchés sont des couples d'entiers. Toutes les solutions s'expriment à partir du couple solution formé de deux entiers minimaux en valeur absolue dans l'ensemble des solutions. La méthode chakravala permet d'obtenir un couple de cette nature.
L'égalité suivante est un exemple de solution ; elle était connue des Indiens du VIIe siècle[2] :
Histoire
modifierMathématiques indiennes
modifierLes mathématiques indiennes s'intéressent très tôt à l'arithmétique. Aryabhata, un mathématicien du VIe siècle, en établit les bases. Il développe un système de numération montrant qu'il connaissait probablement la notation positionnelle ainsi que l'existence du zéro[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 kuṭṭaka (कूटटक) 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 (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[5]. 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[6]. Brahmagupta l'utilise en 628 dans son livre Brahmasphuta siddhanta pour résoudre l'équation suivante[7] :
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 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[7] 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 XIIe siècle[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
modifierEn février 1657 (à la suite d'un autre défi plus célèbre datant du 3 janvier de la même année[8]), Pierre de Fermat défie Bernard Frénicle de Bessy[9] 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[10].
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[11], 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, A. A. Krishnaswami Ayyangar (en) affirme être le premier à prouver celle de chakravala[12].
Apports de Brahmagupta
modifierDécors
modifierLes 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 + √nb, 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 + √nb 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 + √nb, cela est justifié par le calcul suivant :
Samasa
modifierLa première propriété utilisée est la suivante :
Soit α et β deux éléments de A, alors :
Si α = a1 + √na2 et β = b1 + √nb2, 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 :
Soit α un élément de A et k un entier, alors :
Conséquences
modifier
- Soit α un élément de A de norme 1, alors φ(α) est inverse de α et de norme 1.
- Si l'équation (1) admet une solution différente de ±1, alors elle admet une infinité de solutions distinctes.
En effet, N(α) = N(φ(α)) = αφ(α), et si α est une solution de (1) alors αk aussi pour tout entier naturel k (car la norme d'un produit est égale au produit des normes), or les puissances d'un réel différent de 0, 1 et –1 sont toutes distinctes.
Comprendre comment fait Brahmagupta pour résoudre l'équation (1) dépend de trois propositions :
Soit α un élément de A.
- Si N(α) = ±1 alors α2 est une solution de (1).
- Si N(α) = ±2 alors α2/2 est une solution de (1).
- Si N(α) = 4ε avec ε = ±1 alors une solution de (1) est :
- si α est divisible par 2 : (α/2)(3–ε)/2 ;
- si n est pair[13] : α2/4 ;
- sinon : (α3/8)(3–ε)/2.
Exemples
modifierExemple de Brahmagupta
modifierTraitons avec cette méthode l'exemple de Brahmagupta suivant :
Soit α = m + √83, l'entier m étant choisi tel que la norme N(α) = m2 – 83 soit la plus petite possible en valeur absolue : m = 9, α = 9 + √83, N(α) = –2. Une proposition précédente montre que α2/2 est une solution. Effectivement :
et
Défi de Fermat
modifierLe 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√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 α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
modifierPrincipe de la méthode
modifierUne 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 αj = aj + bj√n de A de la manière suivante. Le premier élément de la suite est α0 = 1, de norme k0 = 1. Supposons la suite définie à l'ordre j. On construit un élément βj = mj + √n. L'entier naturel[14] mj est tel que aj + mjbj soit multiple de la norme kj de αj — autrement dit tel que bjmj soit congru à –aj modulo kj — et mj minimise la valeur absolue de la norme mj2 – n de βj. L'élément αj + 1 est alors défini par
ou encore
le ± correspondant au signe de N(αj) — l'avantage de prendre en compte ce signe[15] est qu'ainsi, aj et bj sont toujours positifs.
On verra plus loin que la condition « aj + mjbj multiple de kj » équivaut à « mj congru à –mj–1 modulo kj », ce qui simplifie l'algorithme.
Exemples
modifierDéfi de Fermat
modifierChoisissons encore n égal à 61[16]. La valeur de m0 est égale à 8 pour minimiser |N(β0)|. En effet, √61 est compris entre 7 et 8 et 82 – 61 = 3 < 61 – 72. L'entier m1 est ensuite choisi parmi ceux congrus, modulo N(α1) = N(8 + √61) = 82 – 61 = 3, à –m0 = –8 donc à 1. Des deux termes consécutifs 7 et 10 de cette suite arithmétique qui encadrent √61, celui qui minimise |N(β1)| est m1 = 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
modifierCe deuxième exemple est aussi extrait du Siddhanta Siroman de Bhāskara II, annoté par Narayana. Pour n = 103, m0 = 10. L'entier m1 est ensuite choisi congru à –10 modulo N(α1) = N(10 + √103) = 102 – 103 = –3. Comme 8 < √103 < 11 et 112 – 103 = 18 < 103 – 82, on obtient m1 = 11 et
On choisit ensuite m2 congru à –11 modulo 6. Comme 7 < √103 < 13 et 103 – 72 = 54 < 132 – 103, on obtient m2 = 7 — remarquons à cette occasion que « minimiser |m2 – n| » ne coïncide pas toujours avec « minimiser |m – √n| » — puis
Puis, modulo 9, m3 doit être congru à –7. Pour minimiser |N(β3)|, il faut choisir m3 égal à 11. On obtient
Le calcul de Brahmagupta permet de conclure : la valeur cherchée est
Non-unicité
modifierL'exemple suivant montre que le nombre αj+1 défini à partir de αj n'est pas toujours unique : pour n = 58, α1 est égal à 8 + √58, de norme 6 puis, pour m1 congru à –2 modulo 6, le minimum de |m12 – 58| est 42, atteint pour les deux valeurs 4 et 10 de m1. Les deux valeurs correspondantes pour α2 sont 15 + 2√58, de norme –7, et 23 + 3√58, de norme 7. Cependant, pour la première on trouve ensuite m2 = 10 et pour la seconde, m2 = 4 donc pour les deux, α3 = 38 + 5√58, de norme –6, puis m3 = 8 et α4 = 99 + 13√58, de norme –1. La bifurcation n'était donc que passagère et les deux suites donnent la même solution.
Démonstrations associées à l'apport de Bhāskara II
modifierLemme
modifierUn 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 a + bm 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.
Soient a, b premiers entre eux et m, n deux entiers quelconques. On pose k = a2 – nb2, c = am + bn et d = a + bm.
Si d est multiple de k alors c aussi, et les deux entiers c/k et d/k sont premiers entre eux.
Ce lemme est immédiat en remarquant que ad – bc = k et que b est premier avec k. Appliqué — avec les notations du § « Principe de la méthode » — à a = aj et b = bj, il montre qu'à chaque étape de la construction de la suite (αj), si mj est choisi selon la méthode indiquée alors αjβj est un multiple de N(αj), αj+1 est un élément de A et aj+1 et bj+1 sont premiers entre eux, ce qui permet d'itérer la construction.
On peut remarquer de plus que la contrainte (dans le choix de mj) « aj + bjm divisible par N(αj) » est équivalente à « m congru à –mj–1 modulo N(αj) ». En effet, bj est premier avec N(αj) et aj + bj(–mj–1) est divisible par N(αj) puisque φ(αj)βj–1 = ±N(αj)φ(αj–1).
Caractère cyclique
modifierUne 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 :
- La suite (|N(αj)|) est majorée par √n[17].
- Pour tout réel C > 0, il n'existe qu'un nombre fini de classes d'équivalence de norme en valeur absolue inférieure à C.
- Si, pour deux indices i et j, αi = εαj avec ε inversible dans A, alors αi+1 = εαj+1.
Ces propriétés ne démontrent que la périodicité à partir d'un certain rang. Le paragraphe suivant montre[Information douteuse] que ce rang est 0.
Structure de la suite
modifierLe 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 un indice j > 0 tel que N(αj) = ±1 (donc N(α2j) = 1).
- La suite (cl(αk)) forme un « palindrome à conjugaison près » : cl(αj–1) = cl(φ(α1)), cl(αj–2) = cl(φ(α2)), etc.
Fraction continue
modifierLa 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 :
Approche théorique
modifierSoit n un entier naturel non carré. On définit par récurrence deux suites, (fj)j≥0 à valeurs dans ℤ et (θj)j≥–1 dans ℚ(√n) par : θ–1 = √n et pour tout j ≥ –1, fj+1 est l'entier (ou le plus petit des deux entiers) pour lequel |N(θj – fj+1)| est minimal et θj+1 = 1/(θj – fj+1). Le fait que √n soit irrationnel montre que θj est toujours irrationnel ; les suites (fj) et (θj) sont ainsi bien définies.
Cette définition diffère de la traditionnelle fraction continue car ici, les θj et les fj ne sont pas nécessairement positifs.
Soient (hj) et (kj) les suites des numérateurs et dénominateurs des réduites.
Si (αj) et (βj) désignent les suites définies précédemment, les égalités suivantes sont vérifiées (avec, par convention, m–1 = 0) :
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 βj d'être de norme systématiquement négative, alors les démonstrations de l'article restent valables et les fractions continues associées correspondent à la définition usuelle.
Méthode de calcul
modifierL'approche par les fractions continues offre un enrichissement de la méthode algorithmique précédente pour l'équation de Pell-Fermat ou la détermination de la fraction continue. Illustrons ces méthodes à l'aide de l'exemple n = 313 et montrons comment Brouncker pouvait effectivement résoudre ce défi en une heure ou deux. Par définition, m–1 = 0 et N(α0) = 1 puis, pour tout indice j ≥ 0 :
- mj est congru à –mj–1 modulo N(αj) et son carré est le plus proche possible de 313 ;
- N(βj) = mj2 – 313 ;
- N(αj+1) = N(βj)/N(αj).
On trouve ainsi m0 = 18, N(β0) = 11, N(α1) = 11, m1 = 15, N(β1) = –88, N(α2) = –8, etc.
On en déduit les fj par la formule du paragraphe précédent : f0 = m0 = 18, f1 = –(18 + 15)/11 = –3, etc.
Cette approche permet d'éviter les grands nombres, sauf pour hj–1 et kj–1, dont aj et bj sont les valeurs absolues. On les calcule pour j ≥ 1 par la formule de récurrence à partir des fj.
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(αr+1) = εN(αr) avec ε = ±1 alors, par récurrence sur k, βr+k = βr–k et N(αr+k+1) = εN(αr–k). Par conséquent, α2r+1 est alors inversible (de norme ε) et — d'après l'expression de la suite des α en fonction de celle des β — égal à εrαr+1/φ(αr) = εrαrαr+1/N(αr).
On construit ainsi le tableau suivant, où l'on constate que la situation mentionnée survient pour r = 6 et ε = –1 :
|
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 :
(Ce nombre est d'ailleurs aussi égal à α32α5/9.) Il ne reste plus qu'à l'élever au carré pour obtenir la solution recherchée :
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 hj–1 et kj–1, inutile pour cet objectif, permet de déterminer une fraction continue de √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 trouverait alors la fraction continue de cet irrationnel quadratique : [17, 1, 2, 4, 11, 1, 1, 3, 2, 2, 3, 1, 1, 11, 4, 2, 1, 34][19].
Notes et références
modifier- (en) Clas-Olof Selenius, « Rationale of the chakravāla process of Jayadeva and Bhāskara II », Historia Mathematica, vol. 2, , p. 167-184 (lire en ligne).
- (en) Victor J. Katz et Karen Parshall, Taming the Unknown, PUP, , 504 p. (ISBN 978-1-4008-5052-5, lire en ligne), p. 122-123.
- 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).
- 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].
- (en) John Stillwell, Mathematics and Its History [détail des éditions], 2010, p. 75-80.
- (en) B. L. van der Waerden, Pell's Equation in Greek and Hindu Mathematics, Russ. Math Surveys 31 (5), 1976, p. 210-225
- (en) John J. O'Connor et Edmund F. Robertson, « Pell's equation », sur MacTutor, université de St Andrews.
- Voir la page Pierre Fermat sur le site de la commune de Beaumont-de-Lomagne.
- Œuvres de Fermat, p. 334.
- Ces informations sont tirées des échanges épistolaires entre les différents acteurs, publiés dans (la) John Wallis, Commercium epistolicum de quæstionibus quibusdam mathematicis nuper habitum Oxonii : Excudebat A. Lichfield, Impensis Tho. Robinson, 1658
- Joseph-Alfred Serret, Œuvres de Lagrange, vol. I, p. 671-731 : « Solution d'un problème d'arithmétique ».
- (en) A. A. Krishnaswami Ayyangar, « New light on Bhaskara's Chakravala or cyclic method of solving indeterminate equations of the second degree in two variables », J. Indian Math. Soc., vol. 18, 1929-30, p. 225-248 (lire en ligne).
- Ce cas, appliqué à α = (10 + √92)2/4 = 48 + 5√92, de norme 82/42 = 4, permet à Brahmagupta de résoudre son premier exemple : Stillwell, p. 77.
- (en) Harold Edwards, Fermat's Last Theorem : A Genetic Introduction to Algebraic Number Theory, Springer, coll. « GTM » (no 50), , 3e éd., 407 p. (ISBN 978-0-387-95002-0, lire en ligne), chap. I, § 9 (« Pell's equation »), p. 25-36.
- Selenius 1975 ajoute cette valeur absolue au dénominateur, tout en précisant à deux reprises que Bhāskara ne le faisait pas. Edwards 2000 intègre cette valeur absolue dans sa formulation, sans même cette précision.
- (en) Stillwell, p. 79.
- La méthode chakravala est, en cela aussi, supérieure à celles d'Euler et de Brouncker : en plus d'atteindre le résultat en moins d'étapes, elle met en jeu des calculs sur des nombres plus petits (Selenius 1975).
- Edwards 2000, p. 35.
- Suite A040295 de l'OEIS.
Voir aussi
modifierLien externe
modifier(en) John J. O'Connor et Edmund F. Robertson, « Indian Mathematics: Redressing the balance, 8 VI. Pell's equation », sur MacTutor, université de St Andrews.
Bibliographie
modifier- (en) Leonard Eugene Dickson, History of the Theory of Numbers (en) [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)