Leçon 142 — PGCD et PPCM, algorithmes de calcul. Applications.
Points clés
- Algorithme d'Euclide
- Bézout
- Complexité
- Fractions continues
- Applications cryptographiques
Plan
- PGCD et PPCM dans [formule]
- Définition par divisibilité
- [formule]
- Identité de Bézout
- Algorithme d'Euclide
- Division euclidienne itérée
- Complexité : [formule] divisions
- Algorithme d'Euclide étendu
- PGCD dans [formule]
- Division euclidienne des polynômes
- Algorithme d'Euclide pour les polynômes
- [formule] ssi [formule] a une racine multiple
- Fractions continues
- Développement en fraction continue d'un rationnel : lié à Euclide
- Réduites [formule] : meilleures approximations rationnelles
- Fractions continues des irrationnels quadratiques : périodiques
- Sous-résultants et résultant
- Résultant [formule] : déterminant de Sylvester
- [formule] ssi racine commune
- Algorithme des sous-résultants
- Applications
- Inversion modulaire par Euclide étendu
- Solution de Pell-Fermat par fractions continues
- Simplification de fractions rationnelles
Théorèmes clés
- Bézout : [formule] calculable par Euclide étendu
- Complexité d'Euclide : [formule] ; pire cas pour les Fibonacci (théorème de Lamé)
- [formule] pour [formule]
- [formule] ssi [formule] et [formule] ont une racine commune
Exemples importants
- Euclide étendu : [formule] avec remontée des coefficients
- Fraction continue de [formule]
- Théorème de Lamé : pire cas pour [formule]
- [formule] dans [formule]
Erreurs courantes
- Se tromper dans la remontée de l'algorithme d'Euclide étendu
- Oublier que [formule]
- Confondre le PGCD dans [formule] (positif) et dans [formule] (unitaire)
Conseils du jury
- Savoir dérouler Euclide étendu sur un exemple numérique est indispensable
- Le théorème de Lamé et Fibonacci est une application élégante
- Le jury attend qu'on sache calculer des PGCD dans [formule] et [formule]
Développements associés
Prérequis
arithmetique z, polynomes