Algorithme d'Euclide
L'algorithme d'Euclide repose sur la propriété suivante :
Fondamental :
Soit \(a\) et \(b\) deux entiers naturels non nuls.
Soit \(r\) le reste de la division euclidienne de \(a\) par \(b\).
Alors \(PGCD(a ; b) = PGCD(b ; r)\)
Démonstration
on note \(a=bq+r\) la division euclidienne de \(a\) par \(b\).
Soit \(d\) un diviseur commun à \(a\) et \(b\).
\(d\) divise \(a\) et \(b\) donc d divise \(a-bq\), c'est à dire \(r\).
Soit \(e\) un diviseur commun à \(r\) et \(b\).
\(e\) divise \(r\) et \(b\) donc \(e\) divise \(bq+r\), c'est à dire \(a\).
Donc les diviseurs de \(a\) et \(b\) sont les mêmes que les diviseurs de \(b\) et \(r\). Il en va de même pour le plus grand de ces diviseurs.
Simulation : Déterminer le PGCD de 252 et 360
Impossible d'accéder à la ressource audio ou vidéo à l'adresse :
La ressource n'est plus disponible ou vous n'êtes pas autorisé à y accéder. Veuillez vérifier votre accès puis recharger la vidéo.
On applique l'algorithme d'Euclide :
360 = 252 x 1 + 108
252 = 108 x 2 + 36
108 = 36 x 3 + 0
Le dernier reste non nul est 36 donc \(PGCD(252 ; 360) = 36\).
En effet, d'après la propriété précédente :
\(PGCD(252 ; 360) = PGCD(252 ; 108) = PGCD(108 ; 36) = PGCD(36 ; 0) = 36\)
Complément :
L'ensemble des diviseurs communs de deux entiers est l'ensemble des diviseurs de leur PGCD.
C'est ce qu'on a constaté dans l'activité précédente sur les iris et les roses : les diviseurs de 42 sont les diviseurs commun de 126 et 210.