CHAPITRE VIII
FRACTIONS CONTINUELLES
84. Développement en fraction continuelle d'un nombre rationnel. — Soit un nombre rationnel s. Extrayons le plus grand entier contenu dans ce nombre, soit «o» de sorte que
s = ao-h Vi.
L'entier Oq peut être positif, négatif ou nul, suivant les cas Quant au nombre n il satisfait aux conditions
O < Ti < 1 .
Si /'i = o, c'est-à-dire si s est entier l'opération est finie. Sinon, en posant ri =~, le nombre Sj est plus grand que i. Extrayons le plus grand entier contenu dans 5i, soit a^ de sorte que
et, par suite :
ai + Ta L'entier a^ est positif, et le nombre Ta satisfait aux conditions : o< r2< I.
On pose )% = — et on continue de la même façon. Au bout de
A' 4- I opérations on a :
s = Oo -\
FRACTIONS CONTINUELLES IÔQ
Nous allons montrer qu'au bout d'un certain nombre d'opérations on arrivera à un r^a i qui sera nul. En efifet s étant rationnel
et égal à - (6, c entiers), les opérations qu'on fait pour déterminer
ûq, Oi, ... sont les mêmes que celles par lesquelles on détermine le plus grand commun diviseur de 6 et de c (I. 96). Ce sont des divisions, et on a vu qu'au bout d'un certain nombre /i de ces divisions il y en a une qui se fait exactement. Alors /'„j i = o et
tation
ai -\-
Nous emploierons la rotation
a,,, ai, ... a„ sont des entiers ; Oo peut» être un entier quelconque, mais ai, 02, ... an sont positifs ; an est plus grand que i, car si a«
était égal à i, on aurait a„ ,1 -t- ~ = «„i H- i, donc l'opération
aurait fini à la division précédente.
Un nombre rationnel ne peut se mettre sous la forme précédente, les a étant assujettis à toutes les conditions indiquées, que d'une seule manière. Si l'on n'assujettit pas le dernier a à être plus grand que 1, un nombre rationnel peut se mettre sous la Jorme précédente de deux manières.
En effet, de
il résulte
Oo < s < a.j + I. Donc tty est la partie entière de s, il est déterminé. Posant s = «g -h — on voit de même que «i est là partie entière de r,,, il est donc déterminé aussi, et ainsi de suite. On aboutit à
l60 THÉORIE DBS NOMBRES
Si a„ est assujetti à être plus grand que i , a„i est la partie entière de /•„j, donc il est déterminé et On aussi.
Mais sinon, on peut, ayant obtenu a„> i, le remplacer par
Il est important, comme on le verra plus loin, de remarquer que des deux façons de mettre s sous forme de fraction continuelle il y en a une où le nombre des a est pair, une où il est impair.
I*' Exemple — Reprenant l'exemple de I. 96, on voit que 72715^3 .!|î|±.
37210 II H- I 3 -h I 24
D'ailleurs le plus grand commun diviseur de 77716 et 37216 est 45, de sorte que ^'' t peut se réduire et l'on a
On a aussi
2* Exemple
ou
827 ^ii-h|3-i-|24'
827 II -h I 3 + 1 23 H- I I
3* Exemple
ou
Une expression de la forme précédente s'appellera une Jraction continuelle ; les entiers a s'appellent éléments ou quotients incomplets ; les nombres s s'appellent les quotients complets, les quotients complets et les incomplets sont tous plus grands que i sauf peutêtre le premier, et aussi le dernier quand on écrit la fraction continuelle de la seconde façon.
FRACTIONS CONTINUELLES
85. Fractions continuelles algébriques. Réduites. — Dans ce qui précède les éléments sont des entiers positifs à partir du second, le premier pouvant être positif, négatif ou nul, mais nous aurons avantage à étudier d'abord les expressions
OÙ les a seront des nombres quelconques, et que nous appellerons fractions continuelles algébriques. Celles où les éléments sont entiers seront dites arithmétiques. Celles où de plus ai, Oj, ... seront positifs, c'est-à-dire celles considérées tout d'abord, seront dites fractions continuelles ordinaires.
Donnons-nous une fraction continuelle a^
Qi
et
et cherchons à la calculer en calculant successivement
On a
en posant puis
en posant
-, ...ao-4-
Qo
Ol
on"
Po = ao. Qo = I
Pi
Pi = QoCi H" I
Qi = ai.
Supposons qu'on ail ainsi calculé a^ -f
p Je dis qu'on obtient q-^ en posant
Pfc+l = Ok+lP* H- Pfc— 1
Qa+1 = «fc+iQft •+■ Qk-i-
La loi se vérifiant pour k = o et i il suffit de la démontrer pour la valeur A; + i de l'indice en la supposant vraie jusqu'à la valeur k.
Câhen. ^ Théorie des nombres, t. II. ii
Par hypothèse
Oo
Ol
Or flo +
se déduit de l'expression pré-
Ol
cédente en y remplaçant a* par Ck -+- . Donc, puisque P*i,
Pfc 2. Qji-n Qfc-î ï*® dépendent pas de Ck on trouve :
(ok -+- i-^)P*-i ■+■ P*-J
afc-Li(afcPt-i H- Pfc-0 -h Pfc i qfc+iPjfcH- P^-i aii(+i(a*Qk-i H- Qfc-2) -+- Qk-i Ok+iQh -+- Qv-i
ce qu'il fallait démontrer.
P Les expressions iy se nomment les réduites de la fraction continuelle. La dernière est la valeur de la fraction continuelle ellemême.
Exemple. — Soit la fraction continuelle 2
On calcule directement les deux premières réduites
Po 3
Qo~ï
Pi
Qi
puis
Pj ^ 3 X 23+2 ^ 71^ Qo 3 X II -i- 1 34
Qa "~ 24 X 34 + 1 1 ~~ 827
Les réduites
et
Au lieu de calculer à part les deux
premières réduites de la fraction continuelle on peut les faire rentrer dans la formule générale en les faisant précéder de deux
réduites ,~ = - et p^ = -, les mêmes pour toutes les fractions Q 2 I Q i o' ^
continuelles. On a en efifet
Po = «0 = «oP-l + P-2
Qo = 1 = aoQ i + Q 2
FRACTIONS CONTINUELLES l63
Pi = ao^i + I = «iPo -+- P-i Qi = Oi = aiQo -H Q-i. '
Remarque. — Il peut se faire que l'une des réduites ainsi calculées n'ait pas de sens, son dénominateur étant nul, et que tout de même la fraction continuelle complète en ait un. Cela n'empêche pas les formules précédentes d'être applicables, puisqu'on y calcule séparément le numérateur et le dénominateur de chaque réduite.
Exemple. — Soit Oq H
— . Les réduites successives sont
— . - . — — — ; la seconde n'a pas de sens, la troisième est la valeur de la fraction continuelle.
Ce cas ne se présentera d'ailleurs jamais dans les fractions continuelles arithmétiques, et en général dans les fractions continuelles où l'on a ai > o, a^» Û3» ..• >• o ; car dans ces fractions, les dénominateurs des réduites sont tous positifs.
86, — En posant :
et, d'une façon générale, en appelant P(ao, ai, ... Uk) ce que nous avons appelé Pj^, on a :
Qo = I Qi = P(ai) ... Qk = PK, a„ ... a,).
D'ailleurs nous continuerons à employer les anciennes notations Pfc et Qk conjointement aux nouvelles.
Théorème. — On a :
P(ao, oi, ... Ofc) = ?(ai„ aA i, ... Qo).
Le théorème est évident pour k = o et k = i . Nous allons le démontrer pour la valeur k de l'indice en le supposant vrai pour les valeurs k — i et /c — 2.
l64 THÉORIE DES NOMBRES
On a
P(ao, au ... a^) = afcP(ao, ûi. ••• a;^-i) -+- P(«o. «i, .•• Ok-a) = a;^P(afc i, ... ai, Oo) + P(at-2, •■. Oi. «o)
= afc[aoP(a4 i,...ai)H-P(a,,i,. .Oa)] -4-aoP(aA-2,.--ai) + P(a*;-2.-..a2) = ao[akP(«fc i,...ai)-|-P(aA 2,...ai)] -+- aAP(afc i,...a2)-f-P(aA 2,...as) == ao[a;tP(ai,...aA.,) + P(ai,... 0^-2)] -^-aJlP(a2,...a^•-l);+P(a2.•..ai^-2) = aoP(ai, 02, ... a/,) -f- P(a2, ... a^) = aoP(aA, ... Oi) H- P(aji. ...02) = P{aA, ... Oo).
Généralisation des relations de récurrence du n" 86. Cherchons P^ en fonction de Pa 2 et P/,.3. Pour cela dans la formule
Pa = (^k^k-i ■+■ Pa-2
remplaçons P^ i par aA:iPi 2 ■+- Pa 3. Nous obtenons
Ph = (oaOa-i -+- i)Pa-2 -+- «aPa-s
ce qui peut s'écrire
P, = P(aA. a,OPA, + P(aA)PA 3.
On trouverait de même î
Vk = P(at. «A-i. aA-2)PA-3 -+- P(aA, aA-i)PA-* ce qui nous met sur la voie de la formule générale :
Pfc = P{ai,, a,,i, ... a/,r+i)PA r -+- P(a/;. OA-I, ••. afc-r4-2)Pfc-r l.
Pour démontrer cette formule il suffit de la supposer vraie pour la valeur r de l'indice r et de la démontrer pour la valeur r + i , ce qui est facile.
On démontrerait de même que
Qa = P(aA, «A-l. .-. Ok-r+ÔQk-r H" P(aA, «A-l, .•• «A-r+2)QA r-l.
87. — Théorème. On a, entre les termes de deux réduites consécutives, la relation
(1) PaQa-i-Pa-,Qa = (-0*-*-
Cette relation se vérifie immédiatement pour k=i. Il suffit donc de montrer que si elle est vraie pour la valeur k — i de l'indice elle est vraie aussi pour la valeur k. Or
P,Qa i — Pa iQ;c = (a,P,, + Pa 2)Qa-i - Pa-iKQ^-i + Qa-î) = - (Pa iQa-2 - Pv-2Qa-i) = (-!)*
FRACTIONS CONTINUELLES l65
Généralisalion. — On a
PfcQt-r — Pa-,Q* = (— i)*"'"P(aA, afc-i, ... flA-r+a). EnefiFet
PftQft-r — Pk-rQk = [P{ak, . '.ak-r+l)Pk-r -j- ^Qk, • • . Ok-r+iWk-r-i]Qk-r
— Pi r[P(aA,...afc r4l)QA-- + P(afc.---aA-r+2)Qft-r-l]
= (PA-r-lQA-r — PA-rQA-r-l)P(aA-,...a;i-r+2) = (— O'-^PK-at-r+î).
