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 Bhaskara 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.
Bhaskara 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 :
Choisissons encore d égal 61. La valeur de a 1 est égale à 8 pour minimiser la norme de α1, en effet :
Pour déterminer la valeur de α2 il est nécessaire de calculer m 1. On dispose de l'égalité suivante :
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 :
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.
Ce deuxième exemple est aussi extrait du Siddhanta Siroman de Bhaskara II, annoté par Narayana. Si d est égal à 103, la valeur de a 1 est égale à 10 et :
Le calcul de α2 donne :
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 :
Le calcul de α3 donne :
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 :
Le calcul de α4 donne :
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 :
Le calcul de Brahmagupta permet de conclure, la valeur α cherchée est égal à 1/2.α42 :
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 :
Étudions le cas où n est égal à 19.
A l'ordre 0, l'objectif est de trouver la valeur f0 la plus proche possible de √19. On obtient l'égalité :
Ici, ωk désigne le reste de la fraction continue, souvent appelé quotient complet d'indice k.
A l'ordre 1, on cherche une approximation √19 de la forme f0 + 1/f1 la meilleure possible, on obtient :
A l'ordre 2 :
A l'ordre 3 :
A l'ordre 4 :
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 :
Déterminons les fractions partielles à l'ordre k θk, habituellement appelées réduite d'indice k.
Le calcul de la suite (αk) de la méthode chakrala donne :
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 :
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 :
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é :
La valeur 1 / fk+1 est la meilleure approximation de θk et θk+1 est l'élément de A vérifiant l'égalité :
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.
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.
Un lemme est utile pour établir la proposition de ce paragraphe :
En d'autres termes, l'équivalence suivante est vérifiée :
En effet, a k et b k sont premiers entre eux, cette propriétés est démontrée dans le paragraphe sur les lemmes. L'égalité suivante montre que b k et la norme de αk sont aussi premiers entre eux :
L'élément b k est en conséquence inversible dans l'anneau Z / N(αk)Z. Soit g k son inverse. La condition de congruence est équivalente à la suivante :
La proposition à démontrer est équivalente à l'une des deux formes suivantes :
On reconnaît là la deuxième coordonnée de l'élément αk φ(βk-1), en effet :
Il suffit donc de démontrer que αk φ(βk-1) est un multiple de la norme de αk pour établir le lemme, ou encore, comme la norme de αk est égale au produit αk. φ(αk), il suffit de montrer que φ(βk-1) est un multiple de φ(αk). Une manière plus simple prouver le lemme est de montrer que βk-1 est un multiple de αk. Les égalités suivantes, issues de la définition de αk permettent de conclure :
Montrons ce résultat par récurrence, sur k.
Si k est égal à zéro :
Supposons le résultat établi à l'ordre k - 1, montrons qu'il est vrai à l'ordre k.
Une égalité établie dans le lemme montre que βk-1 est égal au produit de +/-1, αk et de φ(αk-1), on en déduit :
Le lemme montre que mk est choisi de telle manière à ce que (-1)k(mk + mk+1)/ N(αk) soit un entier et (-1)k+1.βk-1 / N(αk) de valeur absolue la plus petite possible.
Pour simplifier les calculs, modifions légèrement la définition de αk. Dans cette démonstration, αk+1 est défini comme le produit : 1/N(αk).αk.βk. Ainsi, si la norme de αk est négative, alors les deux coordonnées de αk+1 sont négatives. On remarque immédiatement que la modification des signes des coordonnées de la suite (αk) ne modifie ni la suite (βk) ni les valeurs absolues des coordonnées de la suite (αk). L'objectif est maintenant de démontrer, avec ces nouvelles conventions que αk = (-1)k(ck + dk√n). On dispose des égalités suivantes :
En remplaçant αk-1 par une valeur équivalente et βk + φ(βk+1) par ses coordonnées, on obtient :
On reconnait le terme f k de la fraction continue calculée pour la démonstration précédente. Si α'k est défini comme égal à -(1)kαk :
Notons αk = ck+1 + dk+1√n et α0 = 1. Les suites (α'k) et (αk) sont égales pour k égale à 0 ou à 1 et elles vérifient toutes les deux la relation de récurrence
Les deux suites (α'k) et (αk) sont donc toujours égales. La suite (αk) est égale à la suite (α'k) au signe près. Or elles ont toutes les deux des coefficients toujours strictement positifs, la suite (αk) est donc égale à la suite (αk), ce qui démontre la proposition.
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 :
|
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.α7.α8 est un élément de norme -1 :
Il faut encore mettre ce nombre α13 au carré pour obtenir la solution recherchée :
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 :