Propriété:
a et b sont deux entiers positifs.
Si d est un diviseur commun à a et b , alors c'est aussi un diviseur du reste de la division euclidienne de a par b.
Exemple:
a= 66 et b= 27
66 | 27 Le reste est r= 12
-54 | 2 3 divise 66 et 27
12 | 3 divise aussi 12.
(Il s'agit d'une division)
Conséquence:
a et b sont deux entiers positif avec a>b
PGCD(a;b)=PGCD(b;r) où r est le reste de la division de a par b.
Algorithme d'Euclide: Exemple
Recherchons le PGCD de 105 et 63 en utilisant des divisions euclidiennes.
(en utilisant la touche " /R " de ta calculatrice)
105/63= 42 Donc PGCD(105;63)= PGCD(63;42)
63/42= 21 Donc PGCD(63;42)= PGCD(42;21)
42/21= 0
Or PGCD(42;21)= 21 car 21 divise 42.
Donc PGCD(105;63)= 21.
Propriété:
Quand on applique l'algorithme d'Euclide a deux entiers positifs, leur PGCD est le dernier reste non nul.
Remarque:
L'algorithme d'Euclide est beaucoup plus rapide en particulier pour les grands nombres.
Autres exemple:
Trouver le PGCD de 495 et 375 par la méthode d'Euclide.
Dividende | Diviseur | Reste
495 | 375 | 120
375 | 120 | 15
120 | 15 | 0
Donc PGCD(495;375)= 15
