Plus grand commun diviseur (mathématiques élémentaires)
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.
image:icone_math_élém.jpg
Cet article fait partie de la série
Mathématiques élémentaires
Algèbre
Analyse
Arithmétique
Géométrie
Logique (La logique (du grec logikê, dérivé de logos (λόγος), terme inventé par Xénocrate signifiant à la fois raison, langage, et raisonnement) est dans...)
Probabilité (La probabilité (du latin probabilitas) est une évaluation du caractère probable d'un évènement. En mathématiques, l'étude des probabilités est un sujet de grande importance donnant lieu à...)
Statistique (Une statistique est, au premier abord, un nombre calculé à propos d'un échantillon. D'une façon générale, c'est le résultat de...)

Le PGCD (ou plus grand diviseur (En mathématiques, un nombre entier d est un diviseur d'un entier n lorsque la division euclidienne de n par d donne un reste égal à...) commun) de deux nombres entiers naturels non nuls est, comme son nom l’indique, le plus grand nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) 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 biologie, la décomposition est le processus par lequel des corps organisés, qu'ils soient d'origine animale ou végétale dès l'instant qu'ils sont...) en facteurs premiers

Pour trouver facilement 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 donc 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 donc 2²×7 soit 28.

Algorithme d’Euclide

Cet algorithme est un peu plus difficile à 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 donc les différences successives du plus petit ôté 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 s'appellent 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 fournit une méthode simple pour calculer le PPCM.

Page générée en 0.160 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique