Transformation homographique appliquée
à un développement en fraction continue fini ou infini

par

SALAH LABHALLA (Marrakech) et HENRI LOMBARDI (Besançon)

**Introduction.** Soit $m$ un entier positif et $x$ un nombre rationnel. L'algorithme de Mendès France ([Men1]) permet de calculer le développement en fraction continue de $mx$ à partir de celui de $x$ sans passer par le calcul du rationnel $x$. Cet algorithme permet en conséquence d'obtenir des informations de nature théorique sur la manière dont se comporte "la multiplication par $m$" lorsqu'elle est vue comme portant directement sur les développements en fraction continue. Dans [Men1] par exemple, Mendès France obtient la borne suivante. Notons $\theta(m)$ la longueur maximum des développements en fraction continue "pairs" pour les rationnels de dénominateur $m$, et notons $\text{lf}(x)$ la longueur du développement en fraction continue de $x$ (pour $x$ rationnel). Alors, si $x$ est un rationnel positif, on a $\text{lf}(mx) \le (\text{lf}(x) - 1)\theta(m) + 1$.

Dans la suite, nous abrégeons “développement en fraction continue” par dfc.

Des majorations analogues mais plus compliquées sont obtenues dans
[Men2] pour $\text{lf}((ax+b)/(cx+d))$ lorsque $a, b, c, d$ sont des entiers premiers
entre eux dans leur ensemble.

Dans l'article présent, nous constatons que l'algorithm de [Men1] calcule
en fait le dfc de $(ax + b)/d$ pour $x$ rationnel et $a, b, d$ entiers avec $ad > 0$.
Ceci nous permet de simplifier l'algorithm donné dans [Men2] et nous en
déduisons une meilleure majoration pour $\text{lf}((ax + b)/(cx + d))$. Si on note
$\text{lfp}(x)$ et $\text{lfi}(x)$ les longueurs des développements en fraction continue pair
et impair de $x$ on a précisément le résultat suivant.

THÉORÈME 2. Soit un rationnel $x$ et des entiers $a, b, c > 0$ et $d$. On suppose $a, b, c$ et $d$ premiers entre eux dans leur ensemble et le déterminant $\Delta = ad - bc \neq 0$. Alors, si $\Delta > 0$, on a

<footnote n="1991">1991 Mathematics Subject Classification: Primary 11A55.</footnote>
$$ (\mathbf{lf}(x) - \mathbf{lf}_i(-d/c) - 2)/\theta(\Delta) \le \mathbf{lf}\left(\frac{ax+b}{cx+d}\right) \le \mathbf{lf}(x)\theta(\Delta) + \mathbf{lf}_i(a/c) + 2, \\ \text{et si } \Delta < 0, \text{ on a} $$

$$ (\mathbf{lf}(x) - \mathbf{lf}_p(-d/c) - 2)/\theta(\Delta) \le \mathbf{lf}\left(\frac{ax+b}{cx+d}\right) \le \mathbf{lf}(x)\theta(\Delta) + \mathbf{lf}_p(a/c) + 2. $$

Ces résultats restent valables pour le cas $c = 0$ si nous prenons conventionnellement $\mathbf{lf}_i(\infty) = -2$ et $\mathbf{lf}_p(\infty) = -1$.

Enfin nous montrons (théorème 3) que les $k$ premiers termes du développement en fraction continue de $(ax + b)/(cx + d)$ ne dépendent que des $k\theta(ad - bc) + \mathbf{lf}(-d/c) + 3$ premiers termes du développement en fraction continue de $x$.

Ce résultat de continuité uniforme “lipschitzienne”, bien que découlant intuitivement du théorème 2, semble a priori assez surprenant, dans la mesure où il s’agit d’un résultat de continuité uniforme et non de continuité en tout point. Cela permet aussi de montrer que, lorsque $x$ est irrationnel, le développement en fraction continue de $(ax + b)/(cx + d)$ peut être calculé par “le même algorithme”.

**1. Rappels sur les fractions continues.** Soit $a_0$ un entier et $(a_1, a_2, \dots, a_n)$ une suite finie d’entiers strictement positifs. Nous notons par $\lfloor a_0, a_1, \dots, a_n \rfloor$ la fraction continue finie

$$ a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \ddots + \frac{1}{a_n}}} $$

Dans le cas d’une suite infinie, nous notons également $\lfloor a_0, a_1, \dots, a_n, \dots \rfloor$ la fraction continue infinie.

Alors chaque nombre irrationnel $x$ a une unique représentation en fraction continue infinie et chaque nombre rationnel $x$ a une unique représentation en fraction continue finie

$$ \lfloor a_0, a_1, \dots, a_n \rfloor \quad \text{avec } a_n > 1 \text{ si } n \ge 1. $$

En outre $\lfloor a_0, a_1, \dots, a_n \rfloor = \lfloor a_0, a_1, \dots, a_{n-1}, 1 \rfloor$ (avec $n \ge 0$). On en déduit que tout rationnel $x$ a une unique représentation en fraction continue finie $\lfloor a_0, a_1, \dots, a_n \rfloor$ avec $n$ pair. Il existe également un unique développement en fraction continue se terminant avec $n$ impair.

**Terminologie et notation.** Dans la suite, nous dirons dfc pair (resp. dfc impair) pour un dfc se terminant sur un indice pair (resp. impair). Pour un rationnel $x$ on notera
• **lf**(*x*) la longueur du dfc de *x*,

• **lfp**(*x*) la longueur (impaire) du dfc pair de *x*,

• **lfi**(*x*) la longueur (paire) du dfc impair de *x*;

pour un entier positif *m* on note

• θ(m) la longueur maximum des développements en fraction continue "pairs" pour les rationnels de dénominateur m, c'est-à-dire encore le maximum des lfp(i/m) pour i = 0, ..., m - 1. Enfin par convention θ(-m) = θ(m). Notez que θ(±1) = 1.

Les fonctions ψ(x) et ψ*(x) dans [Men1] sont respectivement égales à
lf(x) - 1 et lfp(x) - 1. A un développement en fraction continue ordinaire
/a₀, a₁, ..., aₙ/ est associée une fonction homographique z ↦→ /a₀, a₁, ..., 
aₙ, z/, qui est la composée des fonctions z ↦→ /aᵢ, z/ = aᵢ + 1/z. Ceci permet
d'attribuer une signification claire à l'écriture /a₀, a₁, ..., aₙ, z/ pour n'im-
porte quelles valeurs réelles des aᵢ, avec z et /a₀, a₁, ..., aₙ, z/ dans R∪{∞},
et donc aussi à /a₀, a₁, ..., aₙ/ = /a₀, a₁, ..., aₙ, ∞/.

Terminologie. Si un rationnel $x$ est égal à un développement $/a_0, a_1, \dots, a_n/$ avec des entiers $a_i$ qui ne respectent pas la condition d’être strictement positifs pour tous les $i > 1$, on dira que $/a_0, a_1, \dots, a_n/$ est un faux dfc de $x$. Un rationnel $x$ a donc deux vrais dfc (son dfc pair et son dfc impair) et … beaucoup de faux dfc.

Notez qu'on a pour tout $k < n$,

$/a_0, a_1, \dots, a_k, a_{k+1}, \dots, a_n/ = /a_0, a_1, \dots, a_k, (/a_{k+1}, \dots, a_n)/,$

ce qui permet d'attribuer raisonnablement la valeur $\infty$ au dfc vide //.

Lorsqu’on représente les fonctions homographiques par des matrices
(définies à un scalaire multiplicatif près), la fonction $z \mapsto /a_i, z/$ correspond à la matrice $\begin{pmatrix} a_i \\ 1 \end{pmatrix}_{0}$ et la fonction $z \mapsto /a_0, a_1, \dots, a_n, z/$ correspond au produit des matrices

$$
\begin{pmatrix} a_0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} a_1 & 1 \\ 1 & 0 \end{pmatrix} \cdots \begin{pmatrix} a_n & 1 \\ 1 & 0 \end{pmatrix}.
$$

Notez qu’un produit vide de matrices est raisonnablement égal à la matrice identité, qui correspond à la fonction homographique $x \mapsto x$ laquelle prend bien la valeur $\infty$ en $\infty$.

*Terminologie.* Si on considère un développement en fraction continue
/*a*_₀, *a*_₁, ..., *a*_n/ (vrai ou faux) formé d'entiers, et si on a

$$
\begin{pmatrix} u & u' \\ v & v' \end{pmatrix} = \begin{pmatrix} a_0 & 1 \\ 1 & 0 \end{pmatrix} \cdots \begin{pmatrix} a_i & 1 \\ 1 & 0 \end{pmatrix},
$$

on dit que l'élément *u/* *v* de Q ∪ {∞} est le (i + 1)-ème convergent du dfc
(alors *u*'/*v*' est le i-ème convergent du dfc).
## 2. Calcul du développement en fraction continue de $(ax + b)/d$ à partir du développement en fraction continue de $x$

**2.1. Premier algorithme.** Nous donnons dans cette section un algorithme analogue à celui donné par [Men1] et bien explicité dans [Coh]. Il conduit à un faux dfc du rationnel $(ax + b)/d$. Il est basé sur le lemme suivant qui est l'analogue matriciel des lemmes 1 et 2 dans le papier cité.

**LEMME 1.** On considère des entiers $a > 0$, $b$ arbitraire, $d > 0$ et $v$ arbitraire. On note $e_0, e_1, \dots, e_{2s}/$ le dfc pair de $(av + b)/d$. On note $g = \text{pgcd}(|av + b|, d)$, $a' = (av + b)/g$, $d' = d/g$ et $d''$ le dénominateur de l'avant-dernier convergent, c'est-à-dire encore que $a'$, $d'$ et $d''$ sont donnés par

$$ \begin{pmatrix} a' & a'' \\ d' & d'' \end{pmatrix} = \begin{pmatrix} e_0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} e_1 & 1 \\ 1 & 0 \end{pmatrix} \cdots \begin{pmatrix} e_{2s} & 1 \\ 1 & 0 \end{pmatrix}. $$

Alors on a

$$ (*) \quad \begin{pmatrix} a & b \\ 0 & d \end{pmatrix} \begin{pmatrix} v & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} e_0 & 1 \\ 1 & 0 \end{pmatrix} \cdots \begin{pmatrix} e_{2s} & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} g & -d''a \\ 0 & d'a \end{pmatrix} $$

avec $0 \le d'' < d'$. Le cas $d'' = 0$ correspond au cas où $s = 0$, c'est-à-dire, $(av + b)/d$ entier.

**Preuve.** La propriété $0 \le d'' < d'$ est bien connue et résulte de ce que les $e_i$ sont $> 0$ pour $i \ge 1$. Le calcul de la matrice

$$ A = \begin{pmatrix} a' & a'' \\ d' & d'' \end{pmatrix}^{-1} \begin{pmatrix} a & b \\ 0 & d \end{pmatrix} \begin{pmatrix} v & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} -d'' & a'' \\ d' & -a' \end{pmatrix} \begin{pmatrix} av+b & a \\ d & 0 \end{pmatrix} $$

fournit facilement les termes $0, d'a$ et $-d''a$ de la matrice

$$ A = \begin{pmatrix} g & -d''a \\ 0 & d'a \end{pmatrix}. $$

Enfin le dernier coefficient est $g$ puisqu'on sait que le déterminant de $A$ est égal à $ad$. ■

Remarquez que l'égalité (*) signifie qu'on peut remplacer le produit d'une matrice du type $(\begin{smallmatrix} a & b \\ 0 & d \end{smallmatrix})$ et d'une matrice du type $(\begin{smallmatrix} v & 1 \\ 1 & 0 \end{smallmatrix})$ par le produit de plusieurs matrices du type $(\begin{smallmatrix} v & 1 \\ 1 & 0 \end{smallmatrix})$ et d'une matrice du type $(\begin{smallmatrix} a & b \\ 0 & d \end{smallmatrix})$. On en déduit l'algorithme suivant :

**ALGORITHME 1. Entrées** : des entiers $a > 0$, $b$ arbitraire, $d > 0$ et le dfc $x_0, x_1, \dots, x_n/d$ un nombre rationnel $x$. On note $\Delta$ le déterminant $ad$.

**Initialisation** : $a_0 = a$, $b_0 = b$, $d_0 = d$.

**Étape k (pour k de 0 à n)** : On calcule $e_{k,0}, e_{k,1}, \dots, e_{k,2s_k}/$ le dfc pair de $(a_k x_k + b_k)/d_k$. On note $\lambda_k$ la liste $[e_{k,0}, e_{k,1}, \dots, e_{k,2s_k}]$.
Si $k < n$ on fait quelques calculs supplémentaires :

• $a_{k+1} = \text{pgcd}(|a_k x_k + b_k|, d_k)$,

• $d_{k+1} = \Delta/a_{k+1}$ et

• $b_{k+1} = -f_k a_k$ où $f_k$ est "le dénominateur de l'avant-dernier convergent" du dfc $\lambda_k$: notez qu'on a $-d_{k+1} < b_{k+1} \le 0$ et que $b_{k+1} = 0$ ssi $(a_k x_k + b_k)/d_k$ est entier (cf. lemme 1).

Sortie : la liste concatenée des $\lambda_k$ :

$$ \lambda = \lambda_0 \cdot \lambda_1 \cdot \dots \cdot \lambda_n = [e_{0,0}, e_{0,1}, \dots, e_{0,2s_0}, \dots, e_{n,0}, e_{n,1}, \dots, e_{n,2s_n}]. $$

**PROPOSITION 1.** La sortie de l'algorithme 1, lorsque les entrées vérifient les hypothèses indiquées, fournit un développement en fraction continue (en général faux) de $(ax + b)/d$ :

$$ /e_{0,0}, e_{0,1}, \dots, e_{0,2s_0}, \dots, e_{n,0}, e_{n,1}, \dots, e_{n,2s_n}/. $$

Preuve. L'égalité matricielle obtenue par application répétée du lemme 1 montre en fait le résultat un peu plus fort : la fonction homographique associée au faux dfc calculé est égale à la composée

$$ (z \mapsto (az + b)/d) \circ (z \mapsto x_0, x_1, \dots, x_n, z/). \quad \blacksquare $$

Les faits suivants, concernant le faux dfc calculé par l'algorithme, sont expliqués en même temps qu'énoncés.

**FAITS 1.** Dans le faux dfc obtenu, tous les entiers sont strictement positifs sauf éventuellement les $e_{k,0}$ qui peuvent être égaux à 0 ou $-1$ pour $k = 1, \dots, n$ (et avec $e_{0,0}$ arbitraire). En outre:

• La longueur du faux dfc obtenu est majorée par $\theta(\Delta) \lfloor f(x) \rfloor$ (clair).

• Si un $e_{k,0}$ avec $k \ge 1$ est égal à $-1$, l'entier $b_k$ est $< 0$ et le rationnel $(a_k x_k + b_k)/d_k$ est strictement compris entre $-1$ et $0$, donc la longueur de $\lambda_{k-1}$ et celle de $\lambda_k$ sont $\ge 3$. Ainsi un terme $-1$ non initial est toujours précédé et suivi de deux termes $> 0$.

• Si une liste $\lambda_k$ est de longueur 1 et si $k < n$, l'entier $b_{k+1}$ est nul et le rationnel $(a_{k+1}x_{k+1} + b_{k+1})/d_{k+1}$ est $> 0$. Ainsi deux termes 0 consécutifs sont nécessairement suivis de deux termes $> 0$. Remarquez cependant que le faux dfc peut très bien se terminer par un 0.

**2.2. Algorithme de réécriture d'un faux dfc.** Nous passons maintenant à la deuxième phase de l'algorithme de Mendès France, qui consiste à rétablir le "faux dfc" dans sa forme normale. La version donnée dans [Men2] est plus générale, et, nous semble-t-il, plus convaincante que celle donnée dans [Men1]. Avec l'algorithme de [Men2] tout "faux dfc" peut être transformé en un vrai dfc au moyen de "transformations élémentaires".
Les notations sont les suivantes :

• a, b, c désignent des entiers $\ge 1$,

• y, z désignent des entiers arbitraires,

• $\lambda$ et $\lambda'$ désignent des listes d'entiers arbitraires, éventuellement vides,

• $\mu$ désigne une liste d'entiers $\ge 1$, éventuellement vide.

Dans une première phase, on utilise systématiquement (jusqu'à épuisement des possibilités) la règle de contraction suivante :

$$ (0) \qquad \lambda \cdot [y, 0, z] \cdot \lambda' \mapsto \lambda \cdot [y + z] \cdot \lambda'. $$

Dans une deuxième phase, on déplace systématiquement vers la gauche le dernier terme $\le 0$ de la liste (sauf la tête de liste) en utilisant les règles suivantes.

Les deux premières règles concernent les termes $0$ ou $< 0$ en fin de liste, mais pas en début de liste :

$$ (1) \qquad \lambda \cdot [y, 0] \mapsto \lambda, $$

$$ (2) \qquad \lambda \cdot [y, -c] \mapsto \lambda \cdot [y - 1, 1, c - 1] \quad \text{suivi de (1) si } c = 1. $$

Notez que dans les deux cas, le numéro d'ordre du dernier terme $\le 0$ dans la liste a diminué strictement. Toutes les règles vérifieront cette propriété, qui assure la correction de l'algorithme 2.

Les règles suivantes de (3) à (9) concernent un terme $\le 0$ qui n'est ni en fin de liste, ni en début de liste, et qui est suivi par uniquement des termes $> 0$. On traite d'abord le cas d'un terme nul, puis celui d'un terme égal à $-2$, puis celui d'un terme $\le -3$, puis celui d'un terme égal à $-1$, ce dernier cas se divise en de nombreux sous-cas selon que le terme immédiatement après est 1 ou non, et selon la distance de $-1$ à la queue de la liste :

$$ (3) \qquad \lambda \cdot [y, 0, a] \cdot \mu \mapsto \lambda \cdot [y + a] \cdot \mu, $$

$$ (4) \qquad \lambda \cdot [y, -2, a] \cdot \mu \mapsto \lambda \cdot [y - 1, 2, a - 1] \cdot \mu \\ \qquad \text{suivi de (1) ou (3) si } a = 1, $$

$$ (5) \qquad \lambda \cdot [y, -(2+c), a] \cdot \mu \mapsto \lambda \cdot [y - 1, 1, c, 1, a - 1] \cdot \mu \\ \qquad \text{suivi de (1) ou (3) si } a = 1, $$

$$ (6) \qquad \lambda \cdot [y, -1, a + 1] \cdot \mu \mapsto \lambda \cdot [y - 2, 1, a - 1] \cdot \mu \\ \qquad \text{suivi de (1) ou (3) si } a = 1, $$

$$ (7) \qquad \lambda \cdot [y, -1, 1, a, b] \cdot \mu \mapsto \lambda \cdot [y - a - 2, 1, b - 1] \cdot \mu \\ \qquad \text{suivi de (1) ou (3) si } b = 1, $$

$$ (8) \qquad \lambda \cdot [y, -1, 1, a] \mapsto \lambda \cdot [y - a - 1], $$

$$ (9) \qquad \lambda \cdot [y, -1, 1] \mapsto \lambda \cdot [y]. $$
Tout à la fin, la règle (10) est utilisée pour se ramener au dfc ordinaire
si le vrai dfc obtenu est de longueur au moins 2 et se termine par 1 :

$$
(10) \qquad \lambda \cdot [y, 1] \mapsto \lambda \cdot [y + 1].
$$

Ceci donne l’algorithme suivant :

ALGORITHM 2. Première phase. Tant qu'il existe un terme = 0 ailleurs qu'en tête de liste, appliquez la règle (0) (par exemple en traitant toujours le dernier terme nul dans la liste).

Deuxième phase. Tant qu'il existe un terme $\leq 0$ ailleurs qu'en tête de liste, appliquez les règles (1) à (9), de manière itérative, en appliquant toujours celle des neuf règles qui s'applique au dernier terme $\leq 0$ de la liste. On a alors obtenu un vrai dfc (pair ou impair).

Terminez en appliquant éventuellement la règle (10).

Si la liste finale obtenue est vide, cela signifie que le faux dfc représente l'élément $\infty$. Cela ne pourra pas se produire avec les listes issues de l'algorithme 1.

La première phase de l'algorithme n'est pas nécessaire, mais son utilisa-
tion permet de montrer plus clairement la deuxième partie de la proposi-
tion 2.

Notez que seules les règles (2) et (5) augmentent éventuellement la
longueur de la liste.

Remarquons aussi que dans [Men2] manquent les règles (1), (2), (8) et (9). Ce sont des règles concernant la queue de la liste. Elles ne changent pas la valeur du dfc dans $\mathbb{Q} \cup \{\infty\}$, mais elles changent la fonction homographique associée au dfc.

PROPOSITION 2. *L'algorithme 2 traite un faux dfc arbitraire (représentant un élément $x$ de $\mathbb{Q} \cup \{\infty\}$) et le transforme en le développement en fraction continue ordinaire de $x$. Une liste fournie par l'algorithme 1 à laquelle on fait subir l'algorithme 2 n'augmente jamais de longueur.*

Preuve. La première partie de la proposition est claire (il suffit de
vérifier que chacune des règles est correcte et de voir que l'algorithme termine
à coup sûr). La deuxième affirmation résulte des Faits 1 affirmés après la
proposition 1 et d'une analyse détaillée des cas.

La première remarque est que dans l'application de l'algorithme 2 à une
liste fournie par l'algorithme 1, durant la deuxième phase, le début de liste
$\lambda \cdot [y]$ présent dans les 9 règles utilisées est un segment initial de la liste
issue de la première phase et ne contient donc jamais de termes $= 0$ ni de
terme $< -1$, sauf éventuellement la tête de liste. En outre, dans ce début
de liste, un terme non initial égal à $-1$ est toujours précédé de deux termes
$> 0$.
Il faut maintenant vérifier que lorsque les règles (2) ou (5) sont appliquées (les seules qui allongent éventuellement la liste), elles ont été précédées d'événements qui ont suffisamment raccourci la liste pour que le résultat global ne soit jamais un allongement. C'est clair pour le cas de la règle (2), qui rallonge éventuellement la liste de un, car elle est précédée de l'un des 6 cas suivants, qui tous raccourcissent la liste :

• règle (2) avec $c = 1$ et $y \le 0$,

• règle (4) avec $\mu = \emptyset$, $a = 1$ et $y \le 0$,

• règle (6) avec $\mu = \emptyset$, $a = 1$ et $y \le 1$,

• règle (7) avec $\mu = \emptyset$, $b = 1$ et $y \le 1 + a$,

• règle (8) avec $y \le a$,

• règle (9) avec $y \le 0$.

Le cas de la règle (5), qui rallonge éventuellement la liste de deux, est plus subtil. Il est précédé de l'un des deux cas suivants :

• règle (7) avec $y < a$ et $(\mu \neq \emptyset)$ ou $b > 1$

(ici, tout va bien car cette règle raccourcit la liste de deux) ou bien

• règle (6) avec $y = -1$ et $(\mu \neq \emptyset)$ ou $a > 1$.

On est un peu ennuyé, parce que cette règle ne raccourcit pas la liste. Néanmoins, il faut se demander quand est-ce que le cas peut vraiment se produire. On a en effet deux $-1$ consécutifs dans la liste, et ceci ne peut arriver qu'après des événements qu'il est intéressant de préciser. Cela peut être a priori ou bien l'application des règles (2), (4) ou (5) avec $y = 0$, ou bien l'application de la règle (6) avec $y = 1$, ou bien celle de la règle (7) avec $y = a+1$, ou bien celle de la règle (8) avec $y = a$, avec dans chacun des cas $\lambda$ non vide et se terminant par $-1$. Vu la remarque initiale, les trois premiers cas ne peuvent pas se produire car un terme nul dans $\lambda \bullet [y]$ ne peut être qu'en tête de liste. Les deux derniers cas nous conviennent car les règles (7) et (8) raccourcissent la liste au moins de deux. Le cas de la règle (6) est le seul vraiment ennuyeux. Fort heureusement, il ne peut se produire deux fois de suite (la deuxième fois, on tomberait sur la règle (7) ou la règle (8)). Or ce devrait être nécessaire pour que deux $-1$ consécutifs se retrouvent dans une liste transformée. ■

### 2.3. Conséquences pour la longueur des développements en fraction continue

**THÉORÈME 1.** *Soit $x$ un rationnel.*

(i) On considère des entiers $a > 0$, $b$ arbitraire et $d > 0$. On pose $\Delta = ad$. Alors

$$ \lfloor f(x) \rfloor / \theta(\Delta) \le \lfloor f((ax + b) / d) \rfloor \le \lfloor f(x) \rfloor \theta(\Delta). $$
(ii) On considère des entiers $a < 0$, $b$ arbitraire et $d > 0$. Alors

$$ (\lfloor f(x) - 1 \rfloor) / \theta(\Delta) \leq \lfloor f((ax + b)/d) \rfloor \leq \lfloor f(x) \theta(\Delta) \rfloor + 1. $$

Preuve. (i) L'inégalité $\lfloor f((ax + b)/d) \rfloor \leq \lfloor f(x) \theta(\Delta) \rfloor$ résulte des propositions 1 et 2. Par ailleurs la transformation réciproque $y \mapsto (dy - b)/a$ est du même type et elle a même déterminant. Cela fournit l'inégalité $\lfloor f(x) \rfloor \leq \lfloor f((ax + b)/d) \rfloor \theta(\Delta)$.

(ii) Rappelons le passage de $x$ à $-x$ pour les dfc (vrais ou faux) :

* Si $x = x_0$ alors $-x = -x_0$.

* Si $x = x_0, x_1$ alors $-x = -(x_0 + 1), 1, x_1 - 1$ suivi de la règle (1) si $x_1 = 1$.

* Si $x = x_0, x_1, x_2, \dots$ alors $-x = -(x_0 + 1), 1, x_1 - 1, x_2, \dots$ suivi de la règle (3) si $x_1 = 1$.

Dans le cas des dfc ordinaires, il faut terminer éventuellement avec la règle (10). Donc $\lfloor f(-x) \rfloor \leq \lfloor f(x) \rfloor + 1$. On a ensuite $\lfloor f(-(ax + b)/d) \rfloor \leq \lfloor f(x) \theta(\Delta) \rfloor$. D'où $\lfloor f((ax + b)/d) \rfloor \leq \lfloor f(x) \theta(\Delta) \rfloor + 1$.

Pour l'autre inégalité on considère la transformation réciproque $y \mapsto (-dy + b)/(-a)$ et on applique le résultat précédent. ■

Remarque. Lorsque $(a s_0 + b)/d$ est un entier, par exemple lorsque $d = 1$ (cas traité dans [Men1]), la liste $\lambda_0$ fournie par l'algorithme 1 est de longueur 1 et on peut donc obtenir une majoration légèrement meilleure. Par exemple, dans le cas (1) du théorème 1,

$$ \lfloor f((ax + b)/d) \rfloor \leq (\lfloor f(x) \rfloor - 1)\theta(\Delta) + 1. $$

**3. Calcul du développement en fraction continue de $(ax+b)/(cx+d)$ à partir du développement en fraction continue de $x$.** On supposera dans toute cette section que $a, b, c$ et $d$ sont quatre entiers premiers entre eux dans leur ensemble et que le déterminant $\Delta = ad - bc$ est $\neq 0$.

Nous ramenons le calcul (posé en titre de section) au calcul donné dans la section 2 au moyen d'un algorithme qui est essentiellement celui donné dans [Men2]. Nous donnons le lemme correspondant sous forme matricielle.

**LEMME 2.** On considère des entiers $a, b, d$ arbitraires et $c > 0$. On suppose $a, b, c$ et $d$ premiers entre eux dans leur ensemble et le déterminant $\Delta = ad - bc \neq 0$. On note $f(e_0, e_1, \dots, e_r)$ le dfc pair (resp. le dfc impair) de $a/c$ si $\Delta < 0$ (resp. si $\Delta > 0$). Soit $\varepsilon = \pm 1$ le signe du déterminant $\Delta$. On note $g = \text{pgcd}(|a|, c)$, $a' = a/g$, $c' = c/g$ et $c''$ le dénominateur de l'avant-dernier convergent, c'est-à-dire encore que $a', c'$ et $c''$ sont donnés par

$$ (**) \qquad \begin{pmatrix} a' & a'' \\ c' & c'' \end{pmatrix} = \begin{pmatrix} e_0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} e_1 & 1 \\ 1 & 0 \end{pmatrix} \cdots \begin{pmatrix} e_r & 1 \\ 1 & 0 \end{pmatrix}. $$
Alors on a

$$ (***)
\begin{pmatrix} a & b \\ c & d \end{pmatrix} = \begin{pmatrix} e_0 & 1 \\ 1 & 0 \end{pmatrix} \cdots \begin{pmatrix} e_r & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} g & \varepsilon(c''b - a''d) \\ 0 & |\Delta|/g \end{pmatrix}. $$

Donc

$$ \frac{ax+b}{cx+d} = \left/ \begin{array}{l} e_0, e_1, \dots, e_r, \\ \frac{gx + \varepsilon(c''b - a''d)}{|\Delta|/g} \end{array} \right/ . $$

Preuve. Le déterminant de la matrice (**) est égal à $\varepsilon$ par choix de la parité du dfc considéré. Le calcul de la matrice

$$ B = \begin{pmatrix} a' & a'' \\ c' & c'' \end{pmatrix}^{-1} \begin{pmatrix} a & b \\ c & d \end{pmatrix} = \varepsilon \begin{pmatrix} c'' & -a'' \\ -c' & a' \end{pmatrix} \begin{pmatrix} a & b \\ c & d \end{pmatrix} $$

fournit facilement les termes $0, \varepsilon\Delta/g = |\Delta|/g$ et $\varepsilon(c''b - a''d)$ de la matrice

$$ B = \begin{pmatrix} g & \varepsilon(c''b - a''d) \\ 0 & |\Delta|/g \end{pmatrix}. $$

On en déduit le terme $g$ puisque le déterminant de $B$ est égal à $\varepsilon\Delta$, et enfin l'égalité (***) en résulte. ■

On en déduit l'algorithme suivant pour le calcul du dfc de $y = \frac{ax+b}{cx+d}$ lorsque $c > 0$.

* Calculer le dfc (pair ou impair) de $a/c$ et appliquez le lemme 2.

* Calculer ensuite le dfc de $\frac{gx+\varepsilon(c''b-a''d)}{|\Delta|/g}$ conformément à l'algorithme de la section 2 (cas du déterminant > 0).

* Mettre les deux dfc bout à bout.

On obtient un dfc représentant $y$. Ce dfc est un faux dfc uniquement dans le cas où le deuxième dfc commence par un terme $\le 0$.

* Dans ce cas appliquer les règles de réduction décrites à la section 2.

Ici, on voit facilement que l'application de ces règles ne produira pas une augmentation de longueur supérieure à 2 (notez que par contre elles peuvent réduire le faux dfc jusqu'au dfc vide de $\infty$ dans le cas où $x = -d/c$).

Ainsi, compte tenu du théorème 1, nous obtenons le théorème 2 suivant :

**THÉORÈME 2.** Soit un rationnel $x$ et des entiers $a, b, c > 0$ et $d$. On suppose $a, b, c$ et $d$ premiers entre eux dans leur ensemble et le déterminant $\Delta = ad - bc \neq 0$. Alors, si $\Delta > 0$, on a

$$ (\mathbf{lf}(x) - \mathbf{lf}_i(-d/c) - 2)/\theta(\Delta) \le \mathbf{lf}\left(\frac{ax+b}{cx+d}\right) \le \mathbf{lf}(x)\theta(\Delta) + \mathbf{lf}_i(a/c) + 2, \\ \text{et si } \Delta < 0, \text{ on a} $$

$$ (\mathbf{lf}(x) - \mathbf{lf}_p(-d/c) - 2)/\theta(\Delta) \le \mathbf{lf}\left(\frac{ax+b}{cx+d}\right) \le \mathbf{lf}(x)\theta(\Delta) + \mathbf{lf}_p(a/c) + 2. $$
On notera que ces bornes sont plus simples et améliorent assez sensiblement celles données dans [Men2].

Remarques. (i) Le théorème 1 peut être considéré comme un cas particulier du théorème 2 si nous prenons conventionnellement $\mathbf{lfi}(\infty) = -2$ et $\mathbf{lfp}(\infty) = -1$ (ce qui est certes très conventionnel).

(ii) Lorsque $\Delta = \pm 1$ on n'a pas besoin d'appliquer l'algorithme de la section 2 après le "lemme 2" de la section 3. Ceci confirme la convention $\theta(\pm 1) = 1$.

**4. Continuité uniforme d'une fonction homographique rationnelle.** Le théorème suivant peut être interprété en disant que la transformation d'un irrationnel $x$ par une fonction homographique rationnelle (c'est-à-dire, à coefficients entiers) de déterminant $\Delta$ est (à peu près) lipschitzienne de rapport $\theta(\Delta)$ en tant qu'application des irrationnels vers les irrationnels, donnés par leurs dfc, avec la distance

$$d(a_0, a_1, \dots, a_n, \dots, b_0, b_1, \dots, b_n, \dots) = 1/(\text{premier indice } i \text{ tel que } a_i \neq b_i).$$

**THÉORÈME 3.** Soit $x$ un réel, rationnel ou irrationnel, et $a, b, c, d$ des entiers premiers entre eux dans leur ensemble avec $\Delta = ad - bc \neq 0$. Soit

$$y = \frac{ax + b}{cx + d}$$

et posons

$$\varphi(k) = \begin{cases} k\theta(\Delta) + \mathbf{lfi}(-d/c) + 2 & \text{si } \Delta > 0, \\ k\theta(\Delta) + \mathbf{lfp}(-d/c) + 2 & \text{si } \Delta < 0. \end{cases}$$

Alors les $k$ premiers termes du dfc de $y$ ne dépendent que des $\varphi(k)$ premiers termes du dfc de $x$. Ils peuvent donc être obtenus en appliquant les algorithmes décrits aux sections 2 et 3 pour les $\varphi(k)$ premiers termes du dfc de $x$.

Remarque. Si $c = 0$ on appliquera dans la majoration donnée ci-dessus la convention expliquée en remarque après le théorème 2 : $\mathbf{lfi}(\infty) = -2$ et $\mathbf{lfp}(\infty) = -1$.

Preuve du théorème 3. Notons $\psi$ la fonction homographique $z \mapsto \frac{az+b}{cz+d}$. Certifier que $\psi(x)$ a les $k$ premiers termes de son dfc égaux à $[y_0, y_1, \dots, y_{k-1}]$ revient à comparer $\psi(x)$ aux deux rationnels :

$$\frac{y_0, y_1, \dots, y_{k-1}}{1 + y_{k-1}} \text{ et } \frac{y_0, y_1, \dots, 1}{y_0, y_1, \dots, 1 + y_{k-1}}.$$

Cela revient à comparer $x$ aux trois rationnels

$$-d/c, \quad \psi^{-1}(y_0, y_1, \dots, y_{k-1}) \quad \text{et} \quad \psi^{-1}(y_0, y_1, \dots, 1 + y_{k-1}).$$

Chacun de ces trois rationnels a une longueur inférieure ou égale à $\varphi(k)$.
Enfin la comparaison de deux réels donnés par leurs dfc (finis ou infinis) est claire dès que les dfc divergent. ■

**Conclusion.** Il existe dans la littérature d'autres algorithmes que celui de Mendès France pour calculer le dfc $/y_0, y_1, ..., y_k, .../ du réel $y = (ax + b)/(cx + d)$ à partir du dfc $/x_0, x_1, ..., x_k, .../ de x$.

Signalons par exemple l'algorithm de Raney [Ran] qui est de conception très simple, mais qui offre l'inconvénient de travailler avec des "entiers bâtons". Le réel $x$ est supposé $> 0$, les entiers $a, b, c, d$ sont supposés $\ge 0$ avec le déterminant $ad - bc > 0$. Le dfc de $x$ est présenté à la Farey, c'est-à-dire par exemple que $3, 6, 1, 8, .../ est représenté par la suite infinie 000111110111111110... De même le dfc de $y$ sera présenté sous une forme analogue. On appelle $p$ la lettre suivante "à lire" (0 ou 1) dans le dfc de $x$ et $q$ la lettre suivante "à écrire" dans le dfc de $y$. On note $U$ et $V$ les matrices

$$U = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}, \quad V = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}.$$

On note $\mathbf{P}$ l'ensemble des matrices à coefficients $\ge 0$. Enfin $M$ est une matrice qui évolue au cours de l'algorithm (mais son déterminant reste inchangé).

Voici l'algorithm.

1. Initialiser $M$ avec $\begin{pmatrix} a & b \\ c & d \end{pmatrix}$.

2. Si $p = 0$ faire $M \leftarrow MU$ sinon faire $M \leftarrow MV$.

3. Tant que $(U^{-1}M \in \mathbf{P}$ ou $V^{-1}M \in \mathbf{P})$ faire

• si $U^{-1}M \in \mathbf{P}$ faire $M \leftarrow U^{-1}M$, $q \leftarrow 0$

• si $V^{-1}M \in \mathbf{P}$ faire $M \leftarrow V^{-1}M$, $q \leftarrow 1$

(fin du tant que).

4. Aller à 2.

L'algorithm de Raney, et à notre connaissance les autres algorithmes présentés, reviennent à calculer des intervalles rationnels de plus en plus précis sur lequels est situé $y$ jusqu'à trouver sa partie entière $y_0$, puis son premier quotient partiel $y_1$, puis le deuxième quotient partiel $y_2$, etc. Ces algorithmes n'ont donc pas vraiment une spécificité adaptée au problème que l'on veut résoudre. En particulier, ils ne peuvent donner aucune information de nature arithmétique fine comparable à celle que donne l'algorithm de Mendès France (théorèmes 1, 2 et 3 ci-dessus).

Un autre inconvénient de l'algorithm de Raney réside dans la difficulté qu'il y a à récupérer le dfc usuel de $y$ à partir de son développement de Farey. En effet, il est assez facile de vérifier qu'il n'existe pas de fonctionnelle récursive qui réalise cette opération (cf. [LL]). En d'autres termes, les algorithmes travaillant avec les développements de Farey ne se situent pas dans la même "composante connexe" que ceux travaillant avec les dfc usuels.
Références

[Coh] H. Cohen, *Multiplication par un entier d'une fraction continue périodique*, Acta Arith. 26 (1974), 129-148.

[LL] S. Labhalla et H. Lombardi, *Fractions de Farey et coupures de Dedekind*, en préparation.

[Men1] M. Mendès France, *Sur les fractions continues limitées*, Acta Arith. 23 (1973), 207-215.

[Men2] —, *The depth of a rational number*, dans : Topics in Number Theory (Colloq. Debrecen, 1974), Colloq. Math. Soc. János Bolyai 13, 1976, 183-194.

[Ran] G. Raney, *On continued fractions and finite automata*, Math. Ann. 206 (1973), 265-283.

DÉPARTEMENT DE MATHÉMATIQUES
UNIVERSITÉ DE MARRAKECH
BD DE SAFI, BP S 15
MARRAKECH, MAROC

LABORATOIRE DE MATHÉMATIQUES
URA CNRS 741
UNIVERSITÉ DE FRANCHE-COMTÉ
25030 BESANÇON CEDEX, FRANCE
E-mail: HL@GRENET.FR

Reçu le 18.10.1994
et révisé le 8.1.1995

(2683)