PGCD-Nombres premiers entre eux - Cours de Mathématiques Terminale S avec Maxicours - Lycée

01 49 08 38 00 - appel gratuit de 9h à 18h (hors week-end)

PGCD-Nombres premiers entre eux

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 D45 = { 1 ; 3 ; 5 ; 9 ; 15 ; 45 }.
L'ensemble des diviseurs de 63 est D63 = { 1 ; 3 ; 7 ; 9 ; 21 ; 63 }.
L'ensemble de leurs diviseurs communs est D45D63 = { 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.

   et   ; PGCD( 5 ; 7 ) = 1.

Comment avez vous trouvé ce cours ?

Évaluez ce cours !

 

Découvrez
Maxicours

Des profs en ligne

Géographie

Aidez votre enfant à réussir en espagnol grâce à Maxicours

Des profs en ligne

  • 6j/7 de 17h à 20h
  • Par chat, audio, vidéo
  • Sur les 10 matières principales

Des ressources riches

  • Fiches, vidéos de cours
  • Exercices & corrigés
  • Modules de révisions Bac et Brevet

Des outils ludiques

  • Coach virtuel
  • Quiz interactifs
  • Planning de révision

Des tableaux de bord

  • Suivi de la progression
  • Score d’assiduité
  • Une interface Parents