Comment trouver le PGCD de deux entiers ?
En appliquant l'algorithme d'Euclide (divisions euclidiennes successives)
L'objectif
Calculer efficacement le PGCD de deux entiers, même grands, sans les décomposer en facteurs premiers.
Le principe
Le PGCD de et est égal au PGCD de et du reste de la division de par . On répète l'opération jusqu'à ce que le reste soit nul : le dernier diviseur non nul est le PGCD.
La méthode
- 1Effectue la division euclidienne du plus grand nombre par le plus petit : note le quotient et le reste .
- 2Si le reste est nul, le est le diviseur de cette dernière division.
- 3Si le reste est non nul, recommence : divise le diviseur précédent par (le nouveau dividende devient l'ancien diviseur, le nouveau diviseur devient l'ancien reste).
- 4Répète jusqu'à obtenir un reste nul. Le est le dernier reste non nul (c'est-à-dire le dernier diviseur utilisé).
Exemple corrigé
Difficulté croissante de 1 à 5
Exercices aujourd'hui0 / 3
Prêt à t'entraîner ?
Génère un exercice personnalisé sur cette méthode et entraîne-toi avec la correction IA.