Théorème de Lamé

Alaeddine Ben Rhouma

Informations

• Publié par: ALEDINE.BENRHOUMA
• Publié le: 06 mai 2015
• Nombre de lectures: 66
• Langue: Français

Extrait

2 THÉORÈME DE LAMÉ
Algorithme d’Euclide et théorème de Lamé
1 Suites de Fibonacci
Définition.
On appelle suites de Fibonacci l’ensemble
F ={(v ) / u ∈R ; u ∈R et u =u +u pour tout n≥ 0}n (n≥0) 0 1 n+2 n+1 n
.
1. Montrer queF est unR-espace vectoriel de dimension 2.
∗ n2. a) Soit r∈R , trouver les valeurs de r pour que u =r soit un élément deF.n
b) Déduire le terme général de la suite (F ) ∈F vérifiant F = 0 et F = 1.n (n≥0) 0 1
√
1+ 5 n−1
c) Montrer alors que pour tout n≥ 0, on a F >n+1
2
3.Montrerque (F )eststrictementcroissanteàpartirden = 2etquel’algorithmed’Euclidepourdéterminern
le PGCD de F et F nécessite exactement n divisions euclidiennes.n+2 n+1
2 Théorème de Lamé
Théorème.
Le nombre de divisions euclidiennes nécessaires pour obtenir le PGCD de deux entiers naturels
non nuls, en appliquant l’algorithme d’Euclide, est inférieur ou égal à 5 fois le nombre de chiffres
servant à écrire le plus petit des deux nombres.
Démonstration :
Soient deux entiers naturels non nuls a et b tels que a>b.
On suppose que l’algorithme d’Euclide pour déterminer leur PGCD comporte n étapes avec n≥ 2.
On pose alors, a =r et b =r et on peut schématiser celui-ci sous la forme :0 1
r = r q + r2 avec 0<r <r0 1 1 2 1
··· = ··· + ··· ···
r = r q + r avec 0<r <rn−2 n−1 n−1 n n n−1
r = r q + 0n−1 n n
1. Montrer que q ≥ 2 et en déduire que r ≥F .n n−1 3
2. Montrer que pour tout entier k tel que 0≤k≤n, on a r ≥F .n−k k+2
√
1+ 5 n−1
3. Montrer que l’on a b≥F et en déduire que b> .n+1
2
4. Montrer alors le théorème de Lamé.
Alaeddine BEN RHOUMA 1 Agrégation interne de Mathématiques