Algorithme d'Euclide. Bézout. Complexité. Fractions continues. Applications cryptographiques
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)