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

Début de la boite de navigation du chapitre

Soit $x$ un réel.

fin de la boite de navigation du chapitre

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à :

Début d’un théorème

Théorème

$\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}}}$.

Fin du théorème

Faites ces exercices : Exercice 2-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.

Démonstration

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é

Définition

• 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.

Faites ces exercices : la constante de Liouville et ses variantes.

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 :

Proposition

Faites ces exercices : Exercice 2-1.

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 :

Début d’un théorème

Théorème de Liouville (1844)

Si $x$ est algébrique de degré $d\geq 2$, alors sa mesure d'irrationalité est inférieure ou égale à $d$.

Fin du théorème

Démonstration

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

Définition

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.

Propriété

$\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$.

Détail de l'algorithme

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]$.

Faites ces exercices : Exercice 2-5.

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 :

Définition

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 :

Proposition

Faites ces exercices : Exercice 2-4.

${\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.

Proposition : convergence d'une fraction continue infinie vers un irrationnel

1. La suite $(h_{n}/k_{n})$ des réduites d'une fraction continue infinie simple $\left(a_{n}\right)$ converge.
2. 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}}}$.
3. $\ell$ est irrationnel.

Notation

Cette limite $\ell$ est notée $\left[a_{0},a_{1},\dots \right]$.

Démonstration

1. ${\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.
2. 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})}}$.

3. $\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}$.

 

Corollaire

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}}$

Démonstration

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 :

1. $\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}}}$ ;
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$.

 

Début d’un théorème

Théorème : bijection entre irrationnels et fractions continues infinies

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.

Fin du théorème

Démonstration

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é.

Faites ces exercices : fin de la preuve de bijection entre irrationnels et fractions continues infinies.

 

Meilleure approximation

Définition

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|$.

Début d’un théorème

Théorème

Les meilleures approximations d'un irrationnel sont ses réduites.

Fin du théorème

Démonstration

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

Définition

Un irrationnel quadratique est un nombre réel algébrique de degré 2.

Début d’un théorème

Théorème de Lagrange (1770)

Un irrationnel est quadratique si et seulement si son développement en fraction continue est périodique à partir d'un certain rang.

Faites ces exercices : Exercice 2-7.

Fin du théorème

Pour un tel développement, on introduit la notation suivante :

Notation

$\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]$.

Corollaire (Galois, 1829)

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]$.

Faites ces exercices : Exercice 2-8.

Corollaire (Legendre, 1798)

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]$.

Faites ces exercices : Exercice 2-9.