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 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 \mathbb N - \{0, 1\}$

Cette méthode fut développée en Inde et ses racines peuvent être retracées jusqu'au V^e siècle. Initié par Aryabhata, elle est développée plus avant par Brahmagupta et Bhaskara 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 Bhaskara, n'égala la complexité merveilleuse et ingénieuse de chakravala. »^[1]

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

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 (x₀, y₀) 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. Aryabhata, un mathématicien du VI^e 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 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 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 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 XII^e 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^[8] pour trouver une solution minimale à l'équation suivante déjà trouvée par Brahmagupta :

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

Le couple de solution trouvée 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 XII^e 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.^[9] De nouveaux exemples sont traités plus tard, par les mathématiciens indiens. Au XIV^e 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 (1601 - 1665) lance le 3 janvier 1658 un défi aux mathématiciens européens^[10]. 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^[11], 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.^[12]

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^[13].

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 irrationnels de la forme a + √n.b, où a et b désignent deux nombres entiers. Soient N l'application qui au nombre a + √n.b associe a² - n.b² 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 α = a₁ + √n.a₂ et β = b₁ + √n.b₂ 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 \mathbb 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 x^k = 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, α ² est solution de (1).

Il suffit de remarquer que la norme de α ² 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.α² est un élément de A solution de (1).

En effet, si α est égal à a + b.√n alors un calcul montre que α² = a² + n.b² + 2ab.√n. Comme a² + n.b² = N(α) + 2.n.b² et que N(α) et 2ab sont des multiples de 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.α³ est un élément de A de norme égale à +/- 1.

En effet, calculons α³ :

$\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 ² - n.b ² = +/- 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 $ε$ est impair, il suffit de montrer que b est impair pour prouver que α³ est un multiple de 8. Si b est pair, n.b ² est un multiple de quatre et comme N(α) = a ² - n.b ² 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 ε + nb² ainsi que 3ε + nb² sont pairs si n est impair. Ceci montre que α³ 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 ² 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.α³ 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 α² :

$\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.α² :

$\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.α³ 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.α⁶, 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 Bhaskara 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 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 α₁ de la suite est de la forme a₁ + √n. Il est choisi de telle manière à ce que la norme de α₁, égale à a₁² - n, soit la plus petite possible en valeur absolue.

Supposons la suite définie à l'ordre j. On note α_j = a_j + b_j.√n. On construit un élément β_j = m_j + √n. Le nombre entier m_j est tel que a_j + m_j.b_j soit dans un multiple de la norme de α_j et m_j 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 ₁ est égale à 8 pour minimiser la norme de α₁, en effet :

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

Pour déterminer la valeur de α₂ il est nécessaire de calculer m ₁. 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 α₂ est un élément de A, 8 + m ₁ est un multiple de 3, ou encore m ₁ est de la forme 3.k + 1. Pour minimiser la norme de β₁, il faut choisir k égal à 2. On en déduit que m ₁ 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 Bhaskara II, annoté par Narayana. Si d est égal à 103, la valeur de a ₁ est égale à 10 et :

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

Le calcul de α₂ 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 ₁ est de la forme 3.k - 1. Pour minimiser la norme de β₁, il faut choisir m ₁ é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 α₃ 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 ₂ est de la forme 6.k - 5. Pour minimiser la norme de β₂, il faut choisir m ₂ égal à 7. On obtient :

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

Le calcul de α₄ 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 ₃ est de la forme 9.k + 2. Pour minimiser la norme de β₃, il faut choisir m ₃ é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.α₄² :

$\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 Bhaskara II

Lemmes

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

$\forall j \in \mathbb 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 m_j de telle manière à ce 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 α_j.β_j est bien un multiple de k_j. Cette propriété est l'objet des deux lemmes suivants :

Avec les notations précédentes, si a_j + b_j.m_j est choisi multiple de k_j et si a_j , b_j sont premiers entre eux alors , α_j.β_j est un multiple de k_j.

Sous réserve des hypothèses du lemme précédent et si la norme de β_j est choisie minimale en valeur absolue, a_j+1, b_j+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, α_j.β_j 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.

Démonstrations des lemmes

La valeur α_j.β_j est un élément de A multiple de k _j :

Utilisons les notations suivantes :

$\alpha_i\cdot \beta_j = a'_{j+1} + b'_{j+1}\cdot \sqrt n \;$

Les éléments a' _j+1 et b' _j+1 sont des éléments de Z. À ce titre ils peuvent être vu comme des éléments de l'anneau A. Dire que b' _j+1 est divisible par k _j revient à dire que b' _j+1 est divisible par α_j.φ(α_j), en effet :

$k_j = |\mathcal N(\alpha_j)| = |\alpha_j\cdot \varphi (\alpha_j)| \quad\text{donc}\quad \alpha_i\cdot \beta_j = a'_{j+1} + b_{j+1}\cdot \alpha_j\cdot \varphi (\alpha_j)\cdot \sqrt n \;$

On en déduit l'existence d'un nombre δ_j de A tel que : α_j.δ_j = a' _j+1. Si e _j et f _j sont deux éléments de Z tel que :

$\delta_j = e_j + f_j \sqrt n\quad \text{alors}\quad \alpha_j \delta_j \in \mathbb Z \Rightarrow a_jf_j + b_je_j = 0\quad \text{car}\quad \alpha_j \delta_j = a_j e_j + n b_jf_j + (a_jf_j + b_je_j)\sqrt n\;$

La dernière égalité exprime le fait que les couples (e _j, f _j) et (a _j, -b _j) sont proportionnels. Comme a _j et b _j sont premiers entre eux, il existe un entier a _j+1 tel que :

$(e_j, f_j) = a_{j+1}(a_j, -b_j)\quad \text{et}\quad \delta_j = a_j + f_j\sqrt n = a_{j+1}(a_j - b_j \sqrt n) = a_{j+1}\cdot \varphi (\alpha_j)\;$

En remplaçant δ_j par sa valeur dans l'expression α_j.δ_j on obtient :

$\alpha_i\cdot \beta_j =\alpha_j\cdot \varphi (\alpha_j)\cdot a_{j+1} + b_{j+1}\cdot \alpha_j\cdot \varphi (\alpha_j)\cdot \sqrt n = k_j(a_{j+1} + b_{j+1}\cdot\sqrt n)\;$

Les valeurs a _j+1, b _j+1 sont premières entre elles si la valeur absolue de la norme de β_j est choisie minimale :

L'égalité suivante est vérifiée :

$\alpha_j\beta_j = \alpha_j\varphi(\alpha_j)(a_{j+1} + b_{j+1}\sqrt n) \quad\text{donc}\quad \beta_j = \varphi(\alpha_j)(a_{j+1} + b_{j+1}\sqrt n) \;$

Un entier diviseur commun de a _j+1 et b _j+1 divise β _j ainsi que sa norme. Comme la norme de β _j est choisi minimale en valeur absolue, il n'existe aucun diviseur commun à a _j+1 et b _j+1 autre que 1 et -1.

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 si 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 (cl(α_j)) est cyclique.

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

La suite (α_j) 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. Il est alors possible de parler de la norme 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 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 (cl(α_j) 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.

Démonstrations

La suite (α_j) est définie de manière univoque et la suite (N(α_j)) est bornée :

Notons r la partie entière de la racine carrée de n. Montrons par récurrence α_j est inférieur ou égal à 2.r et que la suite est définie de manière univoque.

Si j est égal à un, On dispose des majorations suivantes :

$r^2 < n < (r + 1)^2 = r^2 + 2r + 1\;$

La distance entre les deux carrés parfaits les plus proches encadrant n est égale à 2.r+1, ce qui montre que le carré le plus proche est à une distance inférieure ou égale à r car chaque terme de la majoration est entier. Le fait que le carré le plus proche soit à une distance inférieure ou égal à r et donc à 2.r montre que la norme de α₁ est inférieure à 2.r.

Comme n est entier, il ne peut être exactement au milieu de r ² et (r + 1)². Il n'existe donc qu'une unique valeur possible pour m ₀ et a fortiori pour α₁.

Supposons la propriété démontrée à l'ordre j et montrons là à l'ordre j + 1. Soit m' _j le plus grand entier inférieur ou égal à r et de la forme a_j + m' _j.b_j soit un multiple de k_j. On dispose des majorations suivantes :

$m_j^{\prime 2} < n < (m^{\prime} + k_j)^2 = m_j^{\prime 2} + 2m_j^{\prime}k_j + k_j^2\;$

Une fois encore n ne peut se situer exactement au milieu des deux bornes de la majoration, sinon √n serait une fraction, ce qui est contraire à l'hypothèse indiquant que n est sans facteur carré. On en déduit que m_j est défini de manière univoque et que n est à une distance de m _j² inférieure ou égale à m' _j.k_j + 1/2.k_j². Cette majoration et le fait que m _j soit inférieur ou égal à r, montrent que la norme de β_j est inférieure ou égal à r.k_j + 1/2.k_j². Le paragraphe précédent et l'hypothèse de récurrence établissent que :

$\mathcal N(\alpha_{j+1}) = \frac {\mathcal N(\beta_j)}{\mathcal N(\alpha_j)}\le \frac {rk_j + 1/2\cdot k_j^2}{k_j} = r+\frac 12 k_j \le 2r \;$

Ce qui montre que la suite est majorée et qu'une valeur du majorant est donnée par 2.r si r désigne la partie entière de la racine carrée de n.

Montrons que la suite les classes des α_k est périodique. On remarque que deux éléments d'une même classe possèdent la même norme car la norme d'une unité est égale à 1 en valeur absolue, ce qui permet de donner un sens à la proposition suivante :

Soit C une constante strictement positive. Il n'existe qu'un nombre fini de classes d'équivalences d'éléments de A de norme inférieure à C :

Ce résultat est la conséquence d'un lemme, indiquant qu'il n'existe qu'un nombre fini d'idéaux principaux généré par un élément de norme en valeur absolue inférieure à une constante donnée. Un idéal principal engendré par un élément α de A est l'ensemble des multiples de α dans A. Pour cela, il suffit d'établir la proposition suivante : Soit J un idéal principal engendré par un élément α de norme C un entier strictement positif et B le quotient de A par J.

(1) L'anneau unitaire quotient B est de cardinal fini :

Cette proposition est démontrée dans le paragraphe Idéal premier, idéal maximal de l'article Idéal de l'anneau des entiers d'un corps quadratique.

(3) Il n'existe qu'un nombre fini de classes d'équivalences de norme inférieure à C :

Un idéal ne contient qu'une unique classe d'équivalence de générateurs. En effet, soit α et β deux générateurs d'un tel idéal. L'élément β est généré par α et réciproquement, ce qui montre l'existence d'éléments γ et δ tel que :

$\beta = \gamma\cdot \alpha \text { et } \alpha = \delta \cdot \beta \quad \text{donc}\quad \alpha =\delta \cdot \beta = \delta \cdot \gamma \cdot \alpha \quad \text{ou encore}\quad \delta \cdot \gamma = 1\;$

Le caractère fini du nombre d'idéaux et le fait qu'un idéal ne contient qu'une classe d'équivalence permet de conclure la démonstration.

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

Si α_i = ε.α_j alors les normes de α_i et α_j sont égales en valeur absolue car la norme est multiplicative et celle de ε est égale à +/- 1. Le lemme montre que :

$|\mathcal N(\alpha_i)|\alpha_{i+1} = \alpha_i\cdot \beta_i\quad\text{donc}\quad |\mathcal N(\alpha_j)|\alpha_{i+1}= \epsilon^{-1}\cdot \alpha_j\cdot \beta_i\;$

Ce qui montre que β_i est un multiple de la norme de α_j et comme la norme de β_i est choisi minimale, on a bien β_i = β_j et ceci termine la démonstration.

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

Démonstrations

Soit ψ la fonction de A - {0} dans A - {0} qui à α_k associe α_k+1. Plus précisément à un élément α de A on associe un élément β de forme m + √n avec m entier naturel tel que β.α soit un multiple de la norme de α, de norme minimale et tel que l'égalité N(α).ψ(α) = α.β. Les lemmes et le paragraphe précédent montre que l'application ψ est bien définie et que, si α₀ est choisi égal à 1 :

$\forall k \in \mathbb N,\quad \psi(\alpha_k) = \alpha_{k+1}$

Cette fonction possède une symétrie par rapport à la fonction φ, si G désigne le groupe des unités de A :

La propriété suivante est vérifiée :

$\forall \alpha, \gamma \in \mathbb A - \{0\}, \quad \psi (\alpha) = \gamma \Rightarrow \exists \epsilon \in G,\;\psi\circ \varphi(\gamma) = \epsilon \varphi(\alpha) \;$

Autrement dit, si α possède pour image par ψ la valeur γ, alors γ possède pour image par ψ la valeur α, à un facteur inversible près.

En effet, si α possède pour image par ψ la valeur γ, il existe un unique élément β de la forme m + √n avec m entier naturel tel que, si ε₁ (resp. ε₂) est le signe de la norme de α (resp. γ) :

$\gamma = \frac {\alpha\beta}{|\mathcal N (\alpha)|} = \epsilon_1\frac {\alpha\beta}{\alpha\varphi(\alpha)}=\epsilon_1 \frac {\beta}{\varphi(\alpha)} \quad \text{et}\quad (1) \quad \varphi(\alpha) = \epsilon_1 \frac {\beta}{\gamma} =\epsilon_1\epsilon_2 \frac {\varphi(\gamma)\beta}{|\mathcal N (\varphi(\gamma))|} \;$

L'élément β est bien de la forme m + √n avec m entier naturel tel que β.γ est un multiple de la norme de γ, car φ(α) est entier. Soit β'un élément vérifiant ces propriétés et de norme inférieure à β, l'égalité γ = α.β'/N(β') montre que β' est de norme supérieure à β. On en déduit que les normes de β et β' sont égales et son caractère minimal est vérifié. L'égalité (1) montre que φ(α), à un élément inversible près est bien l'image de φ(γ) par ψ. La proposition est démontrée.

On en déduit que la fonction ψ est une bijection de A - {0} dans A - {0}.

Il existe une valeur j telle que la norme de α_j soit égale à un en valeur absolue :

Remarquons dans un premier temps que l'on peut définir α₀ comme égal à 1, car ψ(1) = α₁. Soit j la plus grande valeur tel que la suite d'éléments α₀, α₁, ... , α_j-1 ne contienne que des éléments de classes distincts par la relation d'équivalence R. Une telle définition possède un sens car les classes d'équivalences de norme inférieures à 2r sont en nombre fini, la suite des classes d'équivalence se répète donc nécessairement à partir d'un certain rang. La valeur α_j est dans la liste α₀, α₁, ... , α_j-1 à un facteur multiplicatif inversible près. Elle ne peut pas être égale à un élément pris dans α₁, ... , α_j-1 car un tel élément aurait deux antécédents ce que la dernière proposition à montré impossible. On en déduit que la classe de α_j est égal à celle de α₀. Il suffit de remarquer que la suite des valeurs (a_k) et (b_k) est strictement croissante pour conclure que la solution trouvée n'est pas triviale.

La suite (α_j) forme un palindrome :

L'égalité ψ(1) = α₁ montre que ψoφ(α₁) est dans classe de φ(1) = 1. On en déduit que cl(α_j-1) = cl(φ(α₁)). L'égalité ψ(α₁) = α₂ montre que l' antécédent de la classe de φ (α₂) est la classe de φ(α₁) ce qui montre que cl(α_j-2) = cl(φ(α₂)). Une récurrence fondée sur ce principe permet d'établir la proposition.

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 + \cfrac{1}{f_1 + \cfrac{1}{f_2 + \frac{1}{f_3+\,\cdots}}}\quad \text{avec}\quad f_i \in \mathbb Z \;$

Introduction par l'exemple

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

A l'ordre 0, l'objectif est de trouver la valeur f₀ 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.

A l'ordre 1, on cherche une approximation √19 de la forme f₀ + 1/f₁ 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)$

A 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)$

A l'ordre 3 :

$\frac 12(5 - \sqrt 19) = \frac {6}{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)$

A l'ordre 4 :

$\frac 13(-4 + \sqrt 19) = \frac {3}{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 ω₄ soit égal à ω₀ montre que la suite (f_k) est périodique, ces termes sont : f₀, f₁, f₂, f₃, f₄, f₁, f₂, f₃, f₄, f₁, ... . 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 (f_k) 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 (f_k) 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 f₀ est égale à la partie entière de √n, où n est un entier strictement supérieur à 1 et sans facteur carré, et θ₀ l'élément de A défini par l'égalité :

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

La valeur 1 / f_k+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 f_k n'est pas nécessairement choisi positif. On remarque de f_k+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 (f_k) 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, si (α_k) et (β_k) 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 \mathbb 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 (f_k) et (θ_k) sont à valeurs strictement positives.

Démonstration

Un lemme est utile pour établir la proposition de ce paragraphe :

La condition de congruence sur β_k est équivalente au fait que pour tout k strictement positif m_k-1 + m_k soit un multiple de la norme de α_k.

En d'autres termes, l'équivalence suivante est vérifiée :

$\forall k \in \mathbb N - \{0\} \quad a_k + b_km_k \equiv 0 \mod |\mathcal N(\alpha_k)| \Leftrightarrow m_{k-1} + m_k \equiv 0 \mod |\mathcal N(\alpha_k)|$

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 :

$\forall k \in \mathbb N\quad a_k^2 - n\cdot b_k^2 = \mathcal N (\alpha_k)$

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 :

$a_kg_k + m_k \equiv 0 \mod |\mathcal N(\alpha_k)|$

La proposition à démontrer est équivalente à l'une des deux formes suivantes :

$a_kg_k \equiv m_{k-1} \mod |\mathcal N(\alpha_k)| \quad \text{ou}\quad a_k - b_km_{k-1} \equiv 0 \mod |\mathcal N(\alpha_k)|$

On reconnaît là la deuxième coordonnée de l'élément α_k φ(β_k-1), en effet :

$\alpha_k\varphi(\beta_{k-1}) = (a_k + b_k\sqrt n)(m_{k-1} - \sqrt n) = a_k m_{k-1} - nb_k + (b_km_{k-1} - a_k)\sqrt n \;$

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 :

$\alpha_k = \frac {\alpha_{k-1}\beta_{k-1}}{|\mathcal N(\alpha_{k-1})|} = \epsilon\frac {\alpha_{k-1}\beta_{k-1}}{\alpha_{k-1}\varphi (\alpha_{k-1})} = \epsilon \frac {\beta_{k-1}}{\varphi(\alpha_{k-1})} \quad \text{et}\quad \beta_{k-1} = \epsilon \alpha_k\varphi(\alpha_{k-1})\quad \text{avec}\quad \epsilon \in \{-1,1\}$

Pour tout nombre entier k, θ_k = (-1)^k+1 φ(β_k) / N(α_k) :

Montrons ce résultat par récurrence, sur k.

Si k est égal à zéro :

$\sqrt n = f_0 + \theta_0 = m_0 - m_0 + \sqrt n = m_0 - \frac {\beta_0}{1} = m_0 - \frac {\varphi(\beta_0)}{\mathcal N (\alpha_0)}\quad \text{et}\quad \theta_0 = - \frac {\varphi(\beta_0)}{\mathcal N (\alpha_0)} \;$

Supposons le résultat établi à l'ordre k - 1, montrons qu'il est vrai à l'ordre k.

$\theta_{k-1} = (-1)^k \frac {\varphi(\beta_{k-1})}{\mathcal N (\alpha_{k-1})}\quad\text{donc}\quad \frac 1\theta_{k-1} = (-1)^k \frac {\mathcal N (\alpha_{k-1})}{\varphi(\beta_{k-1})}= (-1)^k \frac {\mathcal N (\alpha_{k-1})\cdot \beta_{k-1}}{\varphi(\beta_{k-1})\cdot \beta_{k-1}} = (-1)^k \frac {\mathcal N (\alpha_{k-1})\cdot(m_{k-1} + \sqrt n)}{\mathcal N (\beta_{k-1})}\;$

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 :

$\frac 1{\theta_{k-1}}= (-1)^k \frac {\mathcal N (\alpha_{k-1})\cdot(m_{k-1} + \sqrt n)}{\mathcal N (\alpha_{k-1})\mathcal N (\alpha_k)} = (-1)^k \frac {m_k + m_{k-1}}{\mathcal N (\alpha_k)} + (-1)^{k+1} \frac {m_k - \sqrt n}{\mathcal N (\alpha_k)}= (-1)^k \frac {m_k + m_{k-1}}{\mathcal N (\alpha_k)} + (-1)^{k+1}\frac {\varphi(\beta_k)}{\mathcal N (\alpha_k)} \;$

Le lemme montre que m_k est choisi de telle manière à ce que (-1)^k(m_k + m_k+1)/ N(α_k) soit un entier et (-1)^k+1.β_k-1 / N(α_k) de valeur absolue la plus petite possible.

Pour tout nombre entier k, α_k+1 est égal à c_k + d_k√n :

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(c_k + d_k√n). On dispose des égalités suivantes :

$\alpha_{k+1} = \frac {\beta_k}{\varphi(\alpha_k)},\; \alpha_k = \frac {\beta_{k-1}}{\varphi(\alpha_{k-1})} \quad\text{donc}\; \varphi(\beta_{k-1})\alpha_{k+1} = \beta_k\alpha_{k-1}\quad \text{et}\; \varphi(\beta_{k-1})( \alpha_{k+1} + \alpha_{k-1}) = (\beta_k + \varphi(\beta_{k-1}))\alpha_{k-1}$

En remplaçant α_k-1 par une valeur équivalente et β_k + φ(β_k+1) par ses coordonnées, on obtient :

$\varphi(\beta_{k-1})( \alpha_{k+1} + \alpha_{k-1}) =(m_k + m_{k-1})\frac {\varphi (\beta_{k-1})}{\varphi(\alpha_k)} \quad\text{et}\quad \alpha_{k+1} + \alpha_{k-1} = \frac {m_k + m_{k-1}}{\mathcal N(\alpha_k)}\alpha_k$

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 :

$(-1)^k\frac {m_k + m_{k-1}}{\mathcal N(\alpha_k)} = f_k \quad \text{donc}\quad \alpha'_{k+1} = f_k \cdot\alpha'_k + \alpha'_{k-1}\;$

Notons α_k = c_k+1 + d_k+1√n et α₀ = 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

$\forall k \in \mathbb N -\{0,1\} \quad u_{k+1} = f_k\cdot u_k + u_{k-1}\;$

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.

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

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

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

Indice	m_k	N(β_k) = m_k² - 313	N(α_k) = N(β_k-1)/N(α_k-1)	f_k = (-1)^k(m_k + m_k-1)/N(α_k)	a_k = f_k-1.a_k-1 + a_k-2	b_k = f_k-1.b_k-1 + b_k-2
0	18	11	1	m₀ = 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 α₇ est l'opposée de cette de α₈, 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.α₇.α₈ 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 α₁₃ 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

↑ C.O. Selenius Rationale of the chakravala process of Jayadeva and Bhaskara II Historia Mathematica 2 1975 pp 167-184
↑ H. M. Edwards Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory Springer 3^ème Ed 2000 (ISBN 0387950028)
↑ G Ifrah Histoire universelle des chiffres: L'intelligence des hommes racontée par les nombres et le calcul Robert Laffont 1994 (ISBN 2221901002)
↑ Une analyse précise de son œuvre mathématique est disponible dans la thèse : Analyse du contenu mathématique de l'Âryabhatîya
↑ J. Stillwell Mathematics and its History Springer Science 2^ième éd 2004 p 72-74 (ISBN 0387953361)
↑ B. L. van der Waerden Pell's Equation in Greek and Hindu Mathematics Russ. Math Surveys 1976 31 (5) pp 210-225
↑ Cet exemple est tiré de son livre Brahmasphuta siddhanta d'après le site de l'Université de St Andrew Pell's equation
↑ Bhāskara II Bijaganita 1150 cf le site de l'Université de St Andrew Pell's equation
↑ Cette analyse est extraite du site de l'Université de St Andrew Pell's equation
↑ L. Hua J. Rousseau Fermat a-t-il démontré son grand théorème? l'hypothèse "Pascal" L'Harmattan 2002 p 113 (ISBN 2747528367)
↑ 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 par la ville Beaumont de Lomagne
↑ Ces informations proviennent de la compilation des échanges épistolaires entre les différents acteur. Ils sont publiés sous la référence : John Wallis Commercium epistolicum de quæstionibus quibusdam mathematicis nuper habitum Oxonii : Excudebat A. Lichfield, Impensis Tho. Robinson 1658
↑ Le texte des travaux de Lagrange est disponible : Solution d'un problème d'arithmétique

Liens externes

(en) Analyse du contenu mathématique de l'Âryabhatîya
(en) Pell's equation par le site de L'Université de St Andrew
(en) Introduction to chakravala par le site de L'Université de St Andrew
(fr) Joseph-Louis Lagrange Solution d'un Probleme d'Arithmetique : La solution originale par les fractions continuées.

Références

(en) L E Dickson History of the theory of numbers vol. II, Diophantine analysis 1920 réimpression Dover Publications 2005 (ISBN 0486442330)
(en) J. Stillwell Mathematics and its History Springer Science 2^ième éd 2004 p 72-74 (ISBN 0387953361)
(fr) J. Trignan Fractions continues & Différences finies Éditions du Choix 1994 (ISBN 2-909028-16-X)

Portail des mathématiques

Ce document provient de « M%C3%A9thode chakravala ».

Catégories : Équation diophantienne | Algorithme | Arithmétique modulaire | Entier quadratique

Wikimedia Foundation. 2010.

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

Игры ⚽ Нужна курсовая?

Regardez d'autres dictionnaires:

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
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 à… … 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

Dictionnaires et Encyclopédies sur 'Academic'

Methode chakravala

Méthode chakravala

Sommaire

Objectif

Histoire

Mathématiques indiennes

Europe

Apports de Brahmagupta

Décors

Samasa

Conséquences

Exemples

Exemple de Brahmagupta

Défi de Fermat

Apport de Bhaskara II

Principe de la méthode

Exemples

Défi de Fermat

Exemple de Narayana

Démonstrations associées à l'apport de Bhaskara II

Lemmes

Caractère cyclique

Structure de la suite

Fraction continue

Introduction par l'exemple

Approche théorique

Méthode de calcul

Références

Notes

Liens externes

Références

Regardez d'autres dictionnaires:

Share the article and excerpts

Dictionnaires et Encyclopédies sur 'Academic'

Wikipédia en Français

Methode chakravala

Méthode chakravala

Sommaire

Objectif

Histoire

Mathématiques indiennes

Europe

Apports de Brahmagupta

Décors

Samasa

Conséquences

Exemples

Exemple de Brahmagupta

Défi de Fermat

Apport de Bhaskara II

Principe de la méthode

Exemples

Défi de Fermat

Exemple de Narayana

Démonstrations associées à l'apport de Bhaskara II

Lemmes

Caractère cyclique

Structure de la suite

Fraction continue

Introduction par l'exemple

Approche théorique

Méthode de calcul

Références

Notes

Liens externes

Références

Regardez d'autres dictionnaires:

Share the article and excerpts

Direct link