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).

.

Code des fonctions PGCD

fonction n°1 Fonction n°2
_images/pgcd01.PNG
_images/pgcd02.PNG
Programme n°1 :
_images/pgcd03.PNG
Programme n°2 :
_images/pgcd04.PNG
Programme n°3 :
_images/pgcd05.PNG