Fonctions pour calculer le pgcd
Programmes et fonctions
PGCD de deux entiers
1) Définitions
\(a\) et \(b\) étant des entiers relatifs, on note \(D\left( a \right)\) l’ensemble des diviseurs de \(a\) , \(D\left( b \right)\) l’ensemble des diviseurs de \(b\) et l’ensemble des diviseurs communs à \(a\) et à \(b\) .
On a donc :\(D\left( {a,b} \right)\ = \ D\left( a \right) \cap D\left( b \right)\) .
Exemple
\(D\left( 35 \right)\ = \ \left \{ {- 35\ ;\ - 7\ ;\ - 5\ ;\ - 1\ \,\,\,;\,\, 1;\,\, 5;\,\, 7;\,\, 35} \right \}\)
\(D\left( 63 \right)\ = \ \left \{ {- 63\ ;\ - 21\ ;\ - 9\ ;\ - 7\ ;\ - 3\ ;\ - 1;1;\ 3;\ 7;\ 9;\ 21\ ;\ 63} \right \}\) et donc \(D\left( 15,63 \right) = \ \left \{ {- 7\ ;\ - 1\ ;\ 1\ ;\ 7} \right \}.\)
On appelle PGCD de \(a\) et de \(b\) , où \(a\) et \(b\) sont deux entiers relatifs non tous les deux nuls, le plus grand diviseur commun à \(a\) et à \(b\) et on le note \(PGCD\left( {a.b} \right)\) .
Remarque :
Il existe au moins un diviseur commun positif puisque \(1\) est à la fois diviseur de \(a\) et de \(b\) .
Donc dans la pratique, on utilisera uniquement les diviseurs positifs de \(a\) et de \(b\) car \(PGCD(a;b) \in {\mathbb{N}}\,\, et \,\, PGCD(a;b) = PGCD(\left| a \right|;\left| b \right|)\)
On dit que deux entiers relatifs \(a\) et \(b\) non tous les deux nuls sont premiers entre eux, lorsque \(PGCD(a;b) = 1\) .
.
Propriétés de l’ensemble des diviseurs communs
Propriété 1 (Lemme d’Euclide) :
étant deux entiers naturels avec \(b \neq 0\) et \(r\) le reste de la division euclidienne de \(a\) par \(b\) alors \(D\left( {a,b} \right)\ = \ D\left( {b,r} \right)\) et donc \(PGCD\left( {a,b} \right)\ = \ PGCD\left( {b,r} \right)\)
Propriété 2 :
\(a\) et \(b\) étant deux entiers naturels avec \(b \neq 0\) , si \(b\) divise \(a\) alors \(D\left( {a,b} \right)\ = \ D\left( b \right)\) et donc \(PGD(a;b) = b\)
Algorithme d’Euclide
Théorème :
\(a\) et \(b\) sont deux entiers naturels tels que \(b \neq 0\) . Pour trouver le \(PGCD\left( {a;b} \right)\) , on applique l’algorithme suivant appelé algorithme d’Euclide ou algorithme des divisions euclidiennes successives et celui-ci est obtenu en un nombre fini d’étapes :
1) Calculer le reste \(r\) de la division euclidienne de \(a\) par \(b\) ;
2) Si \(r \ = \text{0}\) alors \(PGCD(a;b) = b\) ;
3) Si \(r \neq 0\) alors on remplace \(a\) par \(b\) et \(b\) par \(r\) et on recommence à partir de 1).
