PGCD et Algorithme d'Euclide
1. PGCD (Plus Grand Commun Diviseur):
a. Remarque: Si a et b sont deux nombres entiers, a divise b signifie qu'il existe un nombre entier q tel que b=aq.
Par exemple 6 divise 54 signifie que 54 = 6x9 (ici q=9).
b. Définition: Le PGCD de deux nombres est leur plus grand diviseur commun.
Par exemple le PGCD de 30 et 25 est 5 car 5 divise à la fois 30 et 25 et il n'y a pas de nombre plus grand que 5 qui divise à la fois 30 et 25.
Pour deux nombres "pas trop grands", il est facile de trouver leur PGCD. Mais pour les nombres grands, c'est plus compliqué, mais il existe une méthode : l'Algorithme d'Euclide.
c. Propriétés: Soit a,b et c trois nombres entiers quelconques.
* Si a divise b et c, alors a divise b+c .
En effet a divise b signifie qu'il existe un nombre entier q tel que b=aq.
De même a divise c signifie qu'il existe un nombre entier p tel que c=ap.
Donc b+c=aq+ap=a(q+p) et donc a divise b+c.
* Si a divise b et b+c, alors a divise c.
En effet a divise b signifie qu'il existe un nombre entier q tel que b=aq.
De même a divise b+c signifie qu'il existe un nombre entier p tel que b+c=ap.
Donc c=ap-b=ap-aq=a(p-q) et donc a divise c.
2. Algorithme d'Euclide:
a. Remarque: Un algorithme est un procédé de calcul qui se répète plusieurs fois de suite jusqu'au résultat.
b. Algoritme:
Soit a0 et b0 deux nombres entiers tel que a0 < b0. On cherche leur PGCD. Pour cela:
* Soit a0 divise b0, dans ce cas le PGCD de a0 et b0 est a0. En effet a0 divise a0 et a0 divise b0, il n'y a donc pas de nombre plus grand que a0 qui divise a0 et b0.
*Soit a0 ne divise pas b. Dans ce cas, il existe deux nombres q0 et r0 qui sont les quotient et reste de la division euclidienne de b0 par a0. On a
b0 =q0 x a0 + r0 .Le PGCD de a0 et b0 divise b0 et a0, donc en appliquant la deuxième propriété, ce PGCD divise r0.
On pose alors b1=a0 , a1 = r0 et on recommence:
il existe deux nombres r1 et q1 tel que b1=q1 x a1 + r1
ainsi de suite jusqu'à ce que l'on trouve un reste nul.
Le PGCD sera le dernier reste non nul !
c. Exemple:
Appliquons cette méthode à la recherche du PGCD de 960 et 108.
960 = 8 x 108 + 96
On remplace 960 par 108 et 108 par 96 et on recommence:
108 = 1 x 96 + 12
On remplace 108 par 96 et 96 par 12 et on recommence:
96 = 8 x 12 + 0
Le dernier reste est 0, donc on s'arrête la. Le PGCD est le dernier reste non nul: c'est 12.
d. Définition:
Si deux nombres a et b ont pour PGCD le nombre 1, alors on dit que a et b sont premiers entre eux.
3. Exercice:
1. Pour commencer , cliquer sur la partie en gris.
2. Faire le calcul sur une feuille.
3. Pour obtenir de l'aide, cliquer sur la flèche " droite " -->. (une fois par étape)
4. Pour un nouveau calcul, cliquer sur la flèche " gauche " <--.