Fraction continue

On commence par rappeler le déroulement de l'algorithme dû à Euclide de recherche du PGCD, en analysant l'exemple des deux nombres entiers 15 625 et 6 842. On procède à une suite de divisions euclidiennes avec reste :

${\displaystyle {\begin{matrix}15\;625&=&2\times &6\;842&+&1\;941,&\\6\;842&=&3\times &1\;941&+&1\;019,&\\1\;941&=&1\times &1\;019&+&922,&\\1\;019&=&1\times &922&+&97,&\\922&=&9\times &97&+&49,&\\97&=&1\times &49&+&48,&\\49&=&1\times &48&+&1.&\end{matrix}}}$

Une autre manière d'interpréter cet algorithme consiste à approcher par étapes le quotient 15 625 / 6 842. La partie entière de ce quotient est 2, ce qui permet d'écrire :

${\displaystyle {\frac {15\;625}{6\;842}}=2+{\frac {1\;941}{6\;842}}.}$

Que peut-on dire de la fraction 1 941 /6 842, à part qu'elle est plus petite que 1 ? Elle est comprise entre 1/4 et 1/3, son inverse, 6 842 / 1 941, possède comme partie entière : 3 ; et plus précisément, si l'on utilise les résultats de la deuxième division euclidienne :

${\displaystyle {\frac {1\;941}{6\;842}}={\cfrac {1}{3+{\cfrac {1\;019}{1\;941}}}}.}$

Ainsi de proche en proche :

${\displaystyle {\cfrac {15\;625}{6\;842}}=2+{\cfrac {1}{3+{\frac {1\;019}{1\;941}}}}=2+{\cfrac {1}{3+{\cfrac {1}{1+{\cfrac {922}{1\;019}}}}}}=\dots =2+{\cfrac {1}{3+{\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{9+{\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{48}}}}}}}}}}}}}}}$

qui est bien une fraction continue. On utilise parfois la notation suivante, plus commode :

${\displaystyle {\frac {15\;625}{6\;842}}=[2,3,1,1,9,1,1,48].}$

On peut comparer 15 625 / 6 842 à ses réduites obtenues en tronquant successivement le nombre d'étages de la fraction continue. Le tableau suivant donne les troncatures en notation fractionnelle puis décimale, et la différence entre la réduite et le nombre 15 625 / 6 842.

La suite des erreurs est décroissante en valeur absolue et de signes alternés.

Soit r = p/q un nombre rationnel (avec p et q entiers et q > 0). On cherche pour r un développement fini en fraction continue, c'est-à-dire une écriture de r sous la forme [a₀, … , a_n] avec n entier naturel, a₀ entier relatif et a₁, … , a_n entiers > 0. On applique pour cela l'algorithme d'Euclide :

On pose p₀ = p, p₁ = q, et l'on construit les entiers a₀ et p₂ par division euclidienne :

${\displaystyle p_{0}=a_{0}p_{1}+p_{2},\quad a_{0}\in \mathbb {Z} ,0\leq p_{2}<p_{1}.}$

Puis, tant que p_j n'est pas nul, on définit les entiers a_j–1 et p_j+1 par :

${\displaystyle p_{j-1}=a_{j-1}p_{j}+p_{j+1},}$

avec a_j–1 entier au moins égal à 1 (pour j > 1) et 0 ≤ p_j+1 < p_j. L'algorithme d'Euclide s'arrête. On note n le plus grand entier pour lequel p_n+1 n'est pas nul. On sait donc que p_n/p_n+1 est égal à l'entier a_n. On a alors :

${\displaystyle {\frac {p_{0}}{p_{1}}}=[a_{0},a_{1},\dots ,a_{n}].}$

En effet :

${\displaystyle p_{0}/p_{1}=[a_{0},p_{1}/p_{2}]=[a_{0},a_{1},p_{2}/p_{3}]=\dots =[a_{0},a_{1},\dots ,a_{n}],}$

ou encore :

${\displaystyle p_{n}/p_{n+1}=[a_{n}]{\text{ et pour }}j=n-1,n-2,\ldots ,0~:\quad p_{j}/p_{j+1}=[a_{j},p_{j+1}/p_{j+2}]=[a_{j},a_{j+1},\dots ,a_{n}].}$

Représentation géométrique[24] —

Un pavage d'un rectangle de longueur 30 et de largeur 13 permet de déterminer l'expression de 30/13 en fraction continue : 30/13=[2, 3, 4].

L'algorithme d'Euclide permet de calculer une fraction continue dans le cas des nombres rationnels. Cet algorithme admet dans ce cadre une interprétation géométrique. Soit r = p/q un nombre rationnel, on considère un rectangle de longueur p et de largeur q, et on le pave par des carrés de côté q.

Si r est un entier, le pavage comporte exactement r carrés. Sinon, soit a₀ le nombre de carrés insérés dans le rectangle, ou encore, le premier terme de la fraction continue. Il reste une bande non pavée de dimension q × b₁ avec b₁ égal à p – a₀q ; on pave cette bande avec des carrés de dimension maximale, c'est-à-dire de côté b₁. Le nombre de carrés est égal au deuxième terme a₁ de la fraction continue. En réitérant la méthode, on obtient l'intégralité des coefficients a_p.

Dans l'image ci-contre, on pave le rectangle 30 × 13 par deux carrés de côtés 13. Il reste une bande de longueur 13 et de largeur 4. En termes de fraction continue, on obtient l'égalité :

${\displaystyle {\frac {30}{13}}=2+{\frac {4}{13}}={\color {Red}2}+{\cfrac {1}{\left({\cfrac {13}{4}}\right)}}}$.

La même démarche s'applique pour déterminer un rationnel connaissant sa fraction continue. [1, 1, 2, 3] = 17/10

Ensuite, on remarque qu'il est possible de remplir la bande restante de 3 carrés de côté 4 et il reste une bande de longueur 4 et de largeur 1, ce qui permet de terminer le calcul de la fraction continue :

${\displaystyle 13=3\times 4+1\;\Rightarrow \;{\frac {30}{13}}={\color {Red}2}+{\cfrac {1}{\left({\cfrac {3\times 4+1}{4}}\right)}}={\color {Red}2}+{\cfrac {1}{{\color {Red}3}+{\cfrac {1}{\color {Red}4}}}}=[2,3,4]}$.

La technique du pavage conduit à une fraction continue infinie si la longueur et la largeur du rectangle sont incommensurables.

La même construction permet de trouver le rationnel dont on connait le développement en fraction continue. Dans l'image de gauche on peut retrouver le rationnel dont le développement est [1, 1, 2, 3]. Le dernier coefficient est égal à 3, on trouve donc 3 petits carrés de côté 1, qui donnent la taille du carré suivant (3). L'avant dernier coefficient 2 indique qu'il existe deux carrés moyens de côté 3. Ces deux côtés et le petit carré donnent la taille du carré plus grand (7). Le coefficient associé est égal à 1, il n'en n'existe donc qu'un unique de cette nature. Le carré plus grand (7) et le carré moyen (3) donnent le côté du dernier carré (10). Les deux derniers carrés donnent la longueur totale du rectangle (17). La fraction recherchée est égale à 17/10.

Le processus s'arrête car p et q sont commensurables c'est-à-dire qu'il existe une longueur l et deux entiers a et b tels que p = la et q = lb.

Considérons maintenant un rectangle de longueur L et de largeur l. Si le quotient L/l n'est pas rationnel, c'est-à-dire si les longueurs L et l sont incommensurables, le processus ne s'arrête pas.

Tel est le cas pour la figure de droite représentant un rectangle d'or, c'est-à-dire un rectangle dont le rapport de la longueur sur la largeur est égal à φ le nombre d'or. On ne peut placer qu'un carré dans chaque bande ce qui amène à la représentation : ${\displaystyle \varphi =[1,1,1,\cdots ]}$.

La suite des numérateurs et celle des dénominateurs sont de Fibonacci.

On a donc montré que pour tout rationnel r, l'algorithme d'Euclide fournit un développement fini en fraction continue de r (réciproquement, tout nombre qui possède un développement fini en fraction continue est évidemment rationnel). Le développement [a₀, … , a_n] obtenu ainsi a la particularité que si n est non nul, alors a_n > 1. On en déduit un second développement : r = [a₀, … , a_n – 1, 1]. Ce sont les deux seuls[25]^,[26].

Quand on adjoint, au calcul des a_j de ce développement, le calcul des numérateurs h_j et dénominateurs k_j des différentes réduites :

${\displaystyle {\frac {h_{0}}{k_{0}}}=[a_{0}]={\frac {a_{0}}{1}},\quad {\frac {h_{1}}{k_{1}}}=[a_{0},a_{1}]=a_{0}+{\frac {1}{a_{1}}}={\frac {a_{0}a_{1}+1}{a_{1}}},\quad \ldots }$

cet algorithme d'Euclide devient l'algorithme d'Euclide étendu[27]^{[source détournée]}. Plus précisément, la suite des couples d'entiers (u_i, v_i), fournie par l'algorithme étendu appliqué à (p, q), coïncide avec la suite des (k_j, h_j), aux signes près et à un décalage près des indices : k_j = (–1)^ju_j+2 et h_j = (–1)^j+1v_j+2. Pour tout j, les entiers k_j et h_j sont donc premiers entre eux et p_j+1 = (–1)^j(qh_j–1 – pk_j–1). En particulier : la dernière réduite, h_n/k_n, est la fraction p/q mise sous forme irréductible et l'avant-dernière correspond à la solution particulière de l'identité de Bézout fournie par l'algorithme d'Euclide étendu : PGCD(p, q) = p_n+1 = (–1)ⁿ(qh_n–1 – pk_n–1).

Démonstration

D'après le § « L'algorithme » de l'article sur l'algorithme d'Euclide étendu, les (u_i, v_i) sont définis par la relation de récurrence

${\displaystyle u_{i+1}=-a_{i-1}u_{i}+u_{i-1},\quad v_{i+1}=-a_{i-1}v_{i}+v_{i-1}}$

et l'initialisation

${\displaystyle u_{0}=1,\quad u_{1}=0,\quad v_{0}=0,\quad v_{1}=1.}$

D'après le § « Réduites d'une fraction continue » ci-dessous, les (k_j, h_j) suivent la relation de récurrence

${\displaystyle k_{j}=a_{j}k_{j-1}+k_{j-2},\quad h_{j}=a_{j}h_{j-1}+h_{j-2},}$

même en leur affectant les valeurs supplémentaires

${\displaystyle k_{-2}=1,\quad k_{-1}=0,\quad h_{-2}=0,\quad h_{-1}=1.}$

Le lien annoncé entre ces deux suites de couples d'entiers s'en déduit, par une récurrence d'ordre 2.

Une remarque permet de généraliser la méthode précédente à un réel quelconque. Pour l'illustrer, appliquons-la sur le nombre π. La première étape, dans le cas d'un rationnel, était le calcul du quotient de la division euclidienne du numérateur par le dénominateur, ce qui n'a plus de sens pour un réel, en revanche le résultat était égal à la partie entière du rationnel, or la partie entière d'un réel a un sens. La partie fractionnaire, nécessairement plus petite que 1, était inversée, ce qui est encore possible ici. On obtient :

${\displaystyle \pi =3+{\cfrac {1}{\left({\cfrac {1}{\pi -3}}\right)}}\approx 3+{\frac {1}{7,062\;513\;305\;931}}}$.

Comme π – 3 est plus petit que 1 (c'est une partie fractionnaire) son inverse est plus grand que 1, et n'est pas entier puisque π est irrationnel. On peut donc lui appliquer la même démarche :

${\displaystyle {\frac {1}{\pi -3}}\approx 7+0,062\;513\;305\;931\approx 7+{\frac {1}{15,996\;594\;41}}\quad {\text{et}}\quad \pi \approx 3+{\cfrac {1}{7+{\cfrac {1}{15,996\;594\;41}}}}.}$

La nouvelle valeur, approximativement égale à 15,997, est encore un irrationnel strictement supérieur à 1, d'où la possibilité d'une nouvelle étape, puis d'une nouvelle :

${\displaystyle \pi \approx 3+{\cfrac {1}{7+{\cfrac {1}{15+{\cfrac {1}{1+0,003\;417}}}}}}\approx 3+{\cfrac {1}{7+{\cfrac {1}{15+{\cfrac {1}{1+{\cfrac {1}{292+0,6}}}}}}}}.}$

Puisque que π est irrationnel, le processus ne s'arrête jamais (en imaginant que le calcul est réalisé avec une infinité de décimales). On obtient comme suite de fractions 3 puis 22/7 ≈ 3,1428 puis 333/106 ≈ 3,14150 puis 355/113 ≈ 3,1415929 et enfin 103 993 / 33 102, proche de π avec une précision meilleure que le milliardième. Une fois encore, la suite des erreurs est décroissante en valeur absolue et de signes alternés.

• Nous appellerons fraction continue ou fraction continue simple[note 4] toute suite non vide (a_p) dont le premier terme a₀ est un entier relatif et tous les termes suivants sont des entiers strictement positifs.^{[réf. souhaitée]}
• L'ensemble de ses indices est soit de la forme {0, 1, … , n} pour un certain entier naturel n s'il s'agit d'une suite finie, soit égal à ℕ pour une suite infinie.
• Sa réduite d'indice p est le rationnel [a₀, a₁, … , a_p], défini par${\displaystyle [a_{0}]=a_{0},\quad [a_{0},a_{1}]=a_{0}+{\frac {1}{a_{1}}},\quad \dots [a_{0},\dots ,a_{p}]=a_{0}+{\frac {1}{[a_{1},\dots ,a_{p}]}}.}$

Soit (a_p) une fraction continue. On lui associe deux suites d'entiers (h_p) et (k_p), définies par récurrence par :

${\displaystyle {\begin{aligned}h_{-2}=0,\quad &h_{-1}=1,\quad &h_{p}=a_{p}h_{p-1}+h_{p-2}\\k_{-2}=1,\quad &k_{-1}=0,\quad &k_{p}=a_{p}k_{p-1}+k_{p-2}.\end{aligned}}}$

Alors, pour tout indice p de la fraction continue :

${\displaystyle {\begin{matrix}[a_{0},a_{1},\ldots ,a_{p}]={\frac {h_{p}}{k_{p}}}&\quad &(1)\\a_{p}=-{\frac {h_{p}k_{p-2}-h_{p-2}k_{p}}{h_{p}k_{p-1}-h_{p-1}k_{p}}}&&(2)\\h_{p-1}k_{p}-h_{p}k_{p-1}=(-1)^{p}.&&(3)\end{matrix}}}$

La propriété (3) montre, par application du théorème de Bézout, que les entiers h_p et k_p sont premiers entre eux.

Ces trois propriétés se démontrent directement[28] mais sont aussi des cas particuliers de celles des fractions continues généralisées, démontrées dans l'article correspondant. On y donne également une interprétation matricielle de la définition des h_p et k_p, dont résulte immédiatement, par transposition, une propriété duale de (1)[29] :

${\displaystyle [a_{p},a_{p-1},\ldots ,a_{0}]={\frac {h_{p}}{h_{p-1}}}{\text{ (si }}a_{0}>0{\text{) et }}[a_{p},a_{p-1},\ldots ,a_{1}]={\frac {k_{p}}{k_{p-1}}}{\text{ (si }}p>0{\text{).}}}$

Dans l'algorithme d'Euclide développé précédemment, l'entier a_j est le quotient de p_j dans la division euclidienne par p_j+1. C'est donc la partie entière du réel x_j égal à p_j/p_j+1. La partie fractionnaire x_j – a_j de x_j est p_j+2/p_j+1, inverse du réel x_j+1.

On peut alors définir un développement en fraction continue pour tout réel x. Le symbole ⌊s⌋ désigne la partie entière du nombre s. On pose :

${\displaystyle x_{0}=x,}$

ainsi que la définition récurrente : tant que x_j n'est pas entier,

${\displaystyle a_{j}=\lfloor x_{j}\rfloor ,\quad x_{j}=a_{j}+{\frac {1}{x_{j+1}}}.}$

Si x est rationnel, comme on l'a vu plus haut, il existe un n tel que x_n soit entier : on pose a_n = x_n, l'algorithme s'arrête, et les deux suites (a_j) et (x_j) sont finies. Si x est irrationnel, l'algorithme ne s'arrête jamais et les deux suites sont infinies.

• La suite (a_p) est appelée la fraction continue du réel x.
• Le réel x_p (strictement supérieur à 1 si p > 0) est appelé le quotient complet de x d'indice p.
• Sa partie entière a_p est le quotient incomplet de x d'indice p.

On peut formaliser de manière plus informatique cet algorithme :

• Donnée : un nombre x réel.
• Initialisation : on assigne la valeur x à la variable X. La suite a est vide.
• Boucle : On assigne à la variable A la partie entière de X, on concatène cette valeur à la suite a. Si X est entier, l'algorithme s'arrête. Si X n'est pas entier, on assigne à X la valeur de 1 /(X – A) et on recommence au début de la boucle.

Ou encore :

• si x est entier, son développement est (x) ;
• sinon, soit a₀ sa partie entière ; le développement de x est : a₀, suivi du développement de 1/(x – a₀).

Si x est irrationnel, deux notations sont fréquemment utilisées dans ce contexte :

${\displaystyle x=a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{\cdots }}}}}}=[a_{0},a_{1},a_{2},\cdots ].}$

Elles seront légitimées plus loin : on verra entre autres que la suite des réduites converge vers x.

Soient x un réel, (a_p) sa fraction continue, (h_p) et (k_p) les suites des numérateurs et dénominateurs des réduites associées à cette fraction continue, et (x_p) la suite des quotients complets de x.

Pour tout indice p, on dispose de l'égalité :

${\displaystyle x=[a_{0},a_{1},\dots ,a_{p-1},x_{p}].}$

Or la démonstration des propriétés (1) et (2) ci-dessus des réduites d'une fraction continue reste valide si l'entier a_p est remplacé par le réel x_p. On obtient donc, respectivement :

${\displaystyle {\begin{matrix}x={\frac {x_{p}h_{p-1}+h_{p-2}}{x_{p}k_{p-1}+k_{p-2}}}&\quad &(1')\\x_{p}=-{\frac {xk_{p-2}-h_{p-2}}{xk_{p-1}-h_{p-1}}}.&&(2')\end{matrix}}}$

La propriété (2’) :

• permet de calculer l'entier a_p (partie entière de x_p) en utilisant x comme seul réel, sans utiliser la suite de réels (x_j), qui peut accumuler à chaque étape des imprécisions si l'algorithme est utilisé sur l'outil informatique et conduire ainsi à des valeurs erronées à partir d'un certain rang ;
• montre que la suite des réels |k_px – h_p| est strictement décroissante.

La différence de deux réduites successives d'une fraction continue infinie s'écrit ${\displaystyle {\frac {h_{p+1}}{k_{p+1}}}-{\frac {h_{p}}{k_{p}}}={\frac {(-1)^{p}}{k_{p}k_{p+1}}}}$ (voir supra), ce qui constitue le point de départ du théorème ci-dessous.

Christian Huygens construit un automate planétaire pour déterminer les positions relatives des corps célestes du système solaire.

Christian Huygens souhaite construire, à l'aide d'un mécanisme de type horlogerie, un automate représentant le mouvement des planètes autour du soleil : « Ayant trouuè et fait executer depuis peu une machine automate qui represente les mouvements des Planetes dont la construction est d'une facon particuliere et assez simple a raison de son effect, au reste d'une grande utlitè a ceux qui estudient ou observent le cours des astres[31]. » La difficulté à laquelle il est confronté est liée au rapport de la durée d'une année terrestre et de celle de Saturne. En un an, la Terre tourne de 359° 45′ 40″ 30‴ et Saturne de 12° 13′ 34″ 18‴. Le rapport est égal à 77 708 431/2 640 858. Combien faut-il de dents sur les deux engrenages supportant respectivement la Terre et Saturne ?

Huygens sait que les fractions continues offrent le meilleur compromis, ce qu'il exprime ainsi : « Or, lorsqu'on néglige à partir d'une fraction quelconque les derniers termes de la série et celles qui la suivent, et qu'on réduit les autres plus le nombre entier à un commun dénominateur, le rapport de ce dernier au numérateur sera voisin de celui du plus petit nombre donné au plus grand ; et la différence sera si faible qu'il serait impossible d'obtenir un meilleur accord avec des nombres plus petits[32]. »

Un calcul en fraction continue montre que :

${\displaystyle {\frac {77\,708\,431}{2\,640\,858}}=[29,2,2,1,5,1,4,1,1,2,1,6,1,10,2,2,3]}$.

On obtient la suite de fractions : 29/1, 59/2, 147/5, 206/7, 1 177/40 ... Les deux premières solutions ne sont guère précises, dans le premier cas, à la fin d'une rotation de Saturne, la position de la terre est fausse à près d'un demi-tour, dans l'autre cas l'erreur dépasse 4°. La cinquième est techniquement difficile, elle demande la fabrication d'une roue à plus de 1 000 dents ou plusieurs roues. La quatrième offre une précision proche de 3/1 000. C'est celle que choisit Huygens.

Si la terre fait cent tours complets, sur l'automate planétaire Saturne en fait 700/206, soit trois tours et un angle de 143° 18′. Dans la réalité, Saturne a tourné de 143° 26′. Soit une erreur de 8 minutes d'angle, largement inférieure aux imprécisions mécaniques de l'horloge. Un calcul analogue montre que la fraction 147/5 donne, dans le même contexte, une erreur supérieure à un degré, pour une mise en œuvre d'une difficulté technique comparable.

De même, Euler a développé la fonction exponentielle en une fraction continue de fonctions d'une forme appropriée : ${\displaystyle {\rm {e}}^{1/s}=[1,s-1,1,1,3s-1,1,1,5s-1,1,1,7s-1,\ldots ],}$ de manière à obtenir la fraction continue de e :

${\displaystyle {\rm {e}}=[2,1,2,1,1,4,1,1,6,1,1,8,1,1,10,1,\ldots ].}$

• (en) Jonathan Borwein, Alf van der Poorten, Jeffrey Shallit et Wadim Zudilin (de), Neverending Fractions, Cambridge University Press, 2014
• (en) C. Brezinski, History of Continued Fractions and Padé Approximants, Berlin, Springer-Verlag, 1991 (DOI 10.1007/978-3-642-58169-4, lire en ligne)
• Bulletin de l'APMEP n^o 450
• Roger Descombes, Éléments de théorie des nombres, PUF, 1986
• Daniel Duverney, Théorie des nombres, Dunod, 2007
• G. H. Hardy et E. M. Wright (trad. de l'anglais par F. Sauvageot), Introduction à la théorie des nombres [« An Introduction to the Theory of Numbers »], Vuibert-Springer, 2007
• (en) Doug Hensley, Continued Fractions, World Scientific, 2006 (lire en ligne)
• Jean Trignan, Introduction aux problèmes d'approximation : fractions continues, différences finies, Éd. du Choix, 1994 (ISBN 978-2-909028-16-3)
• Georges Valiron, Théorie des fonctions, Masson, Paris, 1966, Notions sur les fractions continues arithmétiques p. 17-24

• Approximant de Padé
• Factorisation par fraction continue
• Fraction continue d'un irrationnel quadratique
• Fraction continue généralisée
• Fraction continue et approximation diophantienne
• Formule de fraction continue d'Euler
• Développement en série de Engel
• Mesure d'irrationalité
• Quotients partiels restreints (en)
• Concernant la convergence :
  • Constante de Khintchine
  • Constante de Lévy
  • Problème de convergence
  • Théorème de Lochs
  • Théorème de Śleszyński-Pringsheim

• Notices d'autorité :

  • Bibliothèque du Congrès
  • Bibliothèque nationale de la Diète
  • Bibliothèque nationale d’Israël
  • Bibliothèque nationale tchèque
• Notices dans des dictionnaires ou encyclopédies généralistes :

  • Encyclopædia Britannica
  • Gran Enciclopèdia Catalana
• (en) Gilles Lachaud, « Continued fractions, binary quadratic forms, quadratic fields, and zeta functions », dans Algebra and topology 1988, Taejon, Korea Inst. Tech., 1988 (lire en ligne), p. 1-56
• (en) Un calculateur en ligne de fraction continue
• (de) Une illustration graphique de l'algorithme d'Euclide itéré pour le calcul d'une fraction continue (avec Cinderella).
• Charles Walter, « L1 Maths et L1 Info, Option Arithmétique, chap. 2 : Fractions continues », sur Université de Nice, 2011

• Arithmétique et théorie des nombres