Mathématiques expertes (option) · Terminale · Arithmétique

PGCD et algorithme d'Euclide

• Le PGCD de deux entiers est leur plus grand diviseur commun. Deux règles suffisent pour le calculer : PGCD(a, 0) = a, et PGCD(a, b) = PGCD(b, r) quand r est le reste de a divisé par b.
• Algorithme d'Euclide : on divise, on décale (a prend la valeur de b, b celle du reste), on recommence jusqu'à un reste nul. Le PGCD est le dernier reste non nul.
• Il s'arrête toujours : les restes forment une suite d'entiers positifs strictement décroissante.
• L'algorithme d'Euclide étendu remonte les divisions et fournit des entiers u et v tels que au + bv = PGCD(a, b) (coefficients de Bézout).