Fraction continue d'un nombre quadratique

Un article de Wikipédia, l'encyclopédie libre.

$Joseph-Louis Lagrange établit de manière rigoureuse les propriétés des fractions continues des nombres quadratiques.$

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 représentation de ce nombre sous la forme suivante :

$a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \frac{1}{a_3+\,\cdots}}},\quad \forall i \in \mathbb N \quad a_i \in \mathbb N$

Si le nombre représenté est quadratique, c'est à dire s'il n'est pas rationnel mais solution d'une équation du second degré à coefficients rationnels, alors la suite d'entiers (a_n) est périodique à partir d'un certain rang.

L'intérêt de l'étude de la fraction continue d'un nombre quadratique ne se résume pas à cette anecdote. La simplicité de l'algorithme permettant de déterminer les coefficients de la fraction en ont fait pendant longtemps une méthode d'extraction de racine. La connaissance de la fraction continue permet aussi de résoudre une célèbre équation diophantienne, c'est à dire une équation dont les coefficients et les solutions recherchées sont des nombres entiers. Cette équation porte le nom de Pell-Fermat et prend la forme suivante, si n est un entier sans facteur carré.

$x^2 - n\cdot y^2 = \pm 1\;$

Sommaire

1 Préambule
- 1.1 Introduction par l'exemple
- 1.2 Eléments d'histoire
2 Première propriété
3 Période
4 Palindrome
5 Equation de Pell-Fermat
- 5.1 Structure de la solution
- 5.2 Groupe des unités
6 Extraction d'une racine carrée
- 6.1 Première méthode
- 6.2 Accélération violente
7 Un exemple historique de résolution de l'équation de Pell Fermat
8 Voir aussi

[modifier] Préambule

[modifier] Introduction par l'exemple

Le calcul de la fraction continue d'un nombre quadratique est relativement aisée, l'identité remarquable (a + b)(a - b) = a² - b² est utilisée à chaque étape. L'exemple suivant en est une illustration :

$\sqrt {13} = 3 + (-3 + \sqrt {13}) = 3 + \frac {(\sqrt 13-3)(\sqrt 13+ 3)}{\sqrt 13 + 3} = 3 + \frac 4{3 + \sqrt 13} = 3 + \frac 1{\frac{\sqrt 13 + 3}4} \quad\text{et}\quad a_0 = 3,\; x_1 = \frac{\sqrt 13 + 3}4$

Il est possible d'appliquer à nouveau le même algorithme sur x₁ :

$\frac{\sqrt 13 + 3}4 = 1 + \frac{\sqrt 13 - 1}4 = 1 + \frac 1{\frac{\sqrt 13 + 1}3}\quad\text{donc}\quad \sqrt {13} = 3 + \cfrac 1{1 + \cfrac 1{\frac{\sqrt 13 + 1}3}}\quad\text{et}\quad a_1 = 1,\; x_2 = \frac{\sqrt 13 + 1}3$

Puis sur x₂ :

$\frac{\sqrt 13 + 1}3 = 1 + \frac 1{\frac {\sqrt 13 + 2}3} \quad\text{donc}\quad 3 + \cfrac 1{1 + \cfrac 1{1 + \frac 1{\frac {\sqrt 13 + 2}3}}} \quad\text{et}\quad a_2 = 1,\; x_3 = \frac{\sqrt 13 + 2}3$

Avec, ensuite :

$\frac{\sqrt 13 + 2}3 = 1 + \frac 1{1 + \frac 1{6 + \frac 1{\frac {\sqrt 13 + 3}4}}} \quad\text{et}\quad a_3 = 1,\; a_4 = 1,\; a_5 = 6,\; x_5 = \frac{\sqrt 13 + 3}4$

Le vocabulaire et les notations utilisés ici sont ceux définis dans l'article Fraction continue. Le coefficient d'indice n de la fraction continue correspond au coefficient a_n utilisé dans l'introduction. La réduite d'indice n désigne la fraction continue tronquée contenant n barres de fraction et construite à l'aide de n + 1 coefficients, elle est notée h_n / kn. Le quotient complet est la valeur, noté x_n tel que si l'on remplace a_n-1 par a_n-1 + 1/ x_n dans l'expression de la réduite d'indice n - 1, on obtient exactement le nombre initial. Le quotient complet x₀ est la valeur initiale, √13 dans l'exemple choisi.

Le coefficient a_n correspond à la partie entière du quotient complet x_n et le quotient complet x_n+1 à l'inverse de la partie fractionnaire de x_n. Pour résumer, on obtient :

$\sqrt 13 = 3 + \cfrac 1{1 + \cfrac 1{1 + \cfrac 1{1 + \frac 1{1 + \frac 1{6 + \cdots}}}}}\quad{et}\quad \frac{h_0}{k_0} = \frac 31,\; \frac{h_1}{k_1} = \frac 41,\; \frac{h_2}{k_2} = \frac 72,\; \frac{h_3}{k_3} = \frac {11}3,\; \frac{h_4}{k_4} = \frac {18}5,\; \frac{h_5}{k_5} = \frac {119}{33}$

Cette notation étant un peu lourde, on utilise de préférence la suivante, ayant la même signification :

$\sqrt 13 = [3,1,1,1,1,6 \cdots]$

Enfin, que le quotient incomplet x₅ est égal à x₁, ce qui permet de conclure que la suite des coefficients se répète à partir du rang 1. On parle de suite périodique à partir d'un certain rang et on utilise la notation :

$\sqrt 13 = [3,\overline{1,1,1,1,6}]$

La barre utilisée ici est d'un usage fréquent dans la littérature. Elle signifie une répétition à l'infini de la suite d'entiers couverte par la barre.

[modifier] Eléments d'histoire

$Pierre de Fermat est à l'origine du défi lancé aux mathématiciens qui est à l'origine d'un large développement du savoir sur les fractions continues des nombres quadratiques.$

Pierre de Fermat est à l'origine du défi lancé aux mathématiciens qui est à l'origine d'un large développement du savoir sur les fractions continues des nombres quadratiques.

Dès le VI^e siècle, Âryabhata (476 - 550), un mathématicien indien, utilise les fractions continues pour obtenir des rationnels proches de racines carrés^[1]. Si Brahmagupta (598 – 668) un autre mathématicien indien s'intéresse à l'équation de Pell-Fermat et améliore la méthode dite chakravala pour la résoudre, il faut attendre le XII^e siècle et Bhāskara II pour voir une approche analogue à celles des fractions continues appliquées à cette équation. Son algorithme correspond à celui de l'article à la différence que a₀ est défini comme la plus proche valeur entière du nombre à approcher et non celle toujours inférieure. Cette différence est reportée à tous les coefficients a_n qui peuvent devenir négatifs. Cette spécificité, accélère un peu la recherche de la solution.

Ce n'est que plus tard que l'Europe s'intéresse à une démarche de cette nature. Il faut attendre le XVI^e siècle pour que Rafael Bombelli (1526 – 1572) fasse usage d'un ancêtre des fractions continues pour le calcul d'approximations de la racine carrée de 13^[2]. Pietro Antonio Cataldi (1548 – 1626) comprend la portée de la méthode de Bombelli et l'applique à toute les racines carrées, dans un petit opuscule à ce sujet^[3], il choisit l'exemple de la valeur 18.

A la suite d'un défi lancé par Pierre de Fermat en 1657, William Brouncker (1620 – 1684), trouve de manière empirique les relations qui relient la fraction continue d'un nombre quadratique à l'équation de Pell-Fermat. Il est probable que Bernard Frénicle de Bessy connaissait aussi cette méthode pour résoudre l'équation de Pell-Fermat dont il trouve toutes les solutions pour n plus petit que 150, ces travaux ont été perdus. Il défie Brouncker de trouver une solution à l'équation pour n = 313. Dans sa réponse, il indique qu'il ne lui a pas fallu plus d'une heure ou deux pour la trouver. La réponse est la suivante, pas nécessairement immédiate à calculer manuellement :

$x= 32\,188\,120\,829\,134\,849 \quad \text{et} \quad y = 1\,819\,380\,158\,564\,160\;$

Ces informations provient d'une intense relation epistolaire entre les différents acteurs, qui est finalement^[4] publié par John Wallis (1616 – 1703)

Le siècle suivant est celui des preuves. Leonhard Euler (1707 - 1783) reprend les travaux de Brouncker et ceux de Wallis, et démontre rigoureusement tous les aspects un peu élémentaire de la théorie, il montre aussi si la représentation en fraction continue d'un nombre est périodique, à partir d'un certain rang, alors ce nombre est quadratique^[5]. Il faut encore attendre les travaux de Joseph-Louis Lagrange (1736 - 1813) pour la démonstration d'une réciproque ainsi que des raisons de la validité de la méthode Bhāskara II ou de celle de Brouncker^[6]. Les propriétés de la fraction continue d'un nombre quadratique sont alors essentiellement élucidées, il ne reste plus qu'à comprendre dans quel cas une fraction continue n'est pas simplement périodique à partir d'un certain rang, mais périodique pure, ce qui est l'oeuvre^[7] d'Evariste Galois (1811 - 1832).

[modifier] Première propriété

Le calcul pratique d'une fraction continue d'un nombre quadratique est simple. Une est raison est une conséquence de la propriété :

Les quotients complets d'un nombre quadratique sont quadratiques.

Une manière de caractériser un nombre quadratique x est de trouver une racine √d d'un entier sans carré parfait et deux rationnels a et b tel que x soit égal à a + b.√d. Cette condition est nécessaire est suffisante. L'aspect nécessaire se déduit de la méthode de résolution d'une équation du second degré à l'aide du discriminant. Réciproquement, on peut remarquer que x est solution de l'équation, s'il est quadratique :

$x^2 + 2ax + a^2 - db^2=0\;$

Si, dans sa décomposition en facteurs premiers d ne contient que des puissances paires, le nombre d est rationnel et x n'est pas quadratique mais rationnel, s'il en contient quelques uns, il est toujours possible de les extraire de la racine carrée et adjoindre ces facteurs au rationnel b.

La propriété énoncée se démontre par récurrence. A l'ordre 1, le quotient complet est la différence d'un entier et d'un nombre quadratique, il est donc quadratique. Supposons la propriété vraie à l'ordre n et montrons là à l'ordre suivant. x_n est un nombre quadratique, en conséquence a_n+1 - x_n est aussi un nombre quadratique. Notons le a + b.√d, la transformation suivante montre que (a + b.√d)^-1, égal au quotient complet d'indice n + 1 est aussi quadratique :

$\frac 1{a + b \sqrt d} = \frac {a - b \sqrt d}{(a + b \sqrt d)(a - b \sqrt d)} = \frac a{a^2 - d b^2} + \frac a{a^2 - d b^2}\cdot \sqrt d$

On remarque l'expression au dénominateur ne peut être nulle. Si elle l'était, la racine de d serait un rationnel et d ne pourrait être un entier sans facteur carré. Cette première propriété simplifie la recherche de l'expression d'un nombre quadratique sous forme de fraction continue, le calcul de l'inverse d'un nombre quadratique est simple. L'usage de l'identité remarquable : (a + b)(a - b) = a² - b² est en conséquence fréquente.

[modifier] Période

Une autre propriété simplifie la détermination d'un nombre quadratique sous forme de fraction continue :

Un irrationnel x possède un développement en fraction continue périodique à partir d'un certain rang si et seulement si x est solution d'une équation du second degré à coefficients rationnels.

Si le développement de x est périodique à partir du rang p alors il existe un entier n tel que l'égalité suivante soit vérifiée. Ce qui justifie la notation, déjà utilisée dans le préambule :

$x =[a_0, a_1,\cdots, a_{p-1}, a_p,\cdots a_n,a_p, a_{p+1}\cdots \;] =[a_0, a_1,\cdots, a_{p-1},\overline{a_p, a_{p+1},\cdots a_n}]\;$

Cette proposition est au coeur de l'intérêt de la notion de fraction continue pour les nombres quadratiques. Autant il est relativement simple de montrer qu'un nombre ayant une fraction continue périodique à partir d'un certain rang est nécessairement quadratique, autant la réciproque est un peu plus délicate. Sa preuve date de plus d'un siècle après la découverte de cette propriété et est l'oeuvre de Lagrange. La démonstration présentée ici^[8] est relativement proche de l'originale^[9].

Démonstrations

Soit x un nombre réel, s'il admet un développement en fraction continue périodique à partir d'un certain rang, il possède un polynôme minimal de degré deux. :

Le polynôme minimal d'un nombre algébrique est le polynôme de plus petit degré et de monôme dominant ayant pour coefficient 1, qui admet pour racine cet entier. Par hypothèse, le développement de x est périodique à partir d'un certain rang, noté p. On en déduit, si x_p désigne le quotient complet d'indice p de x, l'égalité suivante :

$x_p = [a_p, a_{p+1},\cdots, a_n, x_p]\;$

Si h_n' (resp. k_n' ) désigne le numérateur (resp. le dénominateur) de la fraction continue [a_p, a_p+1, ..., a_n], l'égalité suivante, conséquence d'une propriété démontrée dans l'article Fraction continue, est vérifiée :

$x_p = \frac {x_ph_n' + h_{n-1}'}{x_pk_n' + k_{n-1}'}\quad\text{et}\quad k_n'x_p^2 +(k_{n-1}' - h_n')x_p - h_{n-1}' = 0\Leftrightarrow x_p^2 + \frac {k_{n-1}' - h_n'}{k_n'}{x_p} - \frac {h_{n-1}'}{x_p} = 0$

Et x_p possède un polynôme minimal de degré au plus deux. La valeur x est somme d'un rationnel : la réduite d'indice p et d'un irrationnel quadratique, la caractérisation des nombres quadratiques du paragraphe précédent montre que cette contidion est suffisante pour que x soit quadratique.

Soit x un nombre nombre quadratique, il admet un développement en fraction continue périodique à partir d'un certain rang :

Le principe de la méthode utilisée consiste à associer une forme quadratique à chaque quotient complet, provenant de son polynôme minimal. L'analyse de ces formes quadratiques montre qu'il ne peut en exister qu'un nombre fini, le quotient complet apparaît comme une racine du polynôme associé. Il n'existe que deux racines pour chaque polynôme, soit au total qu'un nombre fini possible de quotients complets. La suite des quotients complets se répète, d'où son caractère périodique.

Par hypothèse, x est racine d'un polynôme du second degré à coefficients rationnels, noté ici α.X² + β.X + γ. On associe à ce polynôme la forme quadratique φ :

$\forall (u,v) \in \mathbb R^2 \quad \varphi (u,v) = \alpha u^2 + \beta uv + \gamma v^2 \;$

Dans le même ordre d'idée, on associe au quotient complet d'indice j la forme quadratique φ_j définie par :

$\forall j \in \mathbb N - \{0\},\;\forall (u,v) \in \mathbb R^2 \quad \varphi_j (u,v) = \varphi (h_ju + h_{j-1}v,k_ju + k_{j-1}v) = \alpha_ju^2 + \beta_juv + \gamma_jv^2 \;$

Un développement de l'expression définissant φ_j en fonction des coefficients de φ et des suites (k_j) et (h_j) montre l'existence des trois coefficients α_j, β_j et γ_j définis par l'égalité précédente.

La définition du quotient complet montre l'égalité :

$\forall j \in \mathbb N - \{0\}\quad x = [a_0,a_1,\cdots,a_j,x_j]\quad\text{et}\quad x = \frac {h_jx_j + h_{j-1}}{k_jx_j + k_{j-1}}\;$

On en déduit que :

$\varphi_j(x_j,1)=\varphi (h_jx_j + h_{j-1},k_jx_j + k_{j-1})=\frac 1{(k_jx_j + k_{j-1})^2}\varphi \left(\frac {h_jx_j + h_{j-1}}{k_jx_j + k_{j-1}},1\right) = \frac 1{(k_jx_j + k_{j-1})^2}\varphi(x, 1) = 0$

La suite des coefficients (α_j) est bornée en valeur absolue :

La définition de φ_j et le fait que φ(x, 1) soit nul montrent que :

$\frac {\alpha_j}{k_j^2} = \frac 1{k_j^2}\varphi_j(1,0)=\frac 1{k_j^2}\varphi(h_j,k_j)= \varphi(\frac {h_j}{k_j},1) = \varphi(\frac {h_j}{k_j},1) - \varphi(x,1)$

On en déduit :

$\frac {\alpha_j}{k_j^2} = \alpha \left(\frac {h_j}{k_j}\right)^2 + \beta\frac {h_j}{k_j} +\gamma - \Big(\alpha x^2 + \beta x + \gamma\Big) =\alpha \left(\left(\frac {h_j}{k_j}\right)^2 - x^2\right) + \beta\left(\frac {h_j}{k_j} - x\right) = \left(\frac {h_j}{k_j} -x\right)\left(\alpha\left(\frac {h_j}{k_j} + x\right) + \beta\right)$

La fraction h_j / h _k est une approximation dont la distance à x est toujours inférieure à 1/k_j². On en déduit que h_j / h _k + x est en valeur absolue inférieur à 2|x| + 1 et :

$|\alpha_j| \le k_j^2\left|\frac {h_j}{k_j} -x\right|(|\alpha|(2|x|+1) + |\beta|)\le |\alpha|(2(|x|+1) + |\beta|$

Ce qui démontre l'assertion.

La suite des coefficients (γ_j) est bornée en valeur absolue :

Il suffit de remarquer que γ_j est égal à α_j-1 car :

$\forall j \in \mathbb N - \{0\}\quad \gamma_j = \varphi_j(0,1)=\varphi(h_{j-1},k_{j-1})= \varphi_{j-1}(1,0) = \alpha_{j-1} \;$

Le caractère majoré de la suite (α_j) permet de conclure.

La suite des coefficients (β_j) est bornée en valeur absolue :

Ici réside l'essentiel de l'astuce de la démonstration de Lagrange. Il remarque que le discriminant d_j du polynôme φ_j(X,1) possède aussi une lecture par un déterminant. Cette propriété permet de montrer que tous les discriminants des polynômes φ_j(X,1) sont égaux à celui du polynôme φ(X,1) noté ici d. Par voie de conséquence, la suite (β_j) est aussi bornée.

$\forall j \in \mathbb N- \{0\}\quad d = \beta^2 - 4\alpha \gamma = \beta_j^2 - 4\alpha_j \gamma_j = d_j\;$

Pour s'en convaincre, notons B la base canonique de R ² et ψ_j l'endomorphisme de R ² de matrice M_j dans la base canonique B, donnée par l'égalité suivante, un calcul de déterminant montre (le dernier calcul provient d'un résultat démontré dans l'article Fraction continue) :

$\forall j \in \mathbb N - \{0\}\quad M_j = \begin{pmatrix} h_j & h_{j-1} \\ k_j & k_{j-1} \end{pmatrix} \quad \det(\psi_j) = h_jk_{j-1} - h_{j-1}k_j = (-1)^j$

La matrice Φ de la forme quadratique φ ainsi que celle de ψ_j donnent une expression matricielle Φ_j de la forme quadratique φ_j. Il suffit alors de remarquer que d (resp. d_j) est égal à -4 fois le déterminant de la matrice Φ (resp. Φ_j) pour conclure :

$\Phi = \begin{pmatrix} \alpha & \beta /2 \\ \beta/2 & \gamma \end{pmatrix},\quad d = -4\det(\Phi) = -4\left(\alpha \beta -\frac {\beta^2}4\right)$

On en déduit :

$\Phi_j = {}^tM_j.\Phi.M_j,\quad d_j=-4\det(\Phi_j) = -4\det({}^tM_j.\Phi.M_j) =-4\det(M_j)^2\det(\Phi) = d$

Conclusion:

Les trois suites (α_j), (b_j) et (c_j) sont bornées en valeur absolue, il ne peut exister qu'un nombre fini de polynômes différents de la forme α_j.X² + β_j.X + γ_j. Un quotient complet est une racine d'un des polynômes précédemment cités, il ne peut en exister qu'un nombre fini. Il existe deux entiers n et p tel que x_p-1 soit égal à x_n. On en déduit que a _p est égal à a_n+1 et x_p à x_n+1 et donc que a_p+1 et égal à a_n+2 et ainsi de suite. Ceci montre le caractère périodique de la suite (a _j).

[modifier] Palindrome

Il est possible d'aller un peu plus loin sur les propriétés de la fraction continue d'un nombre quadratique. Certains nombres possèdent un développement purement périodique. c'est le cas, par exemple, du nombre d'or. En effet, un rapide calcul montre, si φ désigne le nombre d'or :

$\varphi = 1 + \frac 1{\varphi} = 1 + \frac 1{1 + \frac 1{\varphi}} = \cdots \quad\text{et}\quad \varphi = [1,1,1,\cdots] = [\overline{1}]$

La question se pose de savoir dans quel cas le développement en fraction continue est périodique pur, c'est à dire quelle condition rend le développement périodique dès le premier terme. Le nombre x est nécessairement un nombre quadratique. La réponse s'exprime en fonction de x_c, l'autre racine du polynôme annulant x. Le nombre x_c est souvent appelé conjugué de x, par analogie avec la situation où les racines sont complexes. Cette démonstration est l'œuvre d'Evariste Galois.

Le développement de x est purement périodique si et seulement si x est strictement plus grand que 1 et x_c, le conjugué de x est compris entre -1 et 0.^[8]

Cette propriété permet d'obtenir une description plus précise du développement en fraction continue d'une racine d'un entier non carré parfait :

Si x est la racine carrée d'un entier sans facteur carré, sa fraction continue prend la forme suivante :

$x = [a_0, \overline{a_1, a_2, a_3 \cdots a_3,a_2,a_1, 2a_0}]\;$

Si l'on élimine le dernier terme 2a₀ la période est symétrique et forme un palindrome. La partie symétrique pouvant ou non avoir un terme médian.

Les démonstrations utilisent les techniques de l'arithmétique. Il en existe de plusieurs natures. Les plus simples sont présentées dans l'article Méthode chakravala. Elles se fondent sur les propriétés d'un anneau d'entiers quadratiques. La démonstration historique, présentée ici, utilise d'autres techniques liées aux propriétés des formes quadratiques à coefficients entiers^[8].

Démonstrations

Le développement de x est purement périodique si et seulement si x est strictement plus grand que 1 et x_c, le conjugué de x est compris entre -1 et 0 :

Cette démonstration procède en plusieurs étapes :

Si le développement en fraction continue de x est purement périodique, le quotient complet d'indice 0 : x₀ est quadratique, strictement plus grand que 1 et son conjugué x_c0 est donné par la formule suivante :

$x_{c\,0} = \frac 1{x_c - a_0}\;$

Les résultats précédents montrent que x est solution d'une équation du second degré. Soit P(X) le polynôme unitaire du second degré annulant x et considérons la fraction rationnelle composée de P(X) et de a₀ + 1/X. La multiplication de cette fraction rationnelle par X² est un polynôme Q(X) de degré 2 admettant x₀ pour racine, en effet :

$Q(x_0) = x_0^2P\left(a + \frac 1{x_0}\right) = x_0^2P(x) = 0\;$

Le nombre x₀ est irrationnel, sinon x ne le serait pas. Il est de plus racine du polynôme Q(X) de degré 2 à coefficients rationnels, il est donc quadratique. Il est plus grand que 1 car tous les quotients complets le sont. Il l'est strictement car sinon x serait rationnel.

Il ne reste plus qu'à montrer la formule annoncée. L'application σ, qui à un élément de l'extension quadratique Q[x] associe son conjugué est un automorphisme de corps laissant Q invariant. Le conjugé d'un nombre quadratique de la forme a + b.√d, où a et b sont des nombres rationnels et d un entier sans facteur carré est le nombre a - b.√d. L'analogie avec la situation des nombres complexes est à l'origine de cette dénomination. L'égalité x₀(x - a₀) = 1, directement issue de la définition du quotient complet d'indice 0, montre que :

$(x- a_0)x_0 = 1 \;\text{donc}\quad \sigma\Big((x- a_0)x_0\Big) = \sigma(1) = 1 = (x_c - a_0)x_{c\,0} \quad \text{et}\quad x_{c\,0} = \frac 1{x_c - a_0}$

Si le développement en fraction continue de x est purement périodique, x est strictement plus grand que 1 et x_c est strictement compris entre -1 et 0 :

Soit a₀, a₁, ..., a_n la période de x, la partie entière de x est égale à a₀ et donc à a_n+1, ce qui montre que x est plus grand que 1, il est strictement plus grand, sinon il ne serait pas irrationnel.

On dispose de l'égalité x = [a₀, a₁, ..., a_n, x], ce qui montre (pour les détails voir l'article Fraction continue ) :

$x = \frac{xh_n + h_{n-1}}{xk_n + k_{n-1}}\quad\text{et}\quad P(x) =0 \quad \text{si}\quad P(X) = X^2 - \frac{h_n - k_{n-1}}{k_n}X - \frac {h_{n-1}}{k_n} = 0$

Le fait que x soit strictement positif montre que h_n-1 et k_n sont strictement positifs. La deuxième racine de P(X) est le conjugué x_c de x, le produit des racines x.x_c est égal à la constante du polynôme P(X) et est négative. Comme x est positif, x_c est strictement négatif.

Enfin, on remarque que P(-1) est strictement positif, en effet :

$k_n > k_{n-1}\;\text{et}\; h_n > h_{n-1}\quad \text{donc}\quad P(-1) = \frac {k_n - k_{n-1} + h_n - h_{n-1}}{k_n}>0\;$

On remarque que P(-1) est strictement positif, P(0) strictement négatif, le théorème des valeurs intermédiaires montre que la racine négative x_c se situe strictement entre -1 et 0.

Si x est strictement plus grand que 1 et x_c est strictement compris entre -1 et 0, le développement en fraction continue de x est purement périodique :

La méthode consiste à montrer l'existence d'un entier n tel que, pour tout j strictement positif, a_j-1 est égal à a_j+n-1. Ainsi, a₀ est égal à a_n, a₁ est égal à a_n+1 etc... Pour ce faire, on procède en deux étapes :

La suite des quotients complets (x_j) est strictement supérieure à 1 et la suite (x_cj) des conjugués des quotients complets est strictement compris entre -1 et 0 :

Montrons ce résultat par récurrence sur j. Si j est égal à 0, la proposition est vérifiée par hypothèse. Supposons la propriété vraie à l'ordre j et montrons là à l'ordre j + 1. L'irrationnel quadratique x_j vérifie les hypothèses de la première proposition de cette boite déroulante. Son quotient incomplet d'indice 0 est égal à a_j et son quotient complet à x_j+1 et :

$(1)\quad x_{c\,j+1} = \frac 1{x_{c\,j} - a_j}\;$

Par construction, a_j+1 est strictement positif, x_j est un irrationnel et est donc différent de 1, comme sa partie entière est au moins égal à 1, x_j est strictement plus grand que 1. De plus, x_cj est non nul et strictement négatif, ce qui montre que x_cj - a_j est strictement inférieur à -1, donc que x_j+1 est strictement compris entre -1 et 0.

Conclusion :

Le fait que x soit un irrationnel quadratique montre qu'à partir d'un rang p, la suite est périodique. Soit n cette période, c'est à dire :

$\forall j \ge p \quad a_{j+n} = a_j \quad\text{et}\quad x_{j+n}=x_j\;$

L'objectif est de montrer que p est égal à 0. Pour cela, considérons un entier m strictement positif et supérieur ou égal à p, montrons que m est strictement plus grand que p. L'égalité (1) montre :

$-\frac 1{x_{c\,m}} =a_{m-1} - x_{c\,m-1}= -\frac 1{x_{c\,m+n}} =a_{m+n-1} - x_{c\,m+n-1}\;$

On en déduit que a_m-1 et a_m+n-1 sont tous deux égaux à la partie entière de -1/x_cm et ils sont égaux. Ceci permet de déduire que x_m-1 et x_m+n-1 le sont aussi car leurs conjugués le sont :

$x_{c\,m-1} = a_{m-1} + \frac 1{x_{c\,m}} = a_{m+n-1} + \frac 1{x_{c\,m+n}}= x_{c\,m+n-1}\;$

Le fait que a_m-1 et a_m+n-1 soient égaux et que x_m-1 et x_m+n-1 le soient aussi montre que m n'est pas le premier terme de la partie périodique de la suite (a_j). Ceci termine la démonstration.

Si p est un entier sans facteur carré, la période de la fraction continue de √p démarre au deuxième terme et le dernier terme de la période est égal à 2a₀ :

Soit a₀ le coefficient d'indice 0 de la fraction continue de √p. Le nombre quadratique a₀ + √p possède un développement périodique pure d'après la proposition précédente. Il est en effet strictement plus grand que 1 et son conjugué, égal à a₀ - √p, est compris entre -1 et 0. Pour s'en persuader, il suffit de remarquer que a₀ est la partie entière de √p.

Le premier terme de la fraction continue de a₀ + √p est égal à la partie entière de ce nombre ou encore à 2a₀. Il suffit de remarquer, pour conclure, que √p possède le même développement en fraction continue, à l'exception du premier terme, égal à a₀ et non à 2a₀.

Si x est la racine carrée d'un entier sans facteur carré, sa fraction continue prend la forme suivante :

$x = [a_0, \overline{a_1, a_2, a_3 \cdots a_3,a_2,a_1, 2a_0}]\;$

Pour une raison de simplicité, la démonstration consiste à étudier la structure de la période de x + a₀. Dans le cas où p est égal à 19, on trouve :

$4 + \sqrt 19 = [8, \overline{2, 1, 3, 1, 2, 8}]$

La liste des quotients complets, notés ici x_i est :

$x_0 =\frac{\sqrt 19 + 4}1,\, x_1= \frac {\sqrt 19 + 4}3,\,x_2= \frac {\sqrt 19 + 2}5,\,x_3= \frac {\sqrt 19 + 3}2,\,x_4= \frac {\sqrt 19 + 3}5,\,x_5= \frac {\sqrt 19 + 2}3,\,x_6= \frac{\sqrt 19 + 4}1$

Ce qui permet d'imaginer le résultat suivant :

(1) Il existe deux entiers strictement positifs b_i et c_i tel que x_i = (√p + b_i)/c_i tel que b_i² est strictement plus petit que p et c_i divise p - b_i² :

Montrons cette proposition par récurrence. Pour i égal à 1, on a :

$x + a_0 = 2a_0 + \sqrt p - a_0 = 2a_0 + \frac {p - a_0^2}{\sqrt p + a_0} \quad\text{et}\quad x_1 = \frac {\sqrt p + a_0}{p - a_0^2},\;b_1 = a_1,\;c_1 = p - a_1^2$

Supposons la propriété vrai à l'ordre i et montrons là à l'ordre i + 1 :

On définit a_i+1 comme la partie entière de x_i et b_i+1 égal à a_i+1.c_i - b_i. L'entier a_i+1 est défini comme la partie entière d'un nombre strictement plus grand que 1, il est donc strictement positif. Montrons que b_i+1 est aussi strictement positif. b_i est strictement plus petit que √p, par hypothèse de récurrence, donc b_i/c_i est strictement plus petit que la moitié de x_i et donc que sa partie entière a_i+1, ce qui revient exactement à dire que b_i+1 est strictement positif. Il ne reste plus qu'à montrer que c_i+1 divise p - b_i+1² :

$x_i = \frac {\sqrt p + b_i}{c_i} = a_{i+1} + \frac {\sqrt p -a_{i+1}c_i + b_i}{c_i} = a_{i+1} + \frac {p - b_{i+1}^2}{c_i(\sqrt p +b_{i+1})}=a_{i+1}+\frac 1\frac {\sqrt p +b_{i+1}}{c_{i+1}}\quad \text{si}\quad c_{i+1} = \frac {p - b_{i+1}^2}{c_i}$

Par construction b_i+1 est un entier de carré strictement plus petit que p, pour montrer le reste de la proposition, il suffit de montrer que c_i divise p - b_i+1². Cette propriété est la conséquence du fait que c_i divise p - b_i² et de l'égalité suivante :

$p - b_{i+1}^2 = p - (b_i + a_{i+1}c_i)^2 = p - b_i^2 + c_i(2b_ia_{i+1} + a_{i+1}^2c_{i+1})$

On remarque que les coefficients b_i et c_i forment aussi deux palindromes sur l'exemple √19 choisi. Cette propriété est encore générale et découle de la propriété suivante :

(2) Si i est un entier strictement supérieur à 1, la partie entière du nombre quadratique (√p + b_i)/c_i-1 est égal à a_i-1 et son premier quotient complet à (√p + b_i-1)/c_i-2 :

Dans un premier temps, on remarque que c_i-1 est bien un diviseur de p - b_i², la démonstration précédente montre en effet que p - b_i² est égal à c_i-1.c_i. L'égalité suivante montre que la partie entière de (√p + b_i)/c_i-1 est égal à a_i-1 :

$\frac {\sqrt p + b_i}{c_{i-1}} = \frac {\sqrt p + a_{i-1}c_{i-1} - b_{i-1}}{c_{i-1}} = a_{i-1} + \frac {\sqrt p - b_{i-1}}{c_{i-1}}$

La première démonstration montre que (√p - b_i)/c_i-1 égal à l'opposé du conjugé de x_i-1 est bien un nombre strictement compris entre 0 et 1. Montrons ensuite que le premier quotient complet est bien égal à (√p + b_i-1)/c_i-2 :

$\frac {\sqrt p + b_i}{c_{i-1}} = a_{i-1} + \frac {\sqrt p - b_{i-1}}{c_{i-1}} = a_{i-1} + \frac {p - b_{i-1}^2}{c_{i-1}(\sqrt p + b_{i-1})} = a_{i-1} + \frac 1\frac{\sqrt p + b_{i-1}}{c_{i-2}}\quad\text{car}\quad c_{i-1} c_{i-2} = p - b_{i-1}^2$

(3) Il existe deux entiers i et j strictement positifs, tel que x_i et x_i+j sont en correspondance. La première valeur possible pour i est (n+1)/2 et pour j : 1 si la période n est impaire et n/2 pour i et 2 pour j sinon :

On remarque que x₁ et x_n+1 sont en correspondance, cette propriété est donc vérifiée pour au moins un couple de quotients complets. Montrons que si x_i et x_i+j sont en correspondance et que j est strictement plus grand que 1, alors x_i+1 et x_i+j-1 sont aussi en correspondance. Le quotient complet précédent x_i+j est égal au premier quotient complet de (√p + b_i+j)/c_i+j-1), c'est à dire au premier quotient complet de x_i, d'après la proposition précédente.

On remarque alors que x₁ et x_n+1 sont en correspondance de même que x₂ et x_n et en remontant de proche en proche, x_(n-1)/2 et x_(n+1)/2 sont aussi en correspondance si n est impair. Cette configuration est celle de l'exemple p = 19. La propriété de palindrome est alors établi. Si n est impair, le même raisonnement montre que x_n/2 et x_{n/2 +2} sont en correspondance, il reste encore à vérifier l'égalité entre a_n/2 et a_{n/2 +1}.

(4) Si n est impair, a_(n-1)/2 et a_(n+1)/2 sont égaux :

Cette configuration se produit par exemple pour 13:

$3 + \sqrt 13 = [6, \overline{1, 1, 1, 1, 6}]$

La liste des quotients complets est :

$x_1= \frac {\sqrt 13 + 3}4,\,x_2= \frac {\sqrt 13+ 1}3,\,x_3= \frac {\sqrt 13 + 2}3,\,x_4= \frac {\sqrt 13 + 1}4,\,x_5=\frac{\sqrt 13 + 3}1$

Le raisonnement précédent montre que a₁ est égal à a₄, il faut encore montrer que a₂ est égal à a₃. L'étape (4) permet de conclure. Le quotient complet x_n/2 est égal à (√p + b_{n/2 +2})/c_{n/2 + 1} sa partie entière est donc égal à a_{n/2 + 1}, c'est à dire au coefficient d'indice suivant, ce qui termine la démonstration.

[modifier] Equation de Pell-Fermat

[modifier] Structure de la solution

La fraction continue est une technique à la fois théorique et pratique pour résoudre l'équation de Pell-Fermat suivante, si p est un entier sans facteur carré :

$(1)\quad x^2 - p\cdot y^2 = \pm 1$

Une solution est un couple (a, b) d'entiers tel que a² - p.b² soit égal à plus ou moins un. Pour plus de simplicité dans les énoncées, ne sont considérées que les solutions dont les deux valeurs sont strictement positives. A part les solutions triviales (1, 0) et (-1, 0) toutes les autres se déduisent par multiplication ou non des deux termes a et b par -1. Trois propositions permettent de comprendre comment se structurent les solutions.

Si (a, b) est un couple solution de l'équation (1), il existe un indice n tel que (h_n, k_n) soit égal au couple solution. Ici h_n et k_n désigne le numérateur et le dénominateur de la réduite de rang n de la valeur √p.

Autrement dit, toutes les solutions de l'équation se trouvent dans la suite des réduites de la fraction continue de √p.

Pour aller plus loin, il est nécessaire d'analyser la fraction continue de √p. Elle est de la forme, d'après le paragraphe précédent :

$\sqrt p = [a_0,\overline{a_1,a_2,\cdots , a_2,{\color{Red}a_1},2a_0}]$

Notons k l'indice du coefficient a₁ qui se situe juste avant le coefficient 2a₀, c'est à dire celui en rouge dans l'expression précédente. Cela signifie que la période de la fraction continue est égale à k + 1.

Un indice n correspond à une solution de l'équation (1) si, et seulement si, soit n est égal à k, soit il existe un entier positif q tel que n = k + q.(k + 1).

Ce qui signifie que les indices solutions sont ceux qui correspondent aux coefficients de valeur égale à a₁, qui se situe exactement avant le coefficient de valeur égale à 2.a₀. Il en existe exactement un par période.

Si k est pair, il existe des solutions pour la valeur -1, elles correspondent aux indices k et k + 2q.(k + 1), les autres indices donne la valeur 1. Si k est impair, la valeur -1 n'est jamais atteinte.

Une autre manière d'énoncer cette proposition est de dire que la valeur -1 est atteinte si, et seulement si, la période est impair, elle est alors atteinte une fois sur deux et la première solution est négative.

Démonstrations

Si (a, b) est un couple solution de l'équation (1), il existe un indice n tel que (h_n, k_n) soit égal au couple solution :

Cette proposition est une conséquence de la qualité de l'approximation par le rationnel h_n / k_n du nombre √p.

L'article Fraction continue et approximation diophantienne montre que si une fraction h / k approche un réel quelconque avec une précision meilleure que 1/2.k², la fraction est infailliblement une réduite de la fraction continue du réel. Si le couple est une solution de l'équation (1) :

$a^2 - pb^2 = 1,\quad \left(\frac ab\right)^2 = p + \frac 1{b^2}\quad \text{et}\quad \frac ab = \sqrt p \sqrt{1 + \frac 1{pb^2}}$

Or, la fonction qui à x associe 1 + 1/2.x majore la fonction √(1 + x) si x est positif. En remarquant que 1 est nécessairement plus petit que √p on en déduit :

$\left|\frac ab - \sqrt p \right| \le \frac 1{2\sqrt p b^2} < \frac 1{2 b^2}$

Ce qui impose à la fraction a / b d'être une réduite de √p et démontre la proposition.

Un indice n correspond à une solution de l'équation (1) si, et seulement si, soit n est égal à k, soit il existe un entier positif q tel que n = k + q.(k + 1) :

Le paragraphe précédent contient les calculs permettant de prouver simplement cette proposition. Il suffit de montrer que h_n² - p.k_n² est égal, au signe près, au coefficient c_n défini au paragraphe précédent pour la détermination du palindrome. Une fois cette proposition démontrée, il ne reste plus qu'à déterminer dans quel cas c_j prend la valeur 1.

La valeur |h_n-1² - p.k_n-1²| est égale à c_n :

L'article Fraction continue montre que √p est égal à [a₀, a₁, ..., a_n-1,x_n] ce qui donne les égalités :

$\frac {x_nh_{n-1} + h_{n-2}}{x_nk_{n-1} + k_{n-2}} = \sqrt p\quad\text{et}\quad x_n = \frac {-h_{n-2} + k_{n-2}\sqrt p}{h_{n-1} - k_{n-1}\sqrt p}$

Ce que l'on peut encore écrire, avec les notations du paragraphe précédent :

$\frac {b_n}{c_n} + \frac 1{c_n} \sqrt p = \frac {-h_{n-1}h_{n-2} +pk_{n-1}k_{n-2}}{h_{n-1}^2 - pk_{n-1}^2} + \frac {h_{n-1}k_{n-2} - k_{n-1}h_{n-2}}{h_{n-1}^2 - pk_{n-1}^2}\sqrt p$

Comme (1, √p) forme une famille libre sur l'ensemble des rationnels, on en déduit, du fait que h_n-1.k_n-2 - k_n-1.h_n-2 est égal à (-1)ⁿ (cf l'article Fraction continue) :

$\frac 1{c_n} = \frac {h_{n-1}k_{n-2} - k_{n-1}h_{n-2}}{h_{n-1}^2 - pk_{n-1}^2}\quad\text{et}\quad h_{n-1}^2 - pk_{n-1}^2 = (-1)^n c_n$

La valeur c_j est égale à 1 si, et seulement si, il existe un entier q tel que j = q.(k + 1) :

La suite des c_j est périodique de période k + 1, il suffit de montrer que dans l'intervalle des entiers j compris entre 1 et k + 1, uniquement le dernier vérifie c_j est égal à 1.

Montrons que c_k+1 est égal à 1. Par définition de k, x _k+2 est égal à a₀ + √p et a _k+2 = 2a₀. Le calcul suivant montre que b _k+2 est égal à a₀ et c _k+2 = p - a₀² :

$a_0 + \sqrt p = 2a_0 + (-a_0 + \sqrt p) = 2a_0 + \frac 1{\frac {a_0 + \sqrt p}{p^2 - a_0^2}}$

De plus, les calculs précédents ont établi que c_j.c_j+1 = p - b_j+1², donc :

$c_kc_{k+2} = p - a_0^2 \quad\text{et}\quad c_{k+1}(p-a_0^2) = p - a_0^2 \Rightarrow c_{k+1} = 1$

Réciproquement, montrons que si j est un entier compris entre 1 et k + 1 et si c_j est égal à 1, alors j est égal à k + 1. Si c_j est égal à 1, x_j est la somme d'un entier et de √p, sa partie fractionnaire égale à √p - a₀ et donc x_{j +1} à x _k+2, il correspond au dernier élément de la période, c'est à dire que j est égal à k + 1. L'indice de la réduire solution est précède k + 1, comme le montre le calcul de la proposition précédente, il est donc bien égal à k.

Si k est pair, il existe des solutions pour la valeur -1, elles correspondent aux indices k et k + 2q.(k + 1), les autres indices donne la valeur 1. Si k est impair, la valeur -1 n'est jamais atteinte :

C'est une conséquence directe de l'égalité h_n-1² - p.k_n-1² = (-1)ⁿ.c_n. En remplaçant n par un multiple de k + 1, on obtient :

$h_{k + q(k+1)}^2 - pk_{k + q(k+1)}^2 = (-1)^{q(k+1)}\;$

Si k est impair, seule la valeur 1 est obtenue, sinon une alternance de 1 et de -1 apparaît, la première valeur étant négative.

[modifier] Groupe des unités

Article détaillé : Groupe des unités d'un anneau d'entiers quadratiques.

En théorie algébrique des nombres, il est parfois important de connaître la structure du groupe des unités d'un anneau d'entiers algébriques. Cette situation se produit en particulier pour les anneau d'entiers quadratiques. La compréhension de cette structure est utile, par exemple, de démontrer le dernier théorème de Fermat pour n = 3 ou 5, ou pour établir la loi d'apparition des nombres premiers dans la suite de Fibonacci (cf Entier du corps quadratique Q[√5]).

On est amené à trouver les éléments inversible de l'anneau Z[ω] qui sont de la forme a + b.ω ou ω est un entier quadratique et a et b des éléments de Z. On montre que cela revient à résoudre une des deux équations diophantienne suivante, ou d est un entier positif non carré parfait et f un entier positif tel que 4.f + 1 n'est pas un carré parfait :

$(1)\; x^2 + dy^2 = \pm 1\quad (2)\;x^2 + xy -fy^2 = \pm 1 \;$

La première a déja été étudiée, la deuxième est très similaire. On dispose par exemple de la propriété suivante :

Si le couple (a, b) est solution de l'équation (2), alors a / b est une réduite de l'entier quadratique -ω_c défini par :

$\omega = \frac 12 (1 + \sqrt {4f + 1}) \quad\text{et}\quad -\omega_c = \frac 12 (\sqrt {4f + 1} - 1)$

La notation un peu étrange de -ω_c pour indiquer l'entier quadratique approché provient du fait que ω est l'entier quadratique qui définit l'anneau Z[ω], ici le signe c en indice indique la valeur conjuguée. L'origine de ces formules est indiquée dans l'article entier quadratique.

Un calcul strictement analogue montre que l'avant dernier terme de la période de la fraction continue correspond aussi à la réduite recherchée.

Démonstration

Soit d l'entier égal à 4.f + 1. L'équation (2) s'écrit :

$x^2 + xy + \frac {y^2}4 - \frac d4y^2 =(x + \frac y2)^2 - \left( \frac {\sqrt d y}2\right)^2 = (x + \omega y)(x + \omega_c y) = \pm 1$

On remarque de ω = 1/2(1 + √d) et ω_c = 1/2(1 - √d). Soit (a, b) un couple solution de l'équation (2) tel que a et b soient positifs, On obtient :

$\left(\frac ab + \omega\right)\left(\frac ab + \omega_c\right) = \frac {\pm 1}{b^2}\quad\text{et}\quad \left|\frac ab + \omega_c\right| = \frac 1{b^2 \left(\frac ab + \omega\right)}$

De par sa définition ω est strictement supérieur à 1. Si le couple (a, b) est solution de (2) alors a est supérieur à b et a / b aussi supérieur à 1. On obtient la majoration suivante, qui montre que a / b est une réduite de -ω_c :

$\left|\frac ab + \omega_c\right| = \frac 1{2b^2}$

[modifier] Extraction d'une racine carrée

[modifier] Première méthode

Les propriétés de la fraction continue d'un nombre quadratique permettent de calculer des approximations des racines carrées. La première technique consiste simplement à calculer les coefficients de la fraction continue puis ses réduites. Si l'on cherche la racine de 3, on trouve dans un premier temps :

$\sqrt 3 = 1 + (\sqrt 3 - 1) = 1 + \frac {(\sqrt 3 - 1)(\sqrt 3 + 1)}{\sqrt 3 - 1} = 1 + \frac 1{\frac {\sqrt 3 + 1}2} = 1 + \frac 1{1 + \frac {\sqrt 3 - 1}2} = 1 + \frac 1{1 + \frac 1{\sqrt 3 + 1}} = 1 + \frac 1{1 + \frac {\sqrt 3 - 1}2} = 1 + \frac 1{1 + \frac 1{ 2 + \sqrt 3 - 1}}$

Le quotient complet (√3 - 1)^-1 égal à 1/2.(√3 + 1) a déjà été développé en fraction continue, on en déduit l'expression :

$\sqrt 3 = [1,1,2,1,2,\cdots] = [1,\overline{1,2}]$

Les réduites se calculent par des formules de récurrences, étudiées dans l'article Fraction continue. Si h_n / kn sont ces réduites :

$h_{n+2} = a_{n+2}h_{n+1} + h_n \quad \text{et}\quad h_{n+2} = a_{n+2}h_{n+1} + h_n\;$

Ce qui donne les approximations suivantes de la racine de trois :

$\begin{align} h_0 &= 1,\quad h_1 &=2,\quad h_2 &= 2 \times 2 + 1 &= 5,\quad h_3 &= 1 \times 5 + 2 &= 7,\quad h_4 &= 19, & h_5 &= 26, &\cdots \, h_{10} &= 989\\ k_0 &= 1,\quad k_1 &=1,\quad k_2 &= 2 \times 1 + 1 &= 3,\quad k_3 &= 1 \times 3 + 1 &= 4,\quad k_4 &= 11, & k_5 &= 15, &\cdots \, k_{10} &= 571 \end{align}$

Ainsi, à la 10^ième étape, on obtient la fraction 989 / 571, approximativement égale à 1,732 049 alors que les 7 premiers chiffres significatifs exacts sont 1,732 051. La précision de cet algorithme à l'étape n est meilleure que 1/(2h_n²) d'après les calculs précédents. Pour l'approximation d'indice 10, on sait donc que l'erreur est inférieure à 1/(2x571²) meilleure que le 600 000^ième. Une force de cet algorithme est la qualité des solutions proposées, au sens où toute fraction de type a/b avec b strictement inférieur à 571 sera nécessairement moins bonne que la dixième réduite de la fraction continue. Par exemple, la meilleure approximation décimale de la racine de trois avec deux chiffres significatif, égale à 17/10, commet une erreur supérieur au 50^ième. Celle un peu équivalente 19/11 correspondant à la réduite d'indice 4 propose une approximation au 200^ième, soit quatre fois meilleure. Cette propriété est démontrée dans l'article Fraction continue et approximation diophantienne.

[modifier] Accélération violente

L'étude de l'équation de Pell-Fermat permet d'imaginer un algorithme dont la convergence est beaucoup plus rapide. Etudions le cas général. La réduite d'indice n est solution de l'équation de Pell-Fermat suivante si n + 1 est la période de la fraction continue associée à la racine de d, un entier non carré parfait :

$x^2 - dy^2 =\pm 1\;$

L'égalité suivante montre, qu'à partir une solution (h_n, k_n), il est possible d'en construire une nouvelle, en considérant le carré de l'équation :

$(h_n^2 - d k_n^2)^2 = 1 = (h_n - \sqrt d k_n)^2(h_n + \sqrt d k_n)^2 = (h_n^2 + dk_n^2 - \sqrt d\cdot 2h_nk_n)(h_n^2 + d k_n^2 + \sqrt d\cdot 2h_nk_n)$

En appliquant à nouveau l'identité remarquable traitant de (a - b)(a + b), on obtient :

$(h_n^2 + dk_n^2)^2 - d(2h_nk_n)^2 = 1$

Si l'on note u_j et v_j le numérateur et le dénominateur de cette suite, elle est définie par récurrence :

$u_1 = h_n,\quad u_{j+1} = u_j^2 + dv_j^2 \quad\text{et}\quad v_1= k_n,\quad v_{j+1} = 2u_jv_j$

L'application au cas de la racine de 3 donne pour première valeur 2/1, en effet, 2² - 3 x 1² = 1 est bien la première solution non triviale, on trouve ensuite :

$\begin{align} u_1 &= 2,\quad u_2 = 2^2 + 3\times 1^2 &= 7,&\quad u_3 = 7^2 + 3\times 4^2 &= 97,\quad u_4 &= 97^2 + 3\times 56^2 &= 18\,817,\quad u_5 &= 708\,158\,977 \\ v_1 &= 1,\quad v_2 = 2\times 2\times 1 &= 4,&\quad v_3 = 2\times 7\times 4 &= 56,\quad v_4 &= 2\times 97\times 56 &= 10\,864,\quad v_5 &= 408\, 855\,776 \end{align}$

Il n'existe peu d'applications nécessitant d'aller au delà de l'étape 5, la précision de u₅ / u₅ dépasse déjà 20 décimales. Tous ces couples de numérateurs et dénominateurs sont des solutions de l'équation de Pell-Fermat, la théorie indique que ce sont des réduites de la fraction continue de la valeur recherchée, ici la racine de trois. En conséquence, la précision est toujours meilleure que l'inverse du double du carré du dénominateur.

[modifier] Un exemple historique de résolution de l'équation de Pell Fermat

L'équation suivante possède une longue histoire :

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

Brahmagupta^[10] l'utilise comme illustration d'un ancêtre de la méthode chakravala dès le VI^e siècle. A cet époque, les nombres négatifs n'étaient pas considérés. Il est repris par Bhāskara II qui perfectionne la méthode^[11] et lui donne une puissance algorithmique un peu supérieur à celle par les fractions continues, présenté ici.

Le 3 janvier 1658, l'exemple est encore repris par Pierre de Fermat, qui en fait un défi lancé aux mathématiciens de toute l'Europe^[12]. Fermat conclut par « si elle n'est fournie ni par l'Angleterre, ni par la Gaule Belgique ou Celtique, elle le sera par la Narbonnaise^[13] ». Ce défi est à l'origine des travaux anglais sur les fractions continues des nombres quadratiques et leur connexion avec l'équation de Pell Fermat.

Appliquons l'algorithme des fractions continues pour calculer les coefficients et les quotients complets :

$\sqrt 61 = 7 + \frac 1{\frac {7 + \sqrt 61}{12}},\quad \frac {7 + \sqrt 61}{12} = 1 + \frac 1{\frac{5 + \sqrt 61}{3}},\quad \frac{5 + \sqrt 61}{3} = 4 + \cfrac 1{\frac{7 + \sqrt 61}{4}},\quad \frac{7 + \sqrt 61}{4} = 3 + \frac 1{\frac{5+ \sqrt 61}{9}}$

Ce qui donne les premiers coefficients : 7, 1, 4, 3. On continue avec :

$\frac{5 + \sqrt 61}{9} = 1 + \cfrac 1 {\frac{4 + \sqrt 61}{5}} ,\quad \frac{4 + \sqrt 61}{5} = 2 + \frac 1 {\frac{6 + \sqrt 61}{5}}$

On dispose maintenant de la section commençante 7, 1, 4, 3, 1, 2. Il n'est plus nécessaire de continuer. On remarque que les quotients complets x₅ et x₆ sont associés ce qui se remarque au fait qu'ils ont le même dénominateur. La moitié du palindrome est déjà explicitée. Comme ce phénomène se produit pour deux indices adjacents, on peut en déduire que la période est impaire et égale à 2 x 5 + 1. On peut aussi en déduire que a₆ est égal à a₅, ainsi que les termes suivants : 2, 1, 3, 4, 1. Enfin, le dernier terme est égal au double du premier, soit 14. Le premier candidat à la solution est donc celui mise en valeur en rouge dans l'expression suivante :

$\sqrt 61 = [7,\overline{1,4,3,1,2,2,1,3,4,{\color{Red}1},14}]$

On sait que la fraction réduite d'indice 10, appliquée à l'équation du paragraphe donne 1 en valeur absolue. Pour la calculer, le plus simple est de commencer par utiliser les relations de récurrences (cf l'article Fraction continue). Si h_n / k_n désigne la réduite d'indice n et a_n le coefficient d'indice n, on dispose des formules :

$h_{n+2} = a_{n+2}h_{n+1} + h_n \quad \text{et}\quad h_{n+2} = a_{n+2}h_{n+1} + h_n\;$

En remarquant que la première et la deuxième réduite sont égales à 7/1 et 8/1, on obtient :

$\begin{align} h_2 &= 4 \times 8 + 7 &= 39,\quad h_3 &= 3 \times 39 + 7 &= 125,\quad h_4 &= 164, & h_5 &= 453, & h_6 &= 1\,070, &\cdots \, h_{10} &= 29\;718\\ h_2 &= 4 \times 1 + 1 &= 5 ,\quad k_3 &= 3 \times 5 + 1 &= 16,\quad k_4 &= 21, & k_5 &= 58, & k_6 &= 137, &\cdots \, k_{10} &= 3\;805 \end{align}$

Cependant, comme l'indice de la réduite calculée est pair, la solution associée à l'équation du paragraphe est de signe est négatif, ce qui se vérifie aisément :

$29\,718^2 - 61\times 3\,805^2 = 883\,159\,524 - 883\,159\,525 = -1$

Ni Brahmagupta, ni Fermat n'acceptent ce type de solution. La bonne réduite est donc la 21^ième. Pour la calculer, on peut soit prolonger le calcul, soit utiliser le même principe que celui de la deuxième méthode d'extraction d'une racine :

$(h_{10}^2 + 61\cdot k_{10}^2)^2 - 61\cdot (2h_{10}k_{10})^2 = 1$

L'article équation de Pell-Fermat montre que cette formule donne exactement la solution associée à la 21^ième réduite de la fraction continue. La solution du défi de Fermat est :

$h_{21} = 1\,766\,319\,049,\quad k_{21} = 226\,153\,980\quad\text{et}\quad 1\,766\,319\,049^2 - 61\times 226\,153\,980^2 = 1$

[modifier] Voir aussi

[modifier] Notes

↑ G Ifrah Histoire universelle des chiffres: L'intelligence des hommes racontée par les nombres et le calcul Robert Laffont 1994 (ISBN 2221901002)
↑ M. T. Rivolo A. Simi The computation of square and cube roots in Italy from Fibonacci to Bombelli (Italian) Arch. Hist. Exact Sci. 52 (2) 1998 pp 161-193
↑ S. Maracchia Estrazione di radice quadrata secondo Cataldi Archimede 28 (2) 1976 pp 124-127
↑ John Wallis Commercium epistolicum de quæstionibus quibusdam mathematicis nuper habitum Oxonii : Excudebat A. Lichfield, Impensis Tho. Robinson 1658
↑ Leonhard Euler, Introductio in analysin infinitorum. Vol. I, Chapter 18 1748
↑ Ces résultats sont publiés dans : Leonhard Euler et Joseph-Louis Lagrange Eléments d'algèbre Lyon, Bruyset et Paris, Desaint 1774. Le livre contient une centaine de pages nommées Additions par Lagrange.
↑ Evariste Galois annonce le résultat suivant « Si une des racines d’une équation de degré quelconque est une fraction immédiatement périodique, cette équation aura nécessairement une autre racine également périodique que l’on obtiendra en divisant l’unité négative par cette même fraction continue périodique écrite dans un ordre inverse. » extrait de : Histoire de fractions continues par C. Bresinski de l'Université des Sciences et Technologies de Lille p 63
↑ ^a ^b ^c Les démonstrations proposées ici s'inspirent du document : Développement d'un réel en fractions continues par M. Couchouron pour les développements périodiques et l'équation de Pell-Fermat
↑ Elle est accessible sur le net : Joseph-Louis Lagrange Solution d'un Problème d'arithmétique le texte original est : Leonhard Euler et Joseph-Louis Lagrange Eléments d'algèbre Lyon, Bruyset et Paris, Desaint 1774
↑ B. L. van der Waerden Pell's Equation in Greek and Hindu Mathematics Russ. Math Surveys 1976 31 (5) pp 210-225
↑ Bhāskara II Bijaganita 1150 cf le 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)
↑ Voir à ce sujet le site Pierre de Fermat par la ville Beaumont de Lomagne

[modifier] Liens externes

(fr) Développement d'un réel en fractions continues par M. Couchouron pour les développements périodiques et l'équation de Pell-Fermat
(fr) Histoire de fractions continues par C. Bresinski de l'Université des Sciences et Technologies de Lille
(fr) Joseph-Louis Lagrange Solution d'un Problème d'arithmétique : La solution originale de Lagrange sur la représentation d'un élément d'un corps quadratique par une fraction continue.

[modifier] Bibliographie

Pierre Samuel, Théorie algébrique des nombres [détail des éditions]
Alain Faisant, L'équation diophantienne du second degré, Hermann, 1991
(en) A. Baker A Concise Introduction to the Theory of Numbers Cambridge University Press 1985 (ISBN 0521286549)
Marc Guinot, Arithmétique pour amateurs. Vol. 4 : Lagrange et Legendre Aléas, 1996 (ISBN 2-908016-71-0)
(en) G. H. Hardy et E. M. Wright An Introduction to the Theory of Numbers [détail des éditions]

Portail des mathématiques

[0] G Ifrah Histoire universelle des chiffres: L'intelligence des hommes racontée par les nombres et le calcul Robert Laffont 1994 (ISBN 2221901002)

[1] M. T. Rivolo A. Simi The computation of square and cube roots in Italy from Fibonacci to Bombelli (Italian) Arch. Hist. Exact Sci. 52 (2) 1998 pp 161-193

[2] S. Maracchia Estrazione di radice quadrata secondo Cataldi Archimede 28 (2) 1976 pp 124-127

[3] John Wallis Commercium epistolicum de quæstionibus quibusdam mathematicis nuper habitum Oxonii : Excudebat A. Lichfield, Impensis Tho. Robinson 1658

[Euler-4] Leonhard Euler, Introductio in analysin infinitorum. Vol. I, Chapter 18 1748

[5] Ces résultats sont publiés dans : Leonhard Euler et Joseph-Louis Lagrange Eléments d'algèbre Lyon, Bruyset et Paris, Desaint 1774. Le livre contient une centaine de pages nommées Additions par Lagrange.

[6] Evariste Galois annonce le résultat suivant « Si une des racines d’une équation de degré quelconque est une fraction immédiatement périodique, cette équation aura nécessairement une autre racine également périodique que l’on obtiendra en divisant l’unité négative par cette même fraction continue périodique écrite dans un ordre inverse. » extrait de : Histoire de fractions continues par C. Bresinski de l'Université des Sciences et Technologies de Lille p 63

[Couchouron-7] Les démonstrations proposées ici s'inspirent du document : Développement d'un réel en fractions continues par M. Couchouron pour les développements périodiques et l'équation de Pell-Fermat

[8] Elle est accessible sur le net : Joseph-Louis Lagrange Solution d'un Problème d'arithmétique le texte original est : Leonhard Euler et Joseph-Louis Lagrange Eléments d'algèbre Lyon, Bruyset et Paris, Desaint 1774

[9] B. L. van der Waerden Pell's Equation in Greek and Hindu Mathematics Russ. Math Surveys 1976 31 (5) pp 210-225

[10] Bhāskara II Bijaganita 1150 cf le site de l'Université de St Andrew Pell's equation

[11] 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)

[12] Voir à ce sujet le site Pierre de Fermat par la ville Beaumont de Lomagne

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

Fraction continue d'un nombre quadratique

Un article de Wikipédia, l'encyclopédie libre.

Sommaire

[modifier] Préambule

[modifier] Introduction par l'exemple

[modifier] Eléments d'histoire

[modifier] Première propriété

[modifier] Période

[modifier] Palindrome

[modifier] Equation de Pell-Fermat

[modifier] Structure de la solution

[modifier] Groupe des unités

[modifier] Extraction d'une racine carrée

[modifier] Première méthode

[modifier] Accélération violente

[modifier] Un exemple historique de résolution de l'équation de Pell Fermat

[modifier] Voir aussi

[modifier] Notes

[modifier] Liens externes

[modifier] Bibliographie

Affichages

Outils personnels

Rechercher

Navigation

Contribuer

Boîte à outils

Autres langues