# Introduction à la théorie des nombres/Approximation diophantienne et fractions continues

Soit $x$ un réel.

## Approximation d'un réel par des rationnels
### Application du principe des tiroirs

On cherche à approcher $x$ par des rationnels $p/q$ « raisonnables » (de dénominateur $q$ et numérateur $p\approx xq$ « pas trop grands »). Comme $\mathbb {Q}$ est dense dans $\mathbb {R}$, plus on s'autorise $q$ grand, plus on peut se rapprocher du réel $x$. La taille nécessaire pour $q$ en fonction de l'erreur tolérée dépend de $x$, mais pour tous les réels on a déjà :
$\forall x\in \mathbb {R} \quad \forall n\in \mathbb {N} ^{*}\quad \exists (p,q)\in \mathbb {Z} \times \mathbb {N} ^{*}\quad \left|x-{\frac {p}{q}}\right|<{\frac {1}{nq}}\leq {\frac {1}{q^{2}}}$.

#### Application

    On en déduira (dans l'exercice lié) que si $x\notin \mathbb {Q}$, alors il existe une infinité de fractions $p/q$ — et a fortiori de couples $(p,q)$ — vérifiant $\left|x-p/q\right|<1/q^{2}$.

#### Remarques

   * À l'inverse, si $x=a/b\in \mathbb {Q}$ alors, en excluant les solutions triviales $(p,q)=(na,nb)$, il ne reste qu'un nombre fini de solutions (voir infra).
   * On verra au chapitre 6 un théorème plus général d'approximation diophantienne simultanée de plusieurs réels.
Les $n+1$ éléments (non nécessairement distincts) $\{kx\}:=kx-\lfloor kx\rfloor \in \left[0,1\right[$ (parties fractionnaires des $kx$) pour $k=0,1,\dots ,n$ se répartissent dans les $n$ « tiroirs » $\left[{\frac {r}{n}},{\frac {r+1}{n}}\right[$ où $r\in \{0,1,\dots ,n-1\}$.
Il existe donc un tiroir contenant deux parties fractionnaires :
    $\exists r,j,k\in \mathbb {N} \quad r<n,\quad j<k\leq n,\quad {\frac {r}{n}}\leq \{jx\},\{kx\}<{\frac {r+1}{n}}$.
Alors, l'entier
    $q:=k-j$ vérifie
          $1\leq q\leq n$
et l'entier
    $p:=\lfloor kx\rfloor -\lfloor jx\rfloor =\left(kx-\{kx\}\right)-\left(jx-\{jx\}\right)=qx-\left(\{kx\}-\{jx\}\right)$ vérifie
          $|qx-p|<{\frac {1}{n}}$.

### Mesure d'irrationalité

* La mesure d'irrationalité de $x$ est la borne supérieure de l'ensemble des réels $d$ pour lesquels il existe une infinité de couples $(p,q)\in \mathbb {Z} \times \mathbb {N} ^{*}$ tels que $0<\left|x-{\frac {p}{q}}\right|<{\frac {1}{q^{d}}}$.
* Lorsqu'elle est infinie, on dit que $x$ est un nombre de Liouville.
Plus cette « mesure » est grande, mieux $x$ est approchable par des rationnels différents de $x$, et moins il est algébrique. Plus précisément :
* Elle vaut $1$ si $x\in \mathbb {Q}$ (voir l'exercice 2-1), et elle est supérieure ou égale à $2$ sinon (voir supra).
* Elle est finie si $x$ est algébrique, d'après le théorème de Liouville ci-dessous. Les nombres de Liouville sont donc transcendants.
Exemple de nombre de Liouville : la constante de Liouville $\sum _{n\in \mathbb {N} }{\frac {1}{10^{n!}}}$ (voir l'exercice lié).
On démontrera en exercice la proposition suivante :
La mesure d'irrationalité de $x$ est la borne inférieure de l'ensemble des exposants $d$ tels que « $\left|x-{\frac {p}{q}}\right|\gg {\frac {1}{q^{d}}}$ », c'est-à-dire tels que :
il existe $A>0$ tel que pour tout rationnel $p/q\neq x$ (avec $p\in \mathbb {Z}$ et $q\in \mathbb {N} ^{*}$), on ait : $\left|x-{\frac {p}{q}}\right|\geq {\frac {A}{q^{d}}}$.
Cette définition équivalente de la mesure d'irrationalité est plus commode pour démontrer le théorème suivant :
Si $x$ est algébrique de degré $d\geq 2$, alors sa mesure d'irrationalité est inférieure ou égale à $d$.
Soit $P\in \mathbb {Z} [X]$, de degré $d>1$, irréductible sur $\mathbb {Q}$ (donc sans racine rationnelle), tel que $P(x)=0$. Montrons que
    $\exists A>0\quad \forall (p,q)\in \mathbb {Z} \times \mathbb {N} ^{*}\quad |x-p/q|\geq A/q^{d}$.
Soit $(p,q)\in \mathbb {Z} \times \mathbb {N} ^{*}$.
* Si $|x-p/q|>1$, on a immédiatement $|x-p/q|>1/q^{d}$.
* Sinon :
** $p/q\in [x-1,x+1]$ donc d'après l'inégalité des accroissements finis, $|P(p/q)-P(x)|\leq M|x-p/q|$ avec $M:=\max _{t\in [x-1,x+1]}|P'(t)|$.
** Or $q^{d}(P(p/q)-P(x))=q^{d}P(p/q)\in \mathbb {Z} ^{*}$ (d'après les hypothèses sur $P$) donc $|P(p/q)-P(x)|\geq 1/q^{d}$.
** Par conséquent : $|x-p/q|\geq 1/(Mq^{d})$.
* Posons $A:=\min(1,1/M)$. On a dans tous les cas : $|x-p/q|\geq A/q^{d}$.

## Fractions continues
### Réduites, ou fractions continues finies

La suite des réduites $\left[a_{0},\dots ,a_{n}\right]$ associées à une suite $\left(a_{n}\right)_{n}$ est définie récursivement par :
    $\left[a_{0}\right]=a_{0}\quad {\text{et}}\quad \forall p\geq 1\quad \left[a_{0},\dots ,a_{p}\right]=a_{0}+{\frac {1}{\left[a_{1},\dots ,a_{p}\right]}}$.
La preuve de la propriété suivante est laissée en exercice.
$\forall q\in \{1,\dots ,p\}\quad \left[a_{0},\dots ,a_{p}\right]=\left[a_{0},\dots ,a_{q-1},\left[a_{q},\dots ,a_{p}\right]\right]$.

#### Remarques

   * En particulier, $\left[a_{0},\dots ,a_{p}\right]=\left[a_{0},\dots ,a_{p-1}+1/a_{p}\right]$, ce qui fournit une définition récursive équivalente à la précédente.
   * On n'a pas imposé pour l'instant que les $a_{i}$ soient des entiers, ni pris la précaution de supposer non nulles les quantités qu'on inverse. Cette définition est donc à prendre au sens formel, c'est-à-dire en considérant les $a_{i}$ comme des indéterminées et en se plaçant dans leur corps de fractions rationnelles. Par exemple :
       $\left[a_{0},a_{1},a_{2}\right]=a_{0}+{\frac {1}{a_{1}+{\frac {1}{a_{2}}}}}=a_{0}+{\frac {a_{2}}{a_{1}a_{2}+1}}={\frac {a_{0}a_{1}a_{2}+a_{0}+a_{2}}{a_{1}a_{2}+1}}\in \mathbb {Q} \left(a_{0},a_{1},a_{2}\right)$.

### Les deux fractions continues (finies) d'un rationnel

Pour tout rationnel $r$, l'algorithme d'Euclide fournit un développement de $r$ en fraction continue finie « simple », c'est-à-dire avec $a_{0}\in \mathbb {Z}$ et $a_{i}\in \mathbb {N} ^{*}$ pour $i>0$.
Si $r=p/q$, on pose $p_{0}=p,p_{1}=q$ puis, tant que $p_{j+1}$ n'est pas nul, on définit les entiers $a_{j}$ et $p_{j+2}$ par
    $p_{j}=a_{j}p_{j+1}+p_{j+2}$ et $0\leq p_{j+2}<p_{j+1}$.
Autrement dit :
    $r={\frac {p_{0}}{p_{1}}}=a_{0}+{\frac {1}{p_{1}/p_{2}}},\quad {\frac {p_{1}}{p_{2}}}=a_{1}+{\frac {1}{p_{2}/p_{3}}},\quad {\frac {p_{2}}{p_{3}}}=a_{2}+{\frac {1}{p_{3}/p_{4}}},\quad \dots$ et $\left(p_{k}\right)$ est une suite strictement décroissante d'entiers positifs.
L'algorithme d'Euclide finit par s'arrêter. Si $p_{n+1}\neq 0$ et $p_{n+2}=0$ alors $p_{n}/p_{n+1}=a_{n}$ donc
    $p_{0}/p_{1}=\left[a_{0},p_{1}/p_{2}\right]=\left[a_{0},a_{1},p_{2}/p_{3}\right]=\dots =\left[a_{0},a_{1},\dots ,a_{n}\right]$.
Le développement $r=\left[a_{0},\dots ,a_{n}\right]$ obtenu ainsi a la particularité que les $a_{i}$ pour $i>0$ sont même strictement supérieurs à $1$. On en déduit un second développement de $r$ en fraction continue simple, qui n'a plus cette particularité : $r=\left[a_{0},\dots ,a_{n}-1,1\right]$.
Ce sont les deux seuls (cf. exercice lié).

### La fraction continue (infinie) d'un irrationnel

Dans l'algorithme d'Euclide ci-dessus, si l'on note $x_{j}=p_{j}/p_{j+1}$ (en particulier $x_{0}=r$), $a_{j}$ était la partie entière de $x_{j}$ et $1/x_{j+1}$ sa partie fractionnaire. Pour tout irrationnel $x$, le même algorithme donne une fraction continue simple infinie :
    $x_{0}:=x,\quad a_{n}:=\lfloor x_{n}\rfloor ,\quad x_{n}=:a_{n}+{\frac {1}{x_{n+1}}}$.
Ainsi, $x=\left[a_{0},\dots ,a_{n},x_{n+1}\right]$ et l'algorithme ne s'arrête évidemment jamais. L'irrationnel $x_{p}$ ($>1$ si $p>0$) et sa partie entière $a_{p}$ sont appelés le quotient complet et le quotient partiel de $x$ d'indice $p$.

### Numérateurs et dénominateurs des réduites

On a déjà observé que les réduites associées à une suite $\left(a_{n}\right)$ s'expriment rationnellement en fonction des $a_{i}$. On peut systématiser l'exemple qui l'illustrait :
Les suites $\left(h_{n}\right)$ et $\left(k_{n}\right)$ des numérateurs et dénominateurs des réduites associées à une suite $(a_{n})$ sont définies par :
    ${\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}}$
On obtient ainsi :
    ${\begin{matrix}\left[a_{0},a_{1},\ldots ,a_{p}\right]&=&{\frac {a_{p}h_{p-1}+h_{p-2}}{a_{p}k_{p-1}+k_{p-2}}}&=&{\frac {h_{p}}{k_{p}}}&\quad &(1)\\a_{p}&=&-\,{\frac {\left[a_{0},a_{1},\ldots ,a_{p}\right]k_{p-2}-h_{p-2}}{\left[a_{0},a_{1},\ldots ,a_{p}\right]k_{p-1}-h_{p-1}}}&=&-\,{\frac {h_{p}k_{p-2}-h_{p-2}k_{p}}{h_{p}k_{p-1}-h_{p-1}k_{p}}}&\quad &(2)\\h_{p-1}k_{p}-h_{p}k_{p-1}&=&(-1)^{p}&&&\quad &(3)\end{matrix}}$

#### Remarques

   * Comme dans la définition des réduites (voir supra), ces formules sont à prendre au sens formel, les $a_{i}$ étant des indéterminées et les $h_{p},k_{p}$ des polynômes en ces indéterminées. On peut donc y remplacer à volonté les indéterminées par des entiers ou même des réels, tant que cela ne remplace pas les dénominateurs par $0$.
   * En particulier, pour une fraction continue simple infinie :
   ** pour tout $p\geq 0$ : $h_{p}\in \mathbb {Z}$ et $k_{p}\in \mathbb {N} ^{*}$ ;
   ** $h_{p}\land k_{p}=1$ ;
   ** la suite d'entiers $\left(k_{p}\right)_{p\geq 1}$ est strictement croissante donc tend vers l'infini.

### Bijection entre irrationnels et fractions continues infinies

Les résultats de cette section sont centraux dans la théorie des fractions continues : ils établissent une bijection entre l'ensemble des fractions continues infinies simples et l'ensemble des irrationnels, et montrent au passage que les réduites d'un irrationnel en constituent une « bonne approximation », en un sens qui sera précisé dans la section suivante.
* La suite $(h_{n}/k_{n})$ des réduites d'une fraction continue infinie simple $\left(a_{n}\right)$ converge.
* Sa limite $\ell$ vérifie : $\forall p\in \mathbb {N} \quad {\frac {1}{k_{p}(k_{p+1}+k_{p})}}<\left|\ell -{\frac {h_{p}}{k_{p}}}\right|<{\frac {1}{k_{p}k_{p+1}}}$.
* $\ell$ est irrationnel.
Cette limite $\ell$ est notée $\left[a_{0},a_{1},\dots \right]$.
* ${\frac {h_{p+1}}{k_{p+1}}}-{\frac {h_{p}}{k_{p}}}={\frac {(-1)^{p}}{k_{p}k_{p+1}}}$ est le terme général d'une série alternée convergente.
* La majoration résulte du point précédent, et la minoration de
    $\left|\ell -{\frac {h_{p}}{k_{p}}}\right|>\left|{\frac {h_{p+2}}{k_{p+2}}}-{\frac {h_{p}}{k_{p}}}\right|=\left|{\frac {h_{p+2}}{k_{p+2}}}-{\frac {h_{p+1}}{k_{p+1}}}+{\frac {h_{p+1}}{k_{p+1}}}-{\frac {h_{p}}{k_{p}}}\right|={\frac {1}{k_{p}k_{p+1}}}-{\frac {1}{k_{p+1}k_{p+2}}}\geq {\frac {1}{k_{p}k_{p+1}}}-{\frac {1}{k_{p+1}(k_{p}+k_{p+1})}}={\frac {1}{k_{p}(k_{p+1}+k_{p})}}$.
* $\ell$ ne peut pas être égal à un rationnel $a/b$, car l'encadrement de l'erreur donnerait alors $\forall p\in \mathbb {N} \quad 0<\left|ak_{p}-h_{p}b\right|<{\frac {b}{k_{p+1}}}$, or ${\frac {b}{k_{p+1}}}\to 0$ et $ak_{p}-h_{p}b\in \mathbb {Z}$.
Soit $\ell :=\left[a_{0},a_{1},\dots \right]$ la limite des réduites ${\frac {h_{n}}{k_{n}}}=\left[a_{0},\dots ,a_{n}\right]$ d'une fraction continue simple infinie.
Pour tout $p\geq 0$, l'irrationnel $\ell _{p}:=\left[a_{p},a_{p+1},\dots \right]$ vérifie :
    ${\begin{matrix}\ell =\left[a_{0},a_{1},\ldots ,a_{p-1},\ell _{p}\right]={\frac {\ell _{p}h_{p-1}+h_{p-2}}{\ell _{p}k_{p-1}+k_{p-2}}}&\quad &(1')\\\ell _{p}=-{\frac {\ell k_{p-2}-h_{p-2}}{\ell k_{p-1}-h_{p-1}}}&&(2').\end{matrix}}$
Pour tout $n\geq p$, en remplaçant $a_{p}$ par $\left[a_{p},\dots ,a_{n}\right]$ dans les formules génériques sur les numérateurs et dénominateurs des réduites (voir supra), on obtient :
* $\left[a_{0},a_{1},\ldots ,a_{n}\right]=\left[a_{0},a_{1},\ldots ,a_{p-1},\left[a_{p},\dots ,a_{n}\right]\right]={\frac {\left[a_{p},\dots ,a_{n}\right]h_{p-1}+h_{p-2}}{\left[a_{p},\dots ,a_{n}\right]k_{p-1}+k_{p-2}}}$ ;
* $\left[a_{p},\dots ,a_{n}\right]=-{\frac {\left[a_{0},a_{1},\ldots ,a_{n}\right]k_{p-2}-h_{p-2}}{\left[a_{0},a_{1},\ldots ,a_{n}\right]k_{p-1}-h_{p-1}}}$.
On conclut en passant aux limites quand $n\to \infty$.
L'application $\left(a_{n}\right)\mapsto \left[a_{0},a_{1},\dots \right]$ est une bijection de l'ensemble des fractions continues infinies simples dans l'ensemble des irrationnels ; la bijection réciproque est l'application qui associe à chaque irrationnel sa fraction continue.
Notons $L:\mathbb {Z} \times {\mathbb {N} ^{*}}^{\mathbb {N} ^{*}}\to \mathbb {R} \setminus \mathbb {Q}$ l'application $\left(a_{n}\right)\mapsto \left[a_{0},a_{1},\dots \right]$ et $F:\mathbb {R} \setminus \mathbb {Q} \to \mathbb {Z} \times {\mathbb {N} ^{*}}^{\mathbb {N} ^{*}}$ l'application qui à tout irrationnel associe sa fraction continue.
* $L\circ F$ est l'identité : soient $\left(a_{n}\right)=F(x)$ et $\ell =L\left(\left(a_{n}\right)\right)$. Par définition de $F$, on a $x=\left[a_{0},\dots ,a_{n},x_{n+1}\right]$ avec $0<1/x_{n+1}<1/a_{n+1}$, donc $x$ est constamment compris entre deux termes consécutifs de la suite des réduites, qui converge vers $\ell$. Par conséquent, $x=\ell$.
* $F\circ L$ est l'identité : voir l'exercice lié.

### Meilleure approximation

Une meilleure approximation d'un irrationnel $x$ est un couple $(p,q)\in \mathbb {Z} \times \mathbb {N} ^{*}$ vérifiant :
    $\left|q'x-p'\right|>|qx-p|$ pour tout couple d'entiers $\left(p',q'\right)$ tel que $1\leq q'\leq q$ et $\left(p',q'\right)\neq (p,q)$.

#### Remarque

    La fraction $p/q$ approche alors mieux $x$, au sens ordinaire (plus faible que celui de la définition), que toute autre fraction de dénominateur plus petit, car
    si $q'\leq q$ et $\left|q'x-p'\right|>|qx-p|$ alors $\left|x-p'/q'\right|>|x-p/q|$.
Les meilleures approximations d'un irrationnel sont ses réduites.
Soient $h_{n}/k_{n}$ les réduites d'un irrationnel $x$. Excluons le cas litigieux signalé en note, donc considérons une fraction $h/k$ telle que $k_{n}\leq k<k_{n+1}$ et montrons que si $(h,k)\neq (h_{n},k_{n})$ alors $|kx-h|>|k_{n}x-h_{n}|$. Cela prouvera que $h/k$ est une meilleure approximation de $x$ si et seulement si $(h,k)=(h_{n},k_{n})$.
Les deux entiers
    $u:=(-1)^{n+1}(k_{n+1}h-h_{n+1}k)\quad {\rm {et}}\quad v:=(-1)^{n}(k_{n}h-h_{n}k)$
vérifient :
    $h_{n}u+h_{n+1}v=h\quad {\rm {et}}\quad k_{n}u+k_{n+1}v=k$.
D'après la seconde équation, $u\neq 0$ et $uv\leq 0$.
* Si $v=0$ alors $(h,k)=u(h_{n},k_{n})$, avec nécessairement $u>1$, donc $|kx-h|>|k_{n}x-h_{n}|$.
* Si $v\neq 0$ alors $u(k_{n}x-h_{n})$ et $v(k_{n+1}x-h_{n+1})$ sont non nuls et de même signe. Comme leur somme vaut $kx-h$, on a bien $|kx-h|=|u(k_{n}x-h_{n})|+|v(k_{n+1}x-h_{n+1})|>|k_{n}x-h_{n}|$.

## Fraction continue d'un irrationnel quadratique

Un irrationnel quadratique est un nombre réel algébrique de degré 2.
Un irrationnel est quadratique si et seulement si son développement en fraction continue est périodique à partir d'un certain rang.
Pour un tel développement, on introduit la notation suivante :
$\left[a_{0},a_{1},\dots ,a_{r-1},{\overline {a_{r},a_{r+1},\dots a_{r+p-1}}}\right]:=\left[a_{0},a_{1},\dots ,a_{r-1},a_{r},a_{r+1},\dots ,a_{r+p-1},a_{r},a_{r+1}\dots \right]$.
Le développement en fraction continue d'un irrationnel quadratique $x$ est purement périodique (c'est-à-dire $x=\left[{\overline {a_{0},a_{1},\dots ,a_{p-1}}}\right]$) si et seulement si
    $x>1$ et $-1<x'<0$,
où $x'$ désigne le conjugué de $x$, c'est-à-dire l'autre racine de son polynôme minimal.
De plus, dans ce cas, $-{\frac {1}{x'}}=\left[{\overline {a_{p-1},\dots ,a_{1},a_{0}}}\right]$.
Un irrationnel est la racine carrée d'un rationnel $>1$ si et seulement si son développement en fraction continue est de la forme $\left[a_{0},{\overline {a_{1},a_{2},a_{3}\dots ,a_{3},a_{2},a_{1},2a_{0}}}\right]$.