Lycée > Terminale > Mathématiques > PGCD-Nombres premiers entre eux

PGCD-Nombres premiers entre eux

Fiche de cours Quiz Profs en ligne Vidéos Télécharger le pdf

Fiche de cours Quiz Profs en ligne Vidéos Télécharger
le pdf

Objectif :

PGCD de deux entiers naturels - Nombres premiers entre eux

1. PGCD de deux entiers naturels

Définition : Si a et b sont deux entiers, on appelle PGCD (Plus Grand Commun Diviseur) de a et b le plus grand des diviseurs communs de a et de b.

On le note PGCD(a ; b).

Exemple : L'ensemble des diviseurs de 45 est D₄₅ = { 1 ; 3 ; 5 ; 9 ; 15 ; 45 }.
L'ensemble des diviseurs de 63 est D₆₃ = { 1 ; 3 ; 7 ; 9 ; 21 ; 63 }.
L'ensemble de leurs diviseurs communs est D₄₅D₆₃ = { 1 ; 3 ; 9 }.
Leur plus grand diviseur commun est 9. PGCD( 45 ; 63 ) = 9.

Recherche du PGCD avec l'algorithme d'Euclide

Pour trouver le PGCD de deux naturels, une méthode est d'utiliser l'algorithme d'Euclide : on effectue la division euclidienne du plus grand des deux nombres par le plus petit, puis successivement la division du diviseur précédent par le reste précédent jusqu'au dernier reste nul. Le PGCD cherché est le dernier reste non nul.

Exemple : Calcul du PGCD de 4851 et de 616.

donc le PGCD de 4851 et de 616 est 77, le dernier reste non nul.

Le programme de calcul du PGCD
Données : deux entiers naturels a et b, a > b.
Résultat : PGCD( a ; b ).
Règle :
Tant que b > 0, faire :

Retourner à b ← r signifie que dans le registre noté b, on met le contenu du registre noté r.

Théorèmes
Si c est un diviseur de a et un diviseur de b, alors c est un diviseur du PGCD de a et de b.

Exemple : Tout diviseur de 4851 et de 616 est diviseur de leur PGCD, 77.

Si b est un diviseur de a, alors PGCD( a ; b ) = b.

Exemple: PGCD( 187 ; 17 ) = 17.

Quels que soient les entiers naturels non nuls a, b et k,

PGCD( ka ; kb ) = k x PGCD( a ; b ).

Exemple : PGCD ( 4500 ; 6300 ) = 100 x PGCD ( 45 ; 63 ) = 100 x 9 = 900.

2. Nombres premiers entre eux

Définition
« Les deux entiers naturels a et b sont premiers entre eux » signifie que PGCD( a ; b ) = 1.
On en déduit que le seul diviseur commun de deux entiers naturels premiers entre eux est 1.

Exemple :
Le seul diviseur commun de 14 et 25 est 1, donc 14 et 25 sont premiers entre eux.
7 est un diviseur commun de 14 et 21, donc 14 et 21 ne sont pas premiers entre eux.

Théorème
- Quels que soient les entiers non nuls a et b, si PGCD( a ; b ) = D, alors il existe deux entiers naturels a' et b' premiers entre eux tels que a = Da' et b = Db'.

Ou

- Quels que soient les entiers non nuls a et b, si PGCD( a ; b ) = D, alors les nombres a/D et b/D sont premiers entre eux.

Exemple : PGCD ( 4500 ; 6300 ) = 900.