Plus grand commun diviseur (mathematiques elementaires)

Plus grand commun diviseur (mathematiques elementaires)

Plus grand commun diviseur (mathématiques élémentaires)

Icone math élém.jpg
Cet article fait partie 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.

Sommaire

Méthode par décomposition 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

PGCD.png

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.

Voir aussi

Ce document provient de « Plus grand commun diviseur (math%C3%A9matiques %C3%A9l%C3%A9mentaires) ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Plus grand commun diviseur (mathematiques elementaires) de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Plus grand commun diviseur (mathématiques élémentaires) — Cet article fait partie de la série Mathématiques élémentaires Algèbre Logique Arithmétique Probabilités …   Wikipédia en Français

  • Plus grand commun diviseur — Pour une introduction à cette notion, consulter l article : PGCD de nombres entiers. En arithmétique élémentaire, le plus grand commun diviseur, abrégé en général PGCD, de deux nombres entiers naturels est le plus grand entier naturel qui… …   Wikipédia en Français

  • PGCD (mathématiques élémentaires) — Plus grand commun diviseur (mathématiques élémentaires) Cet article fait partie de la série Mathématiques élémentaires Algèbre Logique Arithmétique Probabilités …   Wikipédia en Français

  • Plus petit commun multiple — En mathématiques et plus précisément en arithmétique, le plus petit commun multiple – en abrégé PPCM – de deux entiers non nuls a et b est le plus petit entier strictement positif qui soit à la fois multiple de ces deux nombres. On le note a ∨… …   Wikipédia en Français

  • Plus haut facteur commun — Plus grand commun diviseur En arithmétique élémentaire, le plus grand commun diviseur, abrégé en général PGCD, de deux nombres entiers naturels est le plus grand entier naturel qui divise simultanément ces deux entiers. Par exemple le PGCD de 42… …   Wikipédia en Français

  • PPCM (mathématiques élémentaires) — Plus petit commun multiple En mathématiques et plus précisément en arithmétique, le plus petit commun multiple, en abrégé PPCM (noté lcm en anglais pour least common multiple), de deux entiers naturels a et b, est le plus petit entier qui soit à… …   Wikipédia en Français

  • Algorithme d'Euclide (mathématiques élémentaires) — Algorithme d Euclide L algorithme d Euclide est un algorithme permettant de déterminer le plus grand commun diviseur (P.G.C.D.) de deux entiers dont on ne connaît pas la factorisation. Il est déjà décrit dans le livre VII des Éléments d Euclide.… …   Wikipédia en Français

  • Fraction (mathématiques élémentaires) — Fraction (mathématiques) Pour les articles homonymes, voir Fraction. Un gâteau coupé en quatre dont une part a été retirée. Les trois autres parts apparaissant à l image. U …   Wikipédia en Français

  • Arithmétique (mathématiques élémentaires) — Arithmétique élémentaire L’arithmétique élémentaire regroupe les rudiments de la connaissance des nombres telle qu elle est présentée dans l enseignement des mathématiques. Elle commence avec la comptine numérique, autrement dit la suite des… …   Wikipédia en Français

  • Démonstration (mathématiques élémentaires) — Démontrer une propriété c est utiliser des théorèmes, des définitions ou des axiomes que l on sait être vrais et quelques règles de logique élémentaire. Elle expose une justification d’une propriété nouvelle algébrique, géométrique, numérique…… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”