PGCD (mathématiques élémentaires)

PGCD (mathématiques élémentaires)

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 PGCD (mathématiques élémentaires) de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Mathématiques élémentaires — Les mathématiques élémentaires[1] regroupent des notions et techniques mathématiques abordées dans l enseignement scolaire primaire et secondaire. Elles se démarquent ainsi des mathématiques de l enseignement supérieur et notamment, en France,… …   Wikipédia en Français

  • Probabilités (mathématiques élémentaires) — Pour les articles homonymes, voir Interconnexions entre la théorie des probabilités et les statistiques. Les probabilités sont nées du désir de prévoir l imprévisible ou de quantifier l incertain. Mais il faut avant tout préciser ce qu elles ne… …   Wikipédia en Français

  • Fonction (mathématiques élémentaires) — Pour les articles homonymes, voir Fonction. En mathématiques élémentaires, la plupart des fonctions rencontrées sont des fonctions numériques, mais la notion de fonction ne se limite pas à celle ci. L article qui suit présente quelques règles à… …   Wikipédia en Français

  • Statistiques (mathématiques élémentaires) — Une enquête statistique consiste à observer une certaine population (élèves d’une classe, personnes âgées de 20 à 60 ans dans une région donnée, familles dans une région donnée, exploitations agricoles, appartements, travailleurs…) et à… …   Wikipédia en Français

  • Limite (mathématiques élémentaires) — Pour les articles homonymes, voir Limite. La notion de limite est très intuitive malgré sa formulation abstraite. Pour les mathématiques élémentaires, il convient de distinguer une limite en un point réel fini (pour une fonction numérique) et une …   Wikipédia en Français

  • Logique (mathématiques élémentaires) — La logique est le lieu où le langage puis les axiomes (logiques ou propres à certaines théories) des mathématiques sont définis ce qui est à la base des démonstrations en mathématique. Bien qu elle apparaisse de manière cachée dans toute l… …   Wikipédia en Français

  • Suite (mathématiques élémentaires) — Intuitivement une suite réelle est une règle qui associe à chaque entier naturel n un certain nombre réel ; on dit alors que ce nombre réel est indexé par l’entier. En fait une suite est un moyen d’indexer des nombres réels par des entiers… …   Wikipédia en Français

  • Distributivité (mathématiques élémentaires) — La distributivité est une propriété de la multiplication qui permet d effectuer de deux manières différentes le produit d un nombre par une somme : Ici on a distribué a à chaque terme de la somme Ici on a distribué c à chaque terme de la… …   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

  • Série (mathématiques élémentaires) — Pour les articles homonymes, voir Série. Les séries sont une catégorie de suite. Une série de terme général un est, basiquement, la somme des n premiers termes de la suite . C est pour cette raison que l on appelle la suite , la suite des sommes… …   Wikipédia en Français

Share the article and excerpts

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