Leçon 1 issue du chapitre Arithmétique
✅ Utiliser l’algorithme des soustractions successives pour calculer un PGCD.
✅ Utiliser l’algorithme d’Euclide pour calculer un PGCD.
✅ Résoudre des petits problèmes de mathématiques en utilisant le PGCD.
Soient $latex a$ et $latex b$ des nombres entiers naturels non nuls.
– Un diviseur commun de deux nombres $latex a$ et $latex b$ est un nombre qui divise les deux sans laisser de reste.
– Le PGCD de $latex a$ et $latex b$, noté $latex \text{PGCD}(a,b)$, est le plus grand de leurs diviseurs communs.
– Le PPCM de $latex a$ et $latex b$, noté $latex \text{PPCM}(a,b)$, est le plus petit multiple commun à $latex a$ et $latex b$.
Pour déterminer le $latex PGCD$ de deux nombres entiers naturels non nuls tels que $latex a>b$, on peut soit utiliser l’algorithme des soustractions successives, soit utiliser l’algorithme d’Euclide ou encore des divisions euclidiennes successives.
Principe :
– On compare les deux nombres donnés.
– À chaque étape, on soustrait le plus petit nombre du plus grand.
On répète ce processus avec les nouveaux résultats obtenus.
– Dès qu’on obtient un reste égal à 0, on arrête.
Le dernier nombre non nul trouvé est alors le $latex PGCD$ !
Exemple : Trouvons $latex \text{PGCD}(168,120)$ :
$latex 168 – 120 = 48$
$latex 120 – 48 = 72$
$latex 72 – 48 = 24$
$latex 48 – 24 = 24$
$latex 24 – 24 = 0$
Résultat : $latex \text{PGCD}(168,120) = 24$
Principe : On fait des divisions successives.
– À chaque étape, on divise le plus grand nombre par le plus petit et on retient uniquement le reste de la division.
– On recommence en divisant le diviseur précédent par ce reste.
– On répète ce processus jusqu’à obtenir un reste égal à 0.
Quand le reste est $latex 0$, c’est fini ! Le dernier reste non nul obtenu avant $latex 0$ est le $latex PGCD$.
Exemple : Trouvons $latex \text{PGCD}(375,2020)$ :
$latex 2020 = 5 \times 375 + 145$
$latex 375 = 2 \times 145 + 85$
$latex 145 = 1 \times 85 + 60$
$latex 85 = 1 \times 60 + 25$
$latex 60 = 2 \times 25 + 10$
$latex 25 = 2 \times 10 + 5$
$latex 10 = 2 \times 5 + 0$
Résultat : $latex \text{PGCD}(375,2020) = 5$