mathématiques (PCSI) · Chapitre 1 · Exercice de TD

Problème — Le théorème de Lamé

Raisonnement et vocabulaire ensembliste · G. Divisibilité, division euclidienne, PGCD et PPCM · niveau 3 (difficile)

Énoncé

On note $(F_{n})_{n \in N}$ la suite de Fibonacci : $F_{0} = 0$ , $F_{1} = 1$ et $F_{n + 2} = F_{n + 1} + F_{n}$ pour tout $n \in N$ ; on pose $φ = \frac{1 + 5}{2}$ .

Pour deux entiers $a > b \geq 1$ , l'algorithme d'Euclide calcule $r_{0} = a$ , $r_{1} = b$ puis, tant que $r_{i} \neq = 0$ , le reste $r_{i + 1}$ de la division euclidienne de $r_{i - 1}$ par $r_{i}$ : $r_{i - 1} = q_{i} r_{i} + r_{i + 1}$ avec $0 \leq r_{i + 1} < r_{i}$ . On note $N (a, b)$ le nombre de divisions effectuées, c'est-à-dire l'indice $N$ tel que $r_{N} \neq = 0$ et $r_{N + 1} = 0$ .

1) Vérifier que $φ^{2} = φ + 1$ , puis montrer par récurrence double que $F_{n + 2} \geq φ^{n}$ pour tout $n \in N$ .

2) Soit $n \geq 1$ . Montrer que $N (F_{n + 2}, F_{n + 1}) = n$ et que $F_{n + 2} \land F_{n + 1} = 1$ . Vérifier sur le couple $(987, 610) = (F_{16}, F_{15})$ .

3) Soient $a > b \geq 1$ tels que $N (a, b) = n$ . Montrer, par récurrence sur $n \geq 1$ , que $b \geq F_{n + 1}$ et $a \geq F_{n + 2}$ . (Si $n \geq 2$ , l'algorithme se poursuit sur le couple $(b, r_{2})$ , avec $b > r_{2} \geq 1$ et $N (b, r_{2}) = n - 1$ ; et $a \geq b + r_{2}$ .)

4) En déduire que $N (a, b) \leq 1 + \frac{ln b}{ln φ}$ .

5) Écrire $φ^{5}$ sous la forme $u φ + v$ avec $u, v$ entiers, montrer que $φ^{5} > 10$ , et en déduire le théorème de Lamé : si $b$ s'écrit avec $k$ chiffres en base $10$ , l'algorithme d'Euclide effectue au plus $5 k$ divisions.

6) Montrer que la borne $5 k$ est atteinte pour $k = 1$ , $2$ et $3$ , mais qu'elle ne l'est pas pour $k = 4$ .

Corrigé de la question 1

Ce qu'on a le droit d'utiliser. La récurrence sous ses trois formes ; la division euclidienne, avec l'unicité du quotient et du reste ; le lemme d'Euclide ; la croissance du logarithme népérien. Les termes $F_{0}$ à $F_{21}$ sont $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946$ . On notera que $F_{n} \geq 1$ pour $n \geq 1$ , et que $F_{n + 1} = F_{n} + F_{n - 1} > F_{n}$ dès que $n \geq 2$ .

1) Le nombre d'or et la minoration de Fibonacci. On calcule $φ^{2} = \frac{1 + 2 5 + 5}{4} = \frac{6 + 2 5}{4} = \frac{3 + 5}{2}$ , et $φ + 1 = \frac{1 + 5 + 2}{2} = \frac{3 + 5}{2}$ : $φ^{2} = φ + 1$ .

Notons $A_{n}$ l'assertion « $F_{n + 2} \geq φ^{n}$ », et raisonnons par récurrence double.

Initialisation, deux rangs. $F_{2} = 1 = φ^{0}$ : $A_{0}$ est vraie. $F_{3} = 2$ et $φ < 2$ puisque $5 < 3$ : $A_{1}$ est vraie.

Hérédité. Soit $n \in N$ tel que $A_{n}$ et $A_{n + 1}$ soient vraies. Alors $F_{n + 4} = F_{n + 3} + F_{n + 2} \geq φ^{n + 1} + φ^{n} = φ^{n} (φ + 1) = φ^{n} φ^{2} = φ^{n + 2},$ ce qui est $A_{n + 2}$ . Par récurrence double, $F_{n + 2} \geq φ^{n}$ pour tout $n \in N$ .

Le point à voir. C'est exactement l'identité $φ^{2} = φ + 1$ qui rend la minoration héréditaire : les puissances de $φ$ vérifient la même relation que la suite de Fibonacci. Et la récurrence est double parce que $F_{n + 4}$ s'exprime à l'aide des deux termes précédents.

Question 2 : comment l'IA t'aide

2) Soit $n \geq 1$ . Montrer que $N (F_{n + 2}, F_{n + 1}) = n$ et que $F_{n + 2} \land F_{n + 1} = 1$ . Vérifier sur le couple $(987, 610) = (F_{16}, F_{15})$ .

Élève

Pour le 2), je fais une récurrence sur $n$ . J'ai bien $F_{n + 2} = F_{n + 1} + F_{n}$ , mais je ne vois pas pourquoi ce serait forcément la division euclidienne de $F_{n + 2}$ par $F_{n + 1}$ .

Une écriture $a = q b + r$ avec $q$ entier est la division euclidienne de $a$ par $b$ dès que $r$ vérifie une certaine condition : laquelle, et pourquoi est-ce suffisant ? Est-elle remplie ici, et pour quels $n$ ?

Élève

Il faut $0 \leq r < b$ , et l'unicité de la division euclidienne conclut. Ici $0 < F_{n} < F_{n + 1}$ dès que $n \geq 2$ ; pour $n = 1$ , $F_{1} = F_{2}$ , donc ce cas est à traiter à part.

Exactement, d'où une initialisation séparée. Une fois la première division identifiée, sur quel couple l'algorithme se poursuit-il, et comment l'hypothèse de récurrence permet-elle de compter les divisions ? Pour le PGCD, quelle propriété de chaque étape d'Euclide vas-tu enchaîner ?

L'IA ne donne pas la réponse : elle pose la question qui fait avancer. À toi de continuer.

Continue cet exercice avec l'IA

Reprends la question 2 là où le dialogue s'arrête, puis la suite de l'exercice.

Continuer avec l'IA — gratuit, sans inscription

Gratuit, sans inscription. L'IA te guide pas à pas, sans te donner la réponse.

Le cours du chapitre · Tous les exercices du chapitre

Continuer avec l'IA, gratuit →