Plus grand diviseur commun – PGCD
1. Le pgcd, c’est quoi ?
Définition 1.
Soient $a$ et $b$ deux nombres entiers naturels et $d$ un entier naturel non nul.
On dit que $d$ est un diviseur commun à $a$ et $b$ si et seulement si $d$ est un diviseur de chacun de ces deux nombres.
Exemple
$3$ est diviseur commun à $18$ et $24$.
Définition 2.
Soient $a$, $b$ et $d$ trois nombres entiers naturels non nuls.
On dit que $d$ est le plus grand diviseur commun à $a$ et $b$ si et seulement si d est un diviseur commun à $a$ et $b$ et que $d$ est le plus grand des diviseurs communs. On note : $$d = PGCD(a ; b)\quad\text{ou}\quad d = pgcd(a ; b)$$
2. Propriétés du PGCD
Propriété 1.
Soient $a$, $b$ et $d$ trois nombres entiers naturels non nuls.
$d$ est le plus grand diviseur commun de $a$ et $b$ si et seulement si les deux conditions suivantes sont réalisées :
$\quad$ 1°) $d$ divise $a$ et $d$ divise $b$.
$\quad$ 2°) Pour tout entier naturel $d’$ : Si $d’$ divise $a$ et $d’$ divise $b$, alors $d’\leqslant d$.
La première condition dit que : $d$ est un diviseur commun à $a$ et $b$.
La deuxième condition dit que : $d$ est le plus grand diviseur commun à $a$ et $b$.
Exemple
$3$ est un diviseur commun à $18$ et $24$. Mais $3$ n’est pas le PGCD de $18$ et $24$.
$6$ est aussi un diviseur commun à $18$ et $24$ et $6 > 3$.
$6$ est le PGCD de $18$ et $24$. On écrit : $$PGCD(18;24)=6$$
Propriété 2. (Conséquence immédiate)
Soient $a$ et $b$ deux nombres entiers naturels non nuls. Si $a$ est un multiple de $b$ (ou que $b$ est un diviseur de $a$), alors le PGCD de $a$ et $b$ est égal à $b$.
Si $b$ divise $a$, alors : $PGCD(a;b)=b$
En effet,
Si on suppose que $a$ est un multiple de $b$, alors $b$ est un diviseur de $a$.
Or, on sait que $b$ est un multiple de $b$, donc $b$ est un diviseur de $b$ et c’est le plus grand parmi les diviseurs de $b$. Ainsi $b$ est un diviseur commun à $a$ et $b$ et c’est le plus grand des diviseurs communs à $a$ et $b$. D’où le résultat.
Exemple. $PGCD(18;6)=6$.
Propriété 3.
Soient $a$ et $b$ deux nombres entiers naturels non nuls. Alors :
$\quad$ 1°) $\boxed{\;\;PGCD (a ;b)=PGCD (a;a+b)\;\;}$
$\quad$ 2°) Si $a>b$, alors $\boxed{\;\;PGCD(a;b)=PGCD(a;a−b)\;\;}$.
La deuxième propriété permet de réduire la recherche à des nombres plus petits. Si on
recommence le procédé de proche en proche, on devrait y arriver. A quel moment faudra-t-il s’arrêter ?
Cette propriété sera utilisée pour développer la méthode ou algorithme des soustractions successives pour le calcul du PGCD.
Exemple
Déterminer le PGCD de $18$ et $24$ en utilisant la méthode précédente.
$PGCD(18;24)=PGCD(18;24-18)$
$\phantom{PGCD(18;24)}=PGCD(18;6)$.
$\phantom{PGCD(18;24)}=6$, car 18 est un multiple de $6$.
CQFD.$\blacktriangle$
Propriété 4.
Soient $a$ et $b$ deux nombres entiers naturels non nuls. On suppose que $a>b$.
Alors, si on effectue la division euclidienne de $a$ par $b$, il existe un couple unique d’entiers
$(q ; r)$ tel que : $a = bq +r$, avec $0\leqslant r < b$. Alors $$\boxed{\;\;PGCD(a;b)=PGCD(b;r)\;\;}$$
Cette propriété, plus rapide, permet de réduire la recherche à des nombres plus petits. Si on
recommence le procédé de proche en proche, on devrait y arriver. A quel moment faudra-t-il s’arrêter ?
Cette propriété sera utilisée pour développer la méthode des divisions euclidiennes successives, dite algorithme d’Euclide, pour le calcul du PGCD.
Exemple.
Si on pose $a=24$ et $b=18$, alors $24 = 18\times1+6$, donc $r=6$.
Par conséquent : $PGCD(18;24)=PGCD(18;6)=6$.
3. Comment calculer le PGCD de deux entiers naturels non nuls.
Il existe au moins quatre méthodes pour calculer le PGCD de deux entiers naturels $a$ et $b$ non nul.
- Calcul du et PGCD par la méthode des listes des diviseurs
- Méthodes des soustractions successives
- Méthodes des divisions successives ou Algorithme d’Euclide
- Algorithme sur calculatrice ou sur un ordinateur.
Vues : 9