Association pour l'Innovation Didactique
Centre de Recherche et d'Expérimentation pour l'Enseignement des Mathématiques

 Deux ponts entre le discret et le continu:
- différences finies, Euclide et fractions continuées;
- Suite de Stern-Brocot et fractions continuées.


Il existe trois variantes d'un même algorithme géométrique, que les Grecs désignaient par anthyphérèse, qui consiste à découper un rectangle en pièces carrées aussi grandes que possible. Ces variantes sont communément désignées par algorithme des "différences finies", algorithme "d'Euclide"  et algorithme des "fractions continuées" (ou "fractions continues").

1 - L'algorithme des différences finies:
Cet algorithme est enseigné en classe de troisième pour déterminer le plus grand diviseur commun de deux nombres entiers a et b. Il est entièrement construit sur le simple lemme: si d divise a et b, alors il divise a-b.
Par exemple, si a=3471 et b=1239, on peut présenter sous forme de tableau les calculs à réaliser:
on initialise les suites (ai)  et (bi) avec les deux nombres fournis, puis on pose :

di= ai-bi   ,   ai+1= max(ai,ai-bi) et bi+1= min(ai,ai-bi)
On arrête le processus lorsque  di =0; le plus grand commun diviseur de a et b est la dernière différence non nulle.

i ai bi di test d'arrêt: di = 0 ?
0 3471 1239 2232 d0 >0, on continue
1 2232 1239 993 d1 >0, on continue
2 1239 993 246 d2 >0, on continue
3 993 246 747 d3 >0, on continue
4 747 246 501 d4 >0, on continue
5 501 246 255 d5 >0, on continue
6 255 246 9 d6 >0, on continue
7 246 9 237 d7 >0, on continue
8 237 9 228 d8 >0, on continue
... ... ... ... ... on continue...
32 12 9 3 d32 >0, on continue
33 9 3 6 d33 >0, on continue
34 6 3 3 d34 >0, on continue
35 3 3 0 d35 = 0 : STOP, et PGCD(3471,1239) = d34 = 3.

Figure 1 pour illustrer de manière dynamique l'algorithme des différences finies :

Pour choisir les dimensions entières du rectangle: saisissez à la souris le point M ;
pour dessiner la pièce carrée suivante: touche G ; pour sortir du mode trace: touche Echap

2 - L'algorithme d'Euclide, variante accélérée de l'algorithme des différences finies :

L'algorithme d'Euclide, qui est lui aussi programme du collège, permet d'accélérer la procédure précédente de recherche du PGCD de deux nombres. L'idée est d'éviter les répétitions de différence par une division euclidienne.
Cet algorithme est entièrement construit sur un 
corollaire du lemme précédent : si d divise a et b, alors  il divise a-b, et par récurrence a-nb pour tout entier n, 
en particulier il divise a-qb=r où q est le quotient et r le reste de la division euclidienne de a par b.  
Géométriquement, le nombre d'itérations économisées est directement liée au nombre de répétitions de pièces carrées de même taille.  Le tableau ci-dessous présente la mise en œuvre de l'algorithme d'Euclide pour la recherche de PGCD(3471,1239).
Il s'agit cette fois de faire des divisions euclidiennes ai = bi qi + ri partant de a0=3471 et de b0=1239 , et de poser ensuite a1= b0  et b1= r0 , et par la suite ai+1= bi  et bi+1= ri  tant que  ri n'est pas nul. Le PGCD est le dernier reste non  nul.

i ai bi qi ri test d'arrêt: ri = 0 ?
0 3471 1239 2 993 r0 = 993>0, on continue
1 1239 993 1 246 r1 = 246>0, on continue
2 993 246 4 9 r2 = 9>0, on continue
3 246 9 27 3 r3 = 3>0, on continue
4 9 3 3 0 r4 = 0: STOP, et PGCD(3471,1239) = r3 = 3

On peut de plus remarquer que la traduction algébrique du puzzle de forme rectangulaire et à pièces carrées est :
  a0 b0=Si  qi ci², ce qui donne dans notre exemple:  3471´1239  = 2´1239²+1´993²+4´246²+27´9²+3´3²
On en déduit que l'entier a0´b0 est un nombre entier décomposable en somme de carrés. Le thème de la décomposition de nombres entiers en somme de carrés a suscité des développements arithmétiques parfois ardus ayant un lien très étroit avec la théorie des formes quadratiques.

3 - Les fractions continuées, généralisation aux irrationnels des deux algorithmes précédents: 
Soit x un irrationnel.
L'algorithme des fractions continuées permet de construire une suite de rationnels, dite suite des réduites: 
   - qui converge vers l'irrationnel x plus rapidement que la suite des décimaux obtenus par troncature du développement décimal de x après la nième décimale de x, et, comme chacun sait, les approximations les plus courtes sont les meilleures;
   - qui présente, entre autres intérêts théoriques, celui de ne pas dépendre de la base dans laquelle on travaille.
Le procédé nécessite la construction de deux suites annexes et entremêlées: l'une q, prend ses valeurs dans N* , l'autre, e, prend ses valeurs dans {x}U ] 0 1] - Q.
On pose e(0)= x , puis q(0)=E(x)=partie entière de x, puis on cherche à approcher l'erreur e(1)=x-E(x)=e(0)-q(0).
Cette erreur e(1) est irrationnelle, est strictement supérieure à 0 et est inférieure strictement à l'unité, donc son inverse 1/e(1) est un irrationnel supérieur strictement à l'unité. On pose q(1)= E(1/e(1)), qui est bien dans N* , et la nouvelle erreur irrationnelle à estimer est : e(2)= 1/e(1)-q(1), et ainsi de suite. 
La suite des réduites, dont les premiers termes sont 
, , , , et dont le terme général est 

converge vers x.

La suite q devient plus intelligible lorsque on la relie à (et la relit comme une nouvelle application de) notre algorithme géométrique de partition en carrés d'un rectangle dont la proportion Longueur/largeur est égale à x. Seule la proportion du rectangle est importante: tout rectangle semblable pourrait aussi-bien faire l'affaire, même si dans la pratique on ne prendra que des rectangles homothétiques au rectangle dont les côtés sont parallèles aux axes du repère orthonormé. L'idée des fractions continuées est donc strictement la même que pour l'algorithme des différences finies: découper un rectangle en des pièces carrées en se contraignant à chaque nouveau découpage à obtenir une nouvelle pièce carrée aussi grande que possible, et en évitant de gâcher de la surface en "chutes". Le nombre de grandes pièces carrées est q(1), le nombre de pièces carrées de deuxième grandeur est q(2), etc...On comprend dès lors à quoi correspond les n inversions algébriques de la définition de x(n): ce sont les n "basculements" des rectangles successifs qu'il reste à découper, ou encore les n tailles différentes des pièces carrées utilisées jusqu'à ce point. 
Nous avons découvert cette représentation des fractions continuées avec Mathématique, informatique et enseignement de Jacqueline Zizi. Une belle caractérisation géométrique du nombre d'or    est démontrée par Jean Barbé et Renaud Palisse (bulletin n°408 de l'APMEP, pp. 38 à 42) dans un article intitulé "la quadrature du rectangle": il y a basculement à chaque étape, c'est-à-dire un exemplaire unique de chaque pièce carrée. Autrement dit, le nombre d'or limite l'accélération de l'algorithme des fractions continuées.
Des résultats plus généraux peuvent être établis sur les suites q qui sont périodiques ou périodiques à partir d'un certain rang:
Théorème (Lagrange, 1768). Le développement en fraction continuée d'un irrationnel x est périodique à partir d'un certain rang si et seulement si x est un irrationnel racine d'un polynôme de degré 2 à coefficients entiers (ou rationnel, ce qui revient au même, quitte à multiplier par le PGCD des dénominateurs des coefficients).
On dit qu'un tel x est irrationnel quadratique.
Et :
Théorème : Les réels admettant un développement périodique dont la période commence dès le premier rang sont exactement les irrationnels quadratiques x > 1 dont le conjugué radical est élément de ]-1,0[.
On dit qu'un tel x est irrationnel quadratique réduit.
 

Figure 2 pour illustrer de manière dynamique l'algorithme des fractions continuées:
Vous pouvez redimensionner le rectangle en pilotant à la souris le point I,  puis en appuyant sur la touche I.
Appuyez sur la touche G pour obtenir une nouvelle pièce carrée. Pour sortir du mode trace: touche Echap.
Appuyez sur la touche P pour obtenir un rectangle d'or puis G plusieurs fois pour comprendre que la suite q est constante égale à 1 pour le nombre d'or; touche Echap pour sortir du mode trace.
Pour faire apparaître ou disparaître des instructions relatives au théorème de Lagrange, appuyez sur la touche T;
pour régler la période, appuyez sur la touche Q ou R, puis les flèches du clavier, puis de nouveau Q ou R.
Remarque théorique importante: en pilotant le point I à la souris, on ne fait que des affectations décimales; pour forcer une affectation irrationnelle, double-cliquez sur la figure, pour utiliser l'item Piloter/placer un point par coordonnées: vous saisirez alors les coordonnées souhaitées pour le point I.

Pour se familiariser avec le théorème de Lagrange: 
- période de longueur 1 : si pour x irrationnel q(n) = q(0) pour tout n, alors x=q(0)+1/x, donc   x²-q(0)x-1=0; on retrouve au passage le polynôme associé au nombre d'or si q(0)=1, qui est le plus simple des irrationnels quadratiques réduits.
- période de longueur 2: voir texte de la figure ci-dessus. Au passage, le polynôme est x²-q(1) x -q(1)/q(0)=0, et ce polynôme coïncide avec le précédent lorsque q(1)=q(0).
C'est un bon exercice préparatoire à la compréhension de ces théorèmes que de rechercher le polynôme de degré 2, dont les coefficients sont fonctions de trois paramètres q(0),q(1),et q(2), qui s'annule pour x tel que q(3n)=q(0), q(3n+1)=q(1) et q(3n+2)=q(2) pour tout entier n.
La démonstration des deux théorèmes ci-dessus est présentable à une leçon d'agrégation (cf.par exemple http://www.infty08.net/dudeFraCont.pdf.)
L'interprétation géométrique de l'algorithme des fractions continuées permet de montrer que :
        - la suite xn converge effectivement vers x; plus précisément, la suite x2n croît vers x et la suite x2n+1 décroît vers x;
        -  pour x=b/a rationnel, c'est-à-dire si a et b sont commensurables, l'algorithme s'arrête au bout d'un nombre fini d'itérations: il existe un rang n pour lequel l'erreur e(n)=0. 
La preuve de ces deux résultats est laissée en exercice au lecteur; indication: construire à rebours le puzzle dont on néglige les pièces carrées au delà du n+1ième terme,  et en prenant par exemple 1 pour le côté du carré du nième ordre de grandeur : xn n'est autre que la proportion rationnelle du rectangle obtenu, ou son inverse - nous n'avons pas encore clairement défini si une proportion est le rapport longueur/largeur, mais il y a un lien très simple entre le développement en fractions continuées d'un nombre et de son inverse... On laisse également au lecteur retrouver comment exprimer la nième réduite xn ; indication: aller fouiller dans le texte de la figure ci-dessous. 

Figure 3 pour obtenir la suite des réduites d'un nombre x 

Ci-dessous, vous pouvez obtenir les premiers éléments de la suite des réduites pour x =   (touche P), 
pour x= π (touche 2), pour x= 3471/1239 (touche 3), pour x quelconque (touche X, puis flèches du clavier).
Pour piloter le rang N de la réduite affichée: touche N  ; au delà d'un certain rang, les affichages disparaissent, ou deviennent négatifs; le nombre de chiffres exacts d'un entier que gère Géoplan n'est pas illimité ! Pour voir apparaître le rang limite, au-delà duquel les valeurs de la suite q ne sont plus fiables, appuyez sur la touche T : un tableau de valeurs de la suite Q apparaît; la première valeur dont l'affichage nécessite un exposant marque le rang en deçà duquel les résultats sont fiables.
Remarque théorique importante: en pilotant le nombre x à la souris, on ne fait que des affectations décimales; pour forcer une affectation irrationnelle, double-cliquez sur la figure, pour utiliser l'item Piloter/Affecter une variable numérique libre: vous saisirez alors la valeur souhaitée pour le réel x.

Remarques : 
 - Si a et b ne sont pas commensurables, la traduction du puzzle (infini, voir figure 2) n'est plus arithmétique, mais analytique:      ab = Si  qi ci² (sommation infinie).
  - L'outil matriciel (avec des matrices (2,2)) permet également d'évaluer la suite des réduites; ce même outil matriciel peut également être utile pour comprendre la fin du paragraphe suivant. Voyons de quoi il s'agit.

4 - Fractions continuées et suite de Stern-BrocotL'algorithme des fractions continuées est étroitement lié à une suite de rationnels (xn), dite suite de Stern -Brocot  , 
construite suivant un procédé très simple et astucieux, qui utilise, entre autres choses, le fait que si on se donne deux fractions réduites positives rangées   <   , alors on a l'encadrement  < <  , et la fraction intercalée est aussi sous forme réduite.

Cette suite (xn) construit  directement une bijection entre Q* et N* : Stern, un mathématicien allemand, et Brocot, un horloger français, ont semble-t-il indépendamment publié respectivement en 1858 et 1860  l'algorithme suivant, présentable sous forme d'arbre ou ici de "tableau générationnel". 
La "génération 0" contient les deux bornes de Q*, à savoir 0 et +∞ sous "forme réduite". 
génération G0
                             
G1
 		               x1
 		             
G2
      x2
 		     
      x3
 		     
G3
  x4
 		 
  x5
 		 
  x6
 		 
  x7
 		   
G4
x8
x9
x10
x11
x12
x13
x14
x15
etc... Chacun des 2i-1 nouveaux arrivants xj ( 2i-1 j<2i ) de la génération Gi a pour numérateur la somme des numérateurs de ses deux voisins et pour dénominateur la somme de leurs dénominateurs.
Par exemple, x22=(2+3)/(3+4)=5/7

Ce procédé produit un tableau (ou arbre) de rationnels compris entre 0 et 1 dans la partie gauche et de leurs inverses, compris entre 1 et l'infini, dans la partie droite.  L'algorithme donne sans équivoque un sens au concept de "rationnel suivant", ce qui déjà n'est pas une mince affaire, mais fait encore beaucoup mieux, puisque l'on a les trois 
propriétés
1- Toutes les fractions sont sous forme réduite ; 
2- La suite (xn) ainsi définie ne passe pas deux fois par le même rationnel. 
3- La suite (xn) ainsi définie recouvre entièrement Q* . 

Ces résultats sont démontrés dans Concrete Mathematics, de Graham, Knuth et Patashnik (en anglais).
Ils établissent donc de manière constructive la dénombrabilité de l'ensemble des rationnels.

Il y a un lien très étroit entre la suite de Stern-Brocot et l'algorithme des fractions continuées. En effet, si, partant de x1 , et descendant vers xN, on doit dans l'ordre faire a0 saut(s) vers la droite, puis a1 saut(s) vers la gauche,  puis a2 saut(s) vers la droite, et ainsi de suite jusqu'à a2n+1 saut(s) vers la gauche, alors le développement en fractions continuées de xN est: (a0,a1,a2,...,a2n+1, 1); autrement dit, 
 démonstration là encore dans Concrete Mathematics. 
Par exemple, pour descendre de x1 sur x22 =5/7, on passe par x2 puis x5 puis x11, autrement dit on doit dans l'ordre faire a0=0 saut vers la droite, puis a1 = 1 saut vers la gauche,  puis a2 = 2 sauts vers la droite, puis  a3 = 1 saut vers la gauche, et on peut vérifier que   .
Une curiosité : Euler a prouvé que le nombre e était la limite du cheminement suivant dans l'arbre de Stern-Brocot: D1G0D1G1D1G2D1G3D1G4D1G5D1 ....etc où D1 symbolise un saut vers la droite et Gk k sauts vers la gauche; en fait, G et D peuvent être comprise comme deux matrices (2,2), cf. Concrete Mathematics.