Plus grand commun diviseur

Le PGCD de deux nombres entiers naturels non nuls est, comme son nom l'indique, le plus grand nombre entier qui divise nos deux nombres.



Catégories :

Mathématiques élémentaires

Page(s) en rapport avec ce sujet :

  • PGCD et PPCM de deux entiers naturels. Nombres premiers entre eux.... L'expression de plus grand commun diviseur est justifiée par la proposition... (source : mathovore)
  • D'autre part, tout nombre entier est premier avec 1 (pas... Il faut bien comprendre que le pgcd de deux entiers a et b est l'unique entier d tel que... si et uniquement si leur plus grand commun diviseur est égal à 1.... (source : ilemaths)
  • de 0, je fais des pas de longueur b ; le quotient est alors le nombre de pas..... Algorithme de calcul du pgcd. Soient a et b deux entiers tels que 0 <b..... bindi (” Le plus grand commun diviseur est d = ” + d+ ”, ” +” ”) ;... (source : irempt.education)
Icone math élém.jpg
Cet article est membre de la série
Mathématiques élémentaires
Algèbre
Logique
Arithmétique
Probabilités
Statistiques

Le PGCD (ou plus grand diviseur commun) de deux nombres entiers naturels non nuls est , comme son nom l'indique, le plus grand nombre entier qui divise nos deux nombres.

Considérons par exemple 30 et 48.6 divise 30 car 6×5=30 et 6 divise 48 car 6×8=48.
Il n'y a pas de nombre entier supérieur à 6 qui divise à la fois 30 et 48 car sinon il serait divisible par 5.

De la même manière on peut parler de PGCD de plusieurs nombres entiers naturels.

Méthode par décomposition en facteurs premiers

Pour trouver aisément le PGCD de nombres pas trop grands, il est efficace de les décomposer en produits de facteurs premiers.
Reprenons 30 et 48 :

30=2×3×5
48=2×2×2×2×3

On remarque que le produit 2×3=6 est commun aux deux et est le plus grand produit commun, il est par conséquent le PGCD.

Dans le cas de plus de deux nombres entiers cette méthode est applicable :

56=2×2×2×7=2³×7
84=2×2×3×7=2²×3×7
140=2×2×5×7=2²×5×7

Leur PGCD est par conséquent 2²×7 soit 28.

Algorithme d'Euclide

PGCD.png

Cet algorithme est légèrement plus complexe à comprendre, il s'appuie sur le fait que si un nombre entier divise deux autres nombres entiers, alors il divise leur différence (et leur somme). Il divisera par conséquent les différences successives du plus petit enlevé du plus grand.

Reprenons l'exemple de 30 et de 48 :

48−30=18
30−18=12
18−12=6
12−2×6=0

Le dernier reste non nul est le PGCD.

Essayons avec 56 et 140 :

140−56=84
84−56=28
56−28=28
28−28=0

Donc le PGCD est 28

On aurait pu présenter ce dernier de la manière suivante, avec des divisions  :

140−2×56=28
56−2×28=0

Ces algorithmes se nomment algorithme par soustractions successives et par divisions successives

Propriété

Le produit du plus grand commun diviseur et du plus petit commun multiple de deux nombres est égal au produit des deux nombres.

PGCD (a, b) × PPCM (a, b) = a × b

comme on sait calculer le PGCD, ceci nous apporte une méthode simple pour calculer le PPCM.

Voir aussi

Recherche sur Amazon (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Plus_grand_commun_diviseur_(math%C3%A9matiques_%C3%A9l%C3%A9mentaires).
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 10/03/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu