Culture générale   >   PGCD de deux nombres entiers positifs

PGCD de deux nombres entiers positifs

  • Fiche de cours
  • Quiz
  • Profs en ligne
Objectifs
Parmi les diviseurs de deux nombres entiers, on s’intéressera à ceux qui sont communs à ces deux nombres, et tout particulièrement au plus grand d’entre eux.
Pour déterminer ce diviseur, on pourra utiliser plusieurs méthodes dont l’algorithme d’Euclide.

Qu’est-ce-qu’un multiple et un diviseur d’un nombre donné ? Qu’est-ce-que le PGCD de deux nombres entiers ? Comment déterminer le PGCD de deux nombres ? Que signifie que deux nombres entiers sont premiers entre eux ?
1. Multiples et diviseurs
Soient a et b deux nombres entiers.
Un nombre entier a est divisible par un nombre entier b si le reste de la division euclidienne de a par b est nul.
Dans ce cas, il existe un nombre entier k tel que : a = k × b

a est un multiple de b
b est un diviseur de a

Exemple :   238 est divisible par 14   car 238 : 14 = 17
En effet, la division euclidienne de 238 par 14 donne un reste nul :

Dans ce cas, on dit que 238 est un multiple de 14 et de 17 car 238 = 14 x 17
De même, on dit que 14 est un diviseur de 238.

Remarques : 17 est aussi un diviseur de 238 car 238 : 17 = 14

Conséquence : Chaque nombre a pour diviseurs 1 et lui-même.
Dans l'exemple précédent, 1 et 17 sont des diviseurs de 17, car 17 : 17 = 1 et 17 : 1 = 17
2. PGCD de deux nombres entiers
Soient a et b deux nombres entiers.
Un nombre entier c est un diviseur commun de a et de b, si c est à la fois un diviseur de a et un diviseur de b.

Conséquence : 1 est toujours un diviseur commun pour deux nombres entiers donnés.

Exemples :
3 est un diviseur commun de 12 et de 18, car   12 : 3 = 4   et   18 : 3 = 6
15 est un diviseur commun de 345 et 570, car   345 : 15 = 23   et   570 : 15 = 38

Le plus grand des diviseurs communs de deux nombres a et b est appelé le PGCD (Plus Grand Commun Diviseur) de ces deux nombres.
On le note PGCD (a ; b)


Recherche du PGCD de deux nombres entiers :
Méthode: on fait la liste de tous les diviseurs de chaque nombre, puis parmi ceux qui sont communs aux deux nombres, on prend le plus grand.

Exemple :
Donner le PGCD de 60 et 84
- Les diviseurs de 60 sont : 1 ; 2 ; 3 ; 4 ; 5 ; 6 ; 10 ; 12 ; 15 ; 20 ; 30 ; 60.
- Les diviseurs de 84 sont : 1 ; 2 ; 3 ; 4 ; 6 ; 7 ; 12 ; 14 ; 21 ; 28 ; 42 ; 84

1 ; 2 ; 3 ; 4 ; 6 ; 12 sont des diviseurs communs de 60 et 84.
12 est le plus grand nombre de cette liste. Donc le PGCD (60 ; 84) = 12.
3. Algorithme d'Euclide
Propriété : Soient a et b deux nombres entiers tel que a > b , et r le reste de la division euclidienne de a par b. On a : PGCD (a ; b) = PGCD (b ; r)

Exemple :

PGCD (35595 ; 6885)  =  PGCD (6885 ; 1170)
car le reste de la division de 35595 par 6885 est 1170

Application : Recherche du PGCD par l’algorithme d’Euclide

La propriété précédente peut être appliquée de manière successive aux différentes divisions euclidiennes de a par b puis de b par r, etc…
Par cette méthode, appelée "algorithme d’Euclide", le dernier reste non nul est le PGCD des deux nombres de départ.

Exemples : Calculer le PGCD de 35595 et de 6885
• On effectue la division de 35595 par 6885:
35595 = 5 × 6885 + 1170. Le reste de la division est 1170

• Puis on effectue la division de 6885 par 1170:
6885 = 5 × 1170 + 1035. Le reste de la division est 1035

• Puis on effectue la division de 1170 par 1035:
1170 = 1 × 1035 + 135. Le reste de la division est 135

• Puis on effectue la division de 1035 par 135:
1035 = 7 × 135 + 90. Le reste de la division est 90

• Puis on effectue la division de 135 par 90:
135 = 1 × 90 + 45. Le reste de la division est 45

• Puis on effectue la division de 90 par 45:
90 = 2 × 45 + 0. Le reste de la division est 0.

D’après la propriété vue plus haut :
PGCD(35595 ; 6885) = PGCD(6885 ; 1170) = PGCD(1170 ; 1035) = PGCD(1035 ; 135) = PGCD(135 ; 90) = PGCD(90 ; 45) = 45

Conclusion: Le PGCD de 35595 et 6885 est 45.

Remarque : Cet algorithme permet de déterminer le PGCD de deux grands nombres de manière plus rapide qu'en établissant la liste de leurs diviseurs.
4. Nombres premiers entre eux
Deux nombres entiers a et b sont premiers entre eux si leur plus grand diviseur commun est 1, autrement dit si PGCD (a ; b) = 1

Exemples :
- PGCD (23 ; 48) = 1 donc 23 et 48 sont premiers entre eux
- PGCD (35595  ;6885) = 45 donc 35595 et 6885 ne sont pas premiers entre eux.

Comment as-tu trouvé ce cours ?

Évalue ce cours !

 

Question 1/5

La médiane de 6 notes est 13. Cela signifie que :

Question 2/5

On a obtenu la série statistique suivante :

Combien vaut la médiane ?

Question 3/5

On a obtenu la série ci-dessous :

Quelle est la médiane de cette série ?

Question 4/5

On a relevé les tailles en cm des élèves d’une classe :

 

Parmi les propositions suivantes, laquelle est vraie ?

Question 5/5

Les notes en français de deux classes littéraires sont données dans le tableau suivant :

Quelle est la note médiane ?

Vous avez obtenu75%de bonnes réponses !

Recevez l'intégralité des bonnes réponses ainsi que les rappels de cours associés :

Votre adresse e-mail sera exclusivement utilisée pour vous envoyer notre newsletter. Vous pourrez vous désinscrire à tout moment, à travers le lien de désinscription présent dans chaque newsletter. Pour en savoir plus sur la gestion de vos données personnelles et pour exercer vos droits, vous pouvez consulter notre charte.

Une erreur s'est produite, veuillez ré-essayer

Consultez votre boite email, vous y trouverez vos résultats de quiz!

Découvrez le soutien scolaire en ligne avec myMaxicours

Le service propose une plateforme de contenus interactifs, ludiques et variés pour les élèves du CP à la Terminale. Nous proposons des univers adaptés aux tranches d'âge afin de favoriser la concentration, encourager et motiver quel que soit le niveau. Nous souhaitons que chacun se sente bien pour apprendre et progresser en toute sérénité !