Voir la source de Fraction continue d'un irrationnel quadratique

[[Fichier:Joseph Louis Lagrange.jpg|thumb|[[Joseph-Louis Lagrange]] établit de manière rigoureuse les propriétés des fractions continues des [[irrationnel quadratique|irrationnels quadratiques]].]]

En [[mathématiques]], et plus précisément en [[arithmétique]], la '''[[fraction continue]] d'un [[irrationnel quadratique]]''' correspond à la représentation de ce nombre sous la forme

:<math>a_0+\cfrac1{a_1+\cfrac1{a_2+\frac1{a_3+\,\cdots}}}\quad\text{avec}\quad a_0\in\Z\quad\text{et}\quad\forall i \ge 1\quad a_i\in\N</math>.

Si le [[nombre irrationnel]] représenté est quadratique, c'est-à-dire s'il est solution d'une [[équation du second degré]] à coefficients [[nombre rationnel|rationnels]], alors la [[suite d'entiers]] (''a<sub>n</sub>'') est  [[Suite périodique|périodique]] à partir d'un certain rang.

L'intérêt de l'étude de la fraction continue d'un irrationnel quadratique ne se résume pas à cela. La simplicité de l'algorithme permettant de déterminer les coefficients de la fraction en a  fait pendant longtemps une méthode d'extraction de [[racine carrée]]. La connaissance de la fraction continue permet, aussi, entre autres, de résoudre la célèbre [[équation diophantienne]] dite [[équation de Pell-Fermat|de Pell-Fermat]] : {{nobr|''x''{{2}} – ''ny''{{2}} {{=}} ±1}}.

== Préambule ==
=== Introduction sur un exemple ===
On cherche à calculer la fraction continue de {{racine|13}}, qui vaut environ 3,605 et un irrationnel quadratique, car solution de l'équation {{nobr|''x''{{2}} – 13 {{=}} 0}}. Pour calculer la fraction continue, on utilisera l'[[identité remarquable]] {{nobr|(''a'' + ''b'')(''a – b'') {{=}} ''a''{{2}} – ''b''{{2}}}} à chaque étape :
:<math>\sqrt{13}=3+(-3+\sqrt{13})=3+\frac{(\sqrt{13}-3)(\sqrt{13}+3)}{\sqrt{13}+3}=3+\frac4{3+\sqrt{13}}=3+\frac1{\frac{\sqrt{13}+3}4}</math>

et
:<math>a_0=3,~x_1=\frac{\sqrt{13}+3}4</math>.

En appliquant le même algorithme sur ''x''<sub>1</sub> :
:<math>\frac{\sqrt{13}+3}4=1+\frac{\sqrt{13}-1}4=1+\frac1{\frac{\sqrt{13}+1}3}\quad\text{donc}\quad\sqrt{13}=3+\cfrac1{1+\cfrac1{\frac{\sqrt{13}+1}3}}</math>

et ainsi :
:<math>a_1=1,~x_2=\frac{\sqrt{13}+1}3.</math>

On calcule de la même façon <math>x_3</math> :
:<math>\frac{\sqrt{13}+1}3=1+\frac1{\frac{\sqrt{13}+2}3}\quad\text{donc}\quad\sqrt{13}=3+\cfrac1{1+\cfrac1{1+\frac1{\frac{\sqrt{13}+2}3}}}\quad\text{et}\quad a_2=1,~x_3=\frac{\sqrt{13}+2}3.</math>

on continue ainsi et on calcule les termes suivant du développement jusqu'à <math>x_6</math> : 
:<math>x_3=\frac{\sqrt{13}+2}3=1+\frac1{1+\frac1{6+\frac1{\frac{\sqrt{13}+3}4}}}</math> 

enfin :
<math>a_3=1,~a_4=1,~a_5=6,~x_6=\frac{\sqrt{13}+3}4.</math>

Le vocabulaire et les notations utilisés ici sont ceux définis dans l'article « [[Fraction continue]] » : le '''quotient partiel''' ''a<sub>n</sub>'' est la [[partie entière]] du '''quotient complet''' ''x<sub>n</sub>'', sa [[partie fractionnaire]] étant 1/''x''{{ind|''n''+1}}. La '''réduite d'indice ''n'' '''désigne la fraction continue tronquée contenant ''n'' barres de fraction et construite à l'aide de ''n'' + 1 coefficients ; elle est notée ''h<sub>n</sub>''/''k{{ind|n}}''. Si l'on remplace ''a''<sub>''n''–1</sub> par ''a''<sub>''n''–1</sub>&nbsp;+&nbsp;1/''x<sub>n</sub>'' dans l'expression de la réduite d'indice ''n'' – 1, on obtient exactement le nombre initial. Le quotient complet ''x''<sub>0</sub> est la valeur initiale.

Dans l'exemple choisi,
:<math>x_0=\sqrt{13}=3+\cfrac1{1+\cfrac1{1+\cfrac1{1+\frac1{1+\frac1{6+\cdots}}}}}\quad{\rm et}\quad\frac{h_0}{k_0}=\frac31,~\frac{h_1}{k_1}=\frac41,~\frac{h_2}{k_2}=\frac72,~\frac{h_3}{k_3}=\frac{11}3,~\frac{h_4}{k_4}=\frac{18}5,~\frac{h_5}{k_5}=\frac{119}{33}</math>.

Cette notation étant un peu lourde, on utilise de préférence la suivante, ayant la même signification :
:<math>\sqrt{13}=[3,1,1,1,1,6 \cdots]</math>.

Enfin, le quotient complet <math>x_6</math> est égal à <math>x_1</math>, ce qui permet de conclure que la suite des coefficients se répète à partir du rang 1. On parle de suite « périodique à partir d'un certain rang » et l'on utilise la notation :
:<math>\sqrt{13}=[3,\overline{1,1,1,1,6}]</math>,

la barre signifiant une répétition à l'infini de la [[n-uplet|suite finie]] d'[[Entier naturel|entiers]] qu'elle couvre.

=== Éléments d'histoire ===
[[Fichier:Pierre de Fermat.png|thumb|[[Pierre de Fermat]] est à l'origine du défi lancé aux mathématiciens qui est à l'origine d'un large développement du savoir sur les fractions continues des irrationnels quadratiques.]]
Dès le {{VIe siècle}}, [[Aryabhata]] <small>([[476]]-[[550]])</small>, un mathématicien [[mathématiques indiennes|indien]], utilise les fractions continues pour obtenir des rationnels proches de racines carrés d'entiers<ref>[[Georges Ifrah]], ''Histoire universelle des chiffres : L'intelligence des hommes racontée par les nombres et le calcul'', Robert Laffont, 1994 {{ISBN|978-2-70284212-6}}.</ref>{{refinc}}. Si [[Brahmagupta]] <small>([[598]]-[[668]])</small>, un autre mathématicien indien, s'intéresse à l'équation de Pell-Fermat et utilise [[identité de Brahmagupta|une identité remarquable]] pour la résoudre, il faut attendre le {{XIIe siècle}} et [[Bhāskara II]] pour voir une approche analogue à celles des fractions continues appliquées à cette équation. Son algorithme, la [[méthode chakravala]], correspond à celui de l'article, à la différence près que ''a''<sub>0</sub> n'est pas toujours inférieur au nombre à approcher. Cette différence est reportée à tous les coefficients ''a<sub>n</sub>'', qui peuvent devenir négatifs. Cette spécificité accélère un peu la recherche de la solution.

Ce n'est que plus tard que l'Europe s'intéresse à une démarche de cette nature. Il faut attendre le {{s-|XVI}} pour que [[Rafael Bombelli]] fasse usage d'un ancêtre des fractions continues pour le calcul d'approximations de la [[racine carrée]] de 13<ref>{{Article|lang=it|auteur=M. T. Rivolo|auteur2=A. Simi|titre=Il calcolo delle radici quadrate e cubiche in Italia da Fibonacci a Bombelli|revue=[[Archive for History of Exact Sciences|Arch. Hist. Exact Sci.]]|vol=52|numéro=2|année=1998|p.=161-193}}.</ref>. [[Pietro Antonio Cataldi]] comprend la portée de la méthode de Bombelli et l'applique à toutes les racines carrées, dans un petit opuscule à ce sujet<ref>{{Article|lang=it|auteur=S. Maracchia|titre=Estrazione di radice quadrata secondo Cataldi|revue=Archimede|vol=28|numéro=2|année=1976|p.=124-127}}.</ref>, il choisit l'exemple de la valeur 18. On retrouve des résultats de même nature chez [[Albert Girard]]<ref>{{en}} [[Leonard Eugene Dickson]], ''Diophantine analysis'', AMS Bookstore, 1999 {{ISBN|0821819356}}, {{p.|355-356}}, {{Google Livres|eNjKEBLt_tQC|page=355|aperçu}}.</ref> en 1625, puis 1634, pour approcher {{racine|2}} et {{racine|10}}.

À la suite d'un défi lancé par [[Pierre de Fermat]] en 1657, [[William Brouncker]], trouve de manière empirique les relations qui relient la fraction continue d'un irrationnel quadratique à l'équation de Pell-Fermat. Il est probable que [[Bernard Frénicle de Bessy]] connaissait aussi cette méthode pour résoudre l'équation de Pell-Fermat dont il trouve toutes les solutions pour ''n'' plus petit que 150, mais ces travaux ont été perdus ; il défie Brouncker de trouver une solution à l'équation pour ''n'' = 313. Dans sa réponse, ce dernier indique qu'il ne lui a pas fallu « plus d'une heure ou deux pour la trouver ». Cette réponse est la suivante :

:<math>x= 32\,188\,120\,829\,134\,849 \quad \text{et} \quad y = 1\,819\,380\,158\,564\,160\;</math>

Ces informations proviennent d'une intense relation épistolaire entre les différents acteurs, qui est finalement publiée par [[John Wallis]] en 1658<ref>{{la}} John Wallis, ''Commercium epistolicum de quæstionibus quibusdam mathematicis nuper habitum'' Oxonii : Excudebat A. Lichfield, Impensis Tho. Robinson, 1658.</ref>.

Le siècle suivant est celui des démonstrations. [[Leonhard Euler]] reprend les travaux de Brouncker et ceux de Wallis, et démontre rigoureusement tous les aspects un peu élémentaires de la théorie ; il montre aussi que si la représentation en fraction continue d'un nombre est périodique, à partir d'un certain rang, alors ce nombre est un irrationnel quadratique<ref name="Euler">{{la}} Leonhard Euler, ''[[Introductio in analysin infinitorum]]'', 1748, vol. I (E101), chap. 18, § 379 {{Lire en ligne|url=http://eulerarchive.maa.org//docs/originals/E101capitel16.18.pdf}}.</ref>. Il faut encore attendre les travaux de [[Joseph-Louis Lagrange]] pour la démonstration d'une réciproque<ref name=TheoLagrange>Joseph-Louis Lagrange, ''Additions au mémoire sur la résolution des équations numériques, § II. — Sur la manière d'approcher de la valeur numérique des racines des équations'', 1770,  rééd. {{Ouvrage |prénom1=Joseph-Alfred |nom1=Serret |lien auteur1=Joseph-Alfred Serret |titre=Œuvres de Lagrange |volume=II |éditeur=[[Gauthier-Villars]] |année=1877 |passage=593-652 |lire en ligne=http://math-doc.ujf-grenoble.fr/cgi-bin/oeitem?id=OE_LAGRANGE__2_581_0}}, plus précisément : [https://gallica.bnf.fr/ark:/12148/bpt6k215570z/f604.image Remarque II, p. 603-622].</ref> ainsi que des raisons de la validité de la méthode Bhāskara II ou de celle de Brouncker<ref>Divers résultats sont publiés dans les ''Additions'' de Lagrange aux ''Élémens d'algèbre par Léonard Euler, tome 2 : de l'analyse indéterminée'', [https://gallica.bnf.fr/ark:/12148/bpt6k123306p {{1e}} éd., Bruyset et Desaint, 1774, p. 379-658 + 662-664] et [https://books.google.fr/books?id=NFWMxC1Kt7IC {{2e}} éd., Bruyset, 1798, p. 379-662 + 666-668], réédités dans : {{Harvsp|Serret|1877|loc=''Œuvres de Lagrange'', vol. VII, [https://gallica.bnf.fr/ark:/12148/bpt6k2299428/f7 {{p.|5-180}}]}}. Voir aussi {{Harvsp|Serret|1877|loc=''Œuvres de Lagrange'', vol. I, p. 671-731}}, « [http://gdz.sub.uni-goettingen.de/no_cache/dms/load/img/?IDDOC=41029 Solution d'un problème d'arithmétique] ».</ref>. Les propriétés de la fraction continue d'un irrationnel quadratique sont alors essentiellement élucidées ; il ne reste plus qu'à comprendre dans quel cas une fraction continue n'est pas simplement périodique à partir d'un certain rang, mais périodique pure, ce qu'[[Évariste Galois]] accomplit en 1828<ref name=Galois>{{Article|prénom=Évariste|nom=Galois|titre=Démonstration d'un théorème sur les fractions continues périodiques|revue=[[Annales de mathématiques pures et appliquées]]|vol=19|année=1828-1829|p.=294-301|url=http://www.bibnum.education.fr/mathematiques/algebre/demonstration-d-un-theoreme-sur-les-fractions-continues-periodiques}} sur [[bibnum]], analysé par Norbert Verdier, Christian Gérini et Alexandre Moatti.</ref>.

== Période ==
Tout irrationnel dont le développement en fraction continue est périodique est un irrationnel quadratique (''a fortiori'', ses quotients complets aussi). 
;Exemple
:L'irrationnel <math>x=[0,1,1,2,1,2,1,2,\dots]=[0,1,\overline{1,2}]</math> est égal à <math>0+\frac1{1+\frac1y}=\frac y{y+1}</math> avec <math>y=[\overline{1,2}]=1+\frac1{2+\frac1y}</math>.
:En remplaçant <math>y</math> par <math>\frac x{1-x}</math> dans cette équation puis en la simplifiant, on trouve <math>3x^2-1=0</math>.

Cette implication est au cœur de l'intérêt de la notion de fraction continue pour les irrationnels quadratiques car (plus d'un siècle après sa découverte) Lagrange a réussi à démontrer la réciproque :

{{Théorème|Théorème de [[Joseph-Louis Lagrange|Lagrange]]<ref name=TheoLagrange/>{{,}}<ref>Pour une démonstration, voir par exemple {{Ouvrage |langue=de |auteur1=[[Oskar Perron]] |titre=Die Lehre von den Kettenbrüchen |éditeur=Teubner |année=1913 |lire en ligne=https://archive.org/stream/dielehrevondenk00perrgoog#page/n88/mode/2up}}, § 20 ({{p.|73-77}}) ou § 21 ({{p.|77-79}}), ou {{Note autre projet|Wikiversité|Introduction à la théorie des nombres/Exercices/Approximation diophantienne et fractions continues#Exercice 2-7|cet exercice corrigé de la leçon « Introduction à la théorie des nombres »|début=}}</ref>|Un irrationnel est quadratique si ''et seulement si'' son développement en fraction continue est périodique à partir d'un certain rang.}}

Lagrange a même prouvé que pour un irrationnel quadratique de la forme (''P'' + {{sqrt|''D''}})/''Q'', les quotients partiels ''a{{ind|i}}'' sont majorés par 2{{sqrt|''D''}} et la période par 2''D''. Des arguments plus fins<ref>{{Article|lang=en|auteur=Dean R. Hickerson|titre=Length of period of simple continued fraction expansion of {{sqrt|''d''}}|revue=[[Liste des journaux scientifiques en mathématiques#P|Pacific J. Math.]]|vol=46|année=1973|p.=429-432|doi=10.2140/pjm.1973.46.429}}.</ref>{{,}}<ref>{{Article|lang=en|auteur=J. H. E. Cohn|titre=The length of the period of the simple continued fraction of ''d''{{exp|1/2}}|revue=Pacific J. Math.|vol=71|numéro=1|année=1977|p.=21-32|url=http://projecteuclid.org/euclid.pjm/1102811631}}.</ref>{{,}}<ref>{{Article|lang=en|auteur=E. V. Podsypanin|titre=Length of the period of a quadratic irrational|revue=Journal of Soviet Mathematics|vol=18|année=1982|p.=919-923|doi=10.1007/BF01763963|numéro=6}}.</ref>, basés sur la [[fonction diviseur]], montrent que cette période est un [[grand O]] de {{sqrt|''D''}} {{math|[[Logarithme|log(''D'')]]}}.

== Développement purement périodique ==
La ''p''-périodicité à partir d'un rang ''r'' du développement d'un irrationnel quadratique ''x'' s'écrit, avec la même notation que dans le préambule :

:<math>x=[a_0,a_1,\cdots,a_{r-1},a_r,a_{r+1},\cdots a_{r+p-1},a_r, a_{r+1}\cdots \;]=[a_0, a_1,\cdots,a_{r-1},\overline{a_r, a_{r+1},\cdots a_{r+p-1}}]</math>.

Certains nombres possèdent un développement purement périodique, c'est-à-dire dès le premier coefficient (''r'' = 0). C'est le cas, par exemple, du [[nombre d'or]] φ. En effet,

:<math>\varphi=1+\frac1{\varphi}=1+\frac1{1+\frac1{\varphi}}=\cdots\quad\text{et}\quad\varphi=[1,1,1,\cdots]=[\overline1]</math>.

La question se pose de savoir dans quel cas le développement en fraction continue est périodique pur. Le nombre ''x'' est nécessairement un irrationnel quadratique donc son [[Polynôme minimal (théorie des corps)|polynôme minimal]] est de degré 2. La réponse — prouvée par Galois (alors qu'il était encore lycéen) mais déjà implicite dans le travail antérieur de Lagrange<ref>{{Ouvrage |langue=en |auteur1=[[Harold Davenport]] |titre=The Higher Arithmetic |sous-titre=An Introduction to the Theory of Numbers |éditeur=[[Cambridge University Press]] |année=1999 |numéro d'édition=7 |pages totales=241 |passage=99 |isbn=978-0-521-63446-5 |lire en ligne={{Google Livres|pGDckKsed3EC|page=99}}}}.</ref> — s'exprime en fonction du [[Entier quadratique#Conjugué et norme|conjugué]] ''x<sub>c</sub>'' de ''x'', qui est l'autre racine de son polynôme minimal :

{{Théorème|Théorème de [[Évariste Galois|Galois]]<ref name=Galois/>{{,}}<ref>Pour une démonstration, voir par exemple {{Harvsp|Perron|1913|p=80-82}}, ou {{Note autre projet|Wikiversité|Introduction à la théorie des nombres/Exercices/Approximation diophantienne et fractions continues#Exercice 2-8|cet exercice corrigé de la leçon « Introduction à la théorie des nombres »|début=}}</ref>|2=Si ''x'' a un développement en fraction continue purement périodique <math>x = [\overline{a_0, a_1, \ldots , a_{p-1}}]</math> alors son conjugué ''x{{ind|c}}'' vérifie 
<math>-1/x_c = [\overline{a_{p-1}, \ldots , a_1, a_0}]</math>. En particulier ''x'' est un irrationnel quadratique réduit, c'est-à-dire que {{nobr|''x'' > 1}} et {{nobr|–1 < ''x{{ind|c}}'' < 0}}.

Réciproquement, le développement en fraction continue de tout irrationnel quadratique réduit est purement périodique.}}

== Palindrome ==
La propriété précédente permet d'obtenir une description plus précise du développement en fraction continue d'une racine d'un rationnel non [[carré parfait|carré]] :
{{Théorème|Théorème de [[Adrien-Marie Legendre|Legendre]]<ref>Ce théorème est attribué à Legendre dans {{Ouvrage |langue=en |auteur1=[[Kiyoshi Itō]] |titre=Encyclopedic Dictionary of Mathematics |volume=1 |éditeur=[[MIT Press]] |année=1993 |numéro d'édition=2 |pages totales=1147 |passage=315-316 |isbn=978-0-262-59020-4 |lire en ligne={{Google Livres|WHjO9K6xEm4C|page=315}}}}. Cependant, {{Ouvrage |prénom1=A. M. |nom1=Legendre |titre=Essai sur la théorie des nombres |année=1798 |passage=50-57 |lire en ligne=https://archive.org/details/essaisurlathor00lege}} (de même que {{Harvsp|Davenport|1999|p=104}}) ne s'intéresse qu'au cas où {{math|''d''}} est entier, et ne démontre que le sens direct. Pour une démonstration complète, voir par exemple {{Harvsp|Perron|1913|p=87-88}}, ou {{Note autre projet|Wikiversité|Introduction à la théorie des nombres/Exercices/Approximation diophantienne et fractions continues#Exercice 2-9|cet exercice corrigé de la leçon « Introduction à la théorie des nombres »|début=}}</ref>|Si ''d'' > 1 est un rationnel non carré, la fraction continue de {{sqrt|''d''}} est de la forme

:<math>\sqrt d = [a_0, \overline{a_1, a_2, a_3 \cdots,a_3,a_2,a_1, 2a_0}]</math>.

Réciproquement, tout irrationnel dont la fraction continue est de cette forme est la racine carrée d'un rationnel.}}

Le [[palindrome]] que forme alors la période privée de son dernier terme 2''a''<sub>0</sub> a un terme médian si et seulement si cette période est de longueur paire. Par exemple<ref>{{MathWorld|nom_url=PeriodicContinuedFraction|titre=Periodic Continued Fraction}}.</ref>,  [[#Introduction sur un exemple|{{sqrt|13}} = [3, {{surligner|1, 1, 1, 1, 6}}]]] et  {{sqrt|19}} = [4, {{surligner|2, 1, 3, 1 ,2, 8}}].

La liste des développements en fraction continue des racines carrées des nombres de 2 à 165 est donnée dans<ref>{{Ouvrage|auteur1=Marc Guinot|titre=Arithmétique pour amateurs ; Une époque de transition, Lagrange et Legendre|tome=4|éditeur=Aléas|année=1996|passage=327}}</ref>. La liste des longueurs des périodes de ces développements est donnée dans {{OEIS2C|A003285}}.

== Équation de Pell-Fermat ==
=== Structure de la solution ===
La fraction continue est une technique à la fois théorique et pratique pour résoudre l'[[équation de Pell-Fermat]] suivante, si ''d'' est un entier positif non carré :

:<math>(1)\quad x^2-dy^2=\pm1</math>.

Une solution est un couple (''a'', ''b'') d'entiers tel que ''a''{{2}} – ''db''{{2}} soit égal à ±1. À part les solutions triviales (1, 0) et (–1, 0), toutes se déduisent de celles pour lesquelles ''a'' et ''b'' sont strictement positifs, en changeant le signe de ''a'' [[Disjonction logique|ou]] ''b''. Trois propositions permettent ensuite de comprendre comment se structurent les solutions<ref>{{Harvsp|Perron|1913|p=102-104}}. {{Note autre projet|Wikiversité|Introduction à la théorie des nombres/Exercices/Approximation diophantienne et fractions continues#Exercice 2-6|cet exercice corrigé de la leçon « Introduction à la théorie des nombres »|début=La première propriété est aussi démontrée dans}} Les deux autres seront généralisées et démontrées au § suivant.</ref> :

{{énoncé|2=* Tout couple d'entiers strictement positifs solution de l'équation (1) est égal au couple du numérateur et du dénominateur de l'une des réduites de {{racine|''d''}}.
* La ''i''-ème réduite de {{racine|''d''}} correspond à une solution de l'équation (1) si et seulement si ''i'' + 1 est divisible par la période de {{racine|''d''}}.
* Si cette période ''p'' est impaire, il existe des solutions pour la valeur –1 : elles correspondent aux indices ''i = qp'' – 1 pour ''q'' impair, ceux pour ''q'' pair donnant la valeur 1. Si la période ''p'' est paire, la valeur –1 n'est jamais atteinte.}}Des exemples de solutions sont données dans "[[Équation_de_Pell-Fermat#Fraction_continue]]".

=== Groupe des unités ===
{{Article détaillé|Groupe des unités d'un anneau d'entiers quadratiques}}
En [[théorie algébrique des nombres]], il est parfois important de connaître la structure du [[groupe des unités]] d'un anneau d'[[entier algébrique|entiers algébriques]]. Cette situation se produit en particulier pour les anneaux d'entiers quadratiques. La compréhension de cette structure est utile, par exemple, pour [[démonstrations du dernier théorème de Fermat#Entier quadratique|démontrer le dernier théorème de Fermat pour ''n'' = 3 ou 5]], ou pour établir la loi d'apparition des [[Nombre premier|nombres premiers]] dans la [[suite de Fibonacci]] (cf. « [[Anneau des entiers de Q(√5)|Anneau des entiers de ℚ({{racine|5}})]] »).

On est amené à chercher les éléments inversibles de l'anneau ℤ[ω] qui sont de la forme ''a'' + ''b''ω où ω est un [[entier quadratique]] et ''a'' et ''b'' des éléments de ℤ. On montre que cela revient à résoudre une des deux équations diophantiennes suivantes, où ''d'' est un entier non carré parfait et ''f'' un entier tel que 4''f'' + 1 n'est pas un carré parfait :

:<math>(1)\;x^2-dy^2=\pm1\quad(2)\;x^2+xy-fy^2=\pm 1</math>.

La première pour ''d'' > 0 a déjà été étudiée. Puisque les solutions ''a + b{{sqrt|d}}'' avec ''a'' et ''b'' > 0 sont [[Groupe des unités d'un anneau d'entiers quadratiques#Généralités|données, par ordre croissant des ''a'', par les puissances de l'unité fondamentale]] ''h''{{ind|''p''–1}} + ''k''{{ind|''p''–1}}''{{sqrt|d}}'' (où ''p'' est la période de ''{{sqrt|d}}'') et sont aussi, d'après ce qui précède, les ''h''{{ind|''qp''–1}} + ''k''{{ind|''qp''–1}}''{{sqrt|d}}'' (pour ''q'' > 0), on a<ref>{{Harvsp|Perron|1913|p=104}}, le démontre directement, à l'aide des formules de récurrence sur les réduites et du fait que [[#Palindrome|''a{{ind|p}}'' = 2''a''{{ind|0}}]].</ref> ''h''{{ind|''qp''–1}} + ''k''{{ind|''qp''–1}}''{{sqrt|d}}'' = (''h''{{ind|''p''–1}} + ''k''{{ind|''p''–1}}''{{sqrt|d}}''){{exp|''q''}}, ce qui offre un moyen de calculer directement cette [[sous-suite]] des réduites de ''{{sqrt|d}}'', par la [[formule du binôme]] ou par récurrence.

La deuxième pour ''f'' > 0 est très similaire. {{refsou|date=mai 2014|On dispose d'abord d'un analogue de la première des trois propriétés du § précédent :}}

{{énoncé|2=Si ''d'' = 4''f'' + 1 et si le couple d'entiers (''a'', ''b''), avec ''b'' > 0 et ''a'' + ''b''/2 ≥ 0, est solution de l'équation (2), alors ''a''/''b'' est une réduite de <math>\alpha:=\frac{\sqrt d-1}2</math>.
}}

{{Démonstration/début}}
Soit <math>\omega=\frac{1+\sqrt d}2</math>.
:<math>(x+\omega y)(x-\alpha y)=\left(x +\tfrac y2+\sqrt d\tfrac y2\right)\left(x +\tfrac y2-\sqrt d\tfrac y2\right)=\left(x +\tfrac y2\right)^2-d\left(\tfrac y2\right)^2=x^2+xy+\frac{1-d}4y^2</math>
donc l'équation (2) s'écrit :

:<math>\left(x+\tfrac y2\right)^2-d\left(\tfrac y2\right)^2=(x + \omega y)(x-\alpha y)=\pm1</math>.

Soit (''a'', ''b'') un couple solution tel que ''b'' ≥ 1 et ''a'' + ''b''/2 ≥ 0, on obtient d'une part

:<math>\left(\frac ab + \omega\right)\left(\frac ab-\alpha\right) = \frac {\pm 1}{b^2}\quad\text{donc}\quad \left|\frac ab-\alpha\right| = \frac 1{b^2 \left(\frac ab + \omega\right)}</math>

et d'autre part

:<math>\tfrac ab+\omega=\tfrac ab+\tfrac12+\tfrac12\sqrt d\ge\frac12\left(\sqrt{d-\tfrac4{b^2}}+\sqrt d\right)</math>.

Le minorant de droite est généralement strictement supérieur à 2 et l'on obtient alors la majoration suivante, qui montre que ''a''/''b'' est une réduite de α :

:<math>\left|\frac ab-\alpha\right|<\frac1{2b^2}</math>.

La seule exception survient lorsque ''d'' = 5 et ''b'' = 1 :
{{Retrait|<math>\frac12\left(\sqrt{5-4}+\sqrt 5\right)<2</math>}}
mais dans ce cas, ''a'' est égal à 0 ou 1, or 0/1 et 1/1 sont bien des réduites de ({{sqrt|5}} – 1)/2 = [[Nombre d'or|φ]] – 1 = [0, {{Surligner|1}}].
{{Démonstration/fin}}

{{refsou|date=mai 2014|1=Les deux autres propriétés se généralisent comme suit<ref>{{Note autre projet|wikiversité|Introduction à la théorie des nombres/Devoir/Équation de Pell-Fermat|devoir corrigé sur l'équation de Pell-Fermat|début=Pour une démonstration, voir par exemple ce}}</ref>,}} donc s'appliquent aussi bien à α = {{sqrt|''d''}} que (si ''d'' est [[congruence sur les entiers|congru]] à 1 modulo 4) à α = ({{sqrt|''d''}} – 1)/2 :

{{énoncé|2=Soient α un entier quadratique (non entier) supérieur à son conjugué, ''p'' sa période et ''h<sub>i</sub>''/''k<sub>i</sub>'' ses réduites.
*[[Entier quadratique#Conjugué et norme|''N''(''h<sub>i</sub> – k<sub>i</sub>''α)]] = ±1 si et seulement ''i'' + 1 est divisible par ''p'' ;
*si ''p'' est impair, il existe des solutions pour la valeur –1 : elles correspondent aux indices ''i = qp'' – 1 pour ''q'' impair, ceux pour ''q'' pair donnant la valeur 1. Si ''p'' est pair, la valeur –1 n'est jamais atteinte.
}}

== [[Extraction de racine carrée|Extraction d'une racine carrée]] ==
=== Première méthode ===
Les propriétés de la fraction continue d'un irrationnel quadratique permettent de calculer des approximations des [[racine carrée|racines carrées]]. La première technique consiste simplement à calculer les coefficients de la fraction continue puis ses réduites. Par exemple :

:<math>\sqrt 3=[1,\overline{1,2}]</math><ref>En utilisant que <math>\frac1\sqrt3=[0,1,\overline{1,2}]</math> {{supra|Période}} ou par calcul direct, comme dans {{Note autre projet|wikiversité|Introduction_à_la_théorie_des_nombres/Exercices/Approximation_diophantienne_et_fractions_continues#Exercice_2-9|cet exercice corrigé|début=}}</ref>.

Les [[Fraction continue#Réduites d'une fraction continue|réduites ''h<sub>n</sub>''/''k<sub>n</sub>'' se calculent par récurrence]] :

:<math>\begin{align} h_{-1}=1,\quad & h_0=a_0,\quad & h_{n+2}= a_{n+2}h_{n+1}+h_n,\\ k_{-1}=0,\quad & k_0=1,\quad & k_{n+2}= a_{n+2}k_{n+1}+k_n,\end{align}</math>

ce qui donne les approximations suivantes de {{sqrt|3}} :

:<math>\begin{align}
h_0 &= 1,& h_1 &=2,&h_2 &= 2 \times 2 + 1 = 5,&h_3 &= 1 \times 5 + 2 = 7,&h_4 &= 19, & h_5 &= 26, &\cdots \, h_{10} &= 989\\
k_0 &= 1,&k_1 &=1,&k_2 &= 2 \times 1 + 1 = 3,&k_3 &= 1 \times 3 + 1 = 4,&k_4 &= 11, & k_5 &= 15, &\cdots \, k_{10} &= 571.
\end{align}</math>

Ainsi, à la {{10e|étape}}, on obtient la fraction 989/571, approximativement égale à 1,732 049 alors que les 7 premiers [[Chiffre significatif|chiffres significatifs]] exacts sont 1,732 051. La précision de cet algorithme à l'étape ''n'' est meilleure que 1/''k<sub>n</sub>''{{2}} (et même, puisqu'ici la période est 2, meilleure que 1/(2''k{{ind|n}}''{{2}}) si ''n'' est impair, d'après le [[#Structure de la solution|§ « Structure de la solution »]] ci-dessus). Pour l'approximation d'indice 10, on sait donc que l'erreur est inférieure à 1/571{{2}}, meilleure que le 300000{{e}}. Une force de cet algorithme est la « qualité » des solutions proposées, où toute fraction de type ''a''/''b'' avec ''b'' strictement inférieur à 571 sera nécessairement moins bonne que la dixième réduite de la fraction continue, au sens ci-dessus (et même en un sens plus fin, précisé dans l'article [[Fraction continue et approximation diophantienne]]). Par exemple, la meilleure approximation décimale de la racine de 3 avec deux chiffres significatifs, égale à 17/10, commet une erreur supérieure au {{50e}}. Celle un peu équivalente 19/11 correspondant à la réduite d'indice 4 propose une approximation au {{100e}}, soit deux fois meilleure.

=== Accélération de la convergence ===
Les solutions (''a{{ind|q}}'', ''b{{ind|q}}'') = (''h''{{ind|''qp''–1}}, ''k''{{ind|''qp''–1}}) de l'équation de Pell-Fermat donnent une suite extraite de la suite des réduites de ''{{sqrt|n}}'', qui converge donc plus vite que cette dernière. De plus, puisque [[#Groupe des unités|''a{{ind|q}} + b{{ind|q}}{{sqrt|n}}'' est de la forme (''a + b{{sqrt|n}}'')''{{exp|q}}'']], on peut accélérer encore la convergence en ne calculant que certaines de ces puissances, par exemple les ''u{{ind|j}} + v{{ind|j}}{{sqrt|n}}'' = (''a + b{{sqrt|n}}''){{exp|2{{exp|''j''}}}}. Puisque

:<math>u_{j+1}+v_{j+1}\sqrt n=(u_j+v_j\sqrt n)^2,</math>

cette sous-suite se calcule par récurrence par :

:<math>u_0=a,\quad v_0=b,\quad u_{j+1}=u_j^2+nv_j^2\quad\text{et}\quad v_{j+1}=2u_jv_j.</math>

Par exemple pour ''n'' = 3, on trouve ''a = h''{{ind|1}} = 2 et ''b = k''{{ind|1}} = 1 (cf. § précédent) puis

:<math>\begin{align}
u_0&= 2,&u_1&= 2^2 + 3\times 1^2 = 7,&u_2&= 7^2 + 3\times 4^2 = 97,&u_3&= 97^2 + 3\times 56^2 = 18\,817,&u_4&= 708\,158\,977 \\
v_0&= 1,&v_1&= 2\times 2\times 1 = 4,&v_2&= 2\times 7\times 4 = 56,&v_3&= 2\times 97\times 56 = 10\,864,&v_4&= 408\, 855\,776\end{align}</math>

et la précision de ''u''<sub>4</sub>/''v''<sub>4</sub> dépasse déjà 18 décimales.

La suite des rationnels ''x{{ind|j}} = u{{ind|j}}''/''v{{ind|j}}'' n'est autre que celle produite par la [[méthode de Héron]] à partir de ''x''{{ind|0}} = ''a''/''b''. En effet, d'après la définition des suites (''u{{ind|j}}'') et (''v{{ind|j}}''), on a

:<math>x_{j+1}=\frac{x_j+\frac n{x_j}}2</math>.

Sa convergence est donc [[Convergence quadratique|quadratique]].

== Un exemple historique de résolution de l'équation de Pell Fermat ==
L'équation suivante possède une longue histoire :

:<math>x^2-61y^2=1</math>.

Brahmagupta<ref>{{Article|lang=en|auteur=[[Bartel Leendert van der Waerden|B. L. van der Waerden]]|titre=Pell's Equation in Greek and Hindu Mathematics|revue={{Lien|Russian Mathematical Surveys|texte=Russ. Math Surveys}}|vol=31|numéro=5|année=1976|p.=210-225}}.</ref> l'utilise comme illustration d'un  ancêtre de la [[méthode chakravala]] dès le {{s-|VII}}. Il est repris par Bhāskara II qui perfectionne la méthode<ref>[[Bhāskara II]], ''Bijaganita'', 1150, d'après {{MacTutor|class=~history/HistTopics|id=Pell|title=Pell's equation}}.</ref> et lui donne une puissance [[algorithmique]] un peu supérieure à celle par les fractions continues, présentée ici. 

En  février [[1657]] (à la suite d'un autre défi plus célèbre datant du 3 janvier de la même année), l'exemple est encore repris par Pierre de Fermat dans une lettre à [[Bernard Frénicle de Bessy]] (il propose également le cas ''n'' = 109)<ref>''[https://archive.org/stream/oeuvresdefermat02ferm#page/334/mode/2up Œuvres de Fermat]'', {{p.|334}}.</ref>. Ce défi est à l'origine des travaux anglais sur les fractions continues des irrationnels quadratiques et leur connexion avec l'équation de Pell-Fermat.

Appliquons l'algorithme des fractions continues pour calculer les quotients complets et partiels :

:<math>x_0=\sqrt{61}=7+\frac1{x_1},\quad x_1=\frac{7+\sqrt{61}}{12}=1+\frac1{x_2},\quad x_2=\frac{5+\sqrt{61}}3=4+\frac1{x_3},</math>

:<math>\quad x_3=\frac{7+\sqrt{61}}4=3+\frac1{x_4},\quad x_4=\frac{5+\sqrt{61}}9=1+\cfrac1{x_5},\quad x_5=\frac{4+\sqrt{61}}5=2+\frac1{x_6},\quad x_6=\frac{6+\sqrt{61}}5,</math>

ce qui donne les premiers quotients partiels : 7, 1, 4, 3, 1, 2. Il n'est plus nécessaire de continuer. En effet, les quotients complets ''x''<sub>5</sub> et ''x''<sub>6</sub> sont associés car ils ont le même dénominateur. La moitié du palindrome est donc déjà explicitée. Comme ce phénomène se produit pour deux indices adjacents, on peut en déduire que la période est impaire et égale à 2×5 + 1. On peut aussi en déduire que ''a''<sub>6</sub> est égal à ''a''<sub>5</sub>, ainsi que les termes suivants : 2, 1, 3, 4, 1. Enfin, le dernier terme est égal au double du premier, soit 14. La première solution est alors celle d'indice 10, dont la position est mise en valeur en rouge dans l'expression suivante :

:<math>\sqrt{61}=[7,\overline{1,4,3,1,2,2,1,3,4,{\color{Red}1},14}]</math>.

Par les formules de récurrence (comme au [[#Première méthode|§ « Première méthode »]]), on obtient :

:<math>\begin{align}h_1&=8,&
h_2 &=39,&h_3 &=125,&h_4 &= 164,&\cdots&\, h_{10} &= 29\;718\\
k_1&=1,&k_2 &=5 ,&k_3 &=16,&k_4 &= 21,&\cdots&\, k_{10} &= 3\;805.
\end{align}</math>

On sait, puisque la période est impaire, que cette première solution donne ''h''{{ind|10}}{{2}} – 61''k''{{ind|10}}{{2}} = –1 et non pas +1. Ni Brahmagupta, ni Fermat n'acceptent ce type de solution. La bonne réduite est donc la {{21e}}. Pour la calculer, on peut soit prolonger le calcul, soit utiliser le même principe que celui de la deuxième méthode d'extraction d'une racine :

:<math>h_{21}+k_{21}\sqrt{61}=(h_{10}+k_{10}\sqrt{61})^2</math>.

La solution du défi de Fermat est :

:<math>h_{21}=1\,766\,319\,049,\quad k_{21}=226\,153\,980\quad\text{et}\quad h_{21}^2-61\times k_{21}^2=1</math>.

== Notes et références ==
{{Traduction/Référence|en|Periodic continued fraction|621452790|type=note}}
{{Références|colonnes=2}}

== Voir aussi ==
=== Bibliographie ===
* {{Ouvrage |langue=en |auteur1=[[Alan Baker]] |titre=A Concise Introduction to the Theory of Numbers |éditeur=Cambridge University Press |année=1985 |pages totales=95 |isbn=978-0-521-28654-1 |lire en ligne=https://books.google.com/books?id=hAFfb8BBC0IC&printsec=frontcover}}
* {{Ouvrage |nom1=Alain Faisant |titre=L'équation diophantienne du second degré |éditeur=[[Hermann (éditions)|Hermann]] |année=1991 |pages totales=237 |isbn=978-2-7056-1430-0}}
* Marc Guinot, ''Arithmétique pour amateurs. Vol. 4 : Lagrange et Legendre'', Aléas, 1996 {{ISBN|978-2-908016-71-0}}
* {{HardyWright}}
*{{Article|auteur=Alexandre Junod|lang=en|titre=An algorithm to solve a Pell equation|url=http://www.emis.de/journals/GMN/yahoo_site_admin/assets/docs/1_GMN-8492-V28N2.190180001.pdf|revue=General Mathematics Notes|vol=28|numéro=2|année=2015|p.=1-8}}
* {{Samuel1}}
* [[Georges Valiron]], ''Théorie des fonctions'', {{3e}} éd., [[éditions Masson|Masson]], 1966, Notions sur les fractions continues arithmétiques, {{p.|17-24}}
* {{Ouvrage |langue=fr |nom1=Sabah Al Fakir |titre=Algèbre et théorie des nombres - Cryptographie |sous-titre=Primalité |éditeur=[[Éditions Ellipses|Ellipses]] |lieu=Paris |année=2003 |pages totales=276 |isbn=2-7298-1480-9}} (chapitre 9, [[Approximation diophantienne|approximations diophantiennes]])

=== Liens externes ===
*{{Lien web|auteur=Claude Brezinski|année=2005|mois=octobre|titre=Ces étranges fractions qui n'en finissent pas|url=http://irem.univ-reunion.fr/IMG/pdf/Brezinski_fractions_continues.pdf}}, diaporama d'une [http://irem.univ-reunion.fr/spip.php?article7 conférence] à l'[[IREM]], [[Université de La Réunion]]
*{{Lien web|url=http://agreg-maths.univ-rennes1.fr/documentation/docs/fraccont.pdf|titre=Développement d’un réel en fractions continues|auteur=Marcel Couchouron|site=[[Université de Rennes I]]}}

{{Portail|arithmétique et théorie des nombres}}

[[Catégorie:Entier quadratique]]
[[Catégorie:Fraction continue]]