∑
MathTCG
#067 / 100•Algebra & Numbers•MathTCG #367 / 500•★Commune•ℤArithmétique•Concept

Plus grand commun diviseur

Période historique : Antiquité

Le plus grand entier positif qui divise simultanément deux entiers non nuls (PGCD).

Contenu & Formulation mathématique

Définition rigoureuse
Borne supérieure dans le treillis de la divisibilité de l'ensemble des diviseurs communs.
Notation usuelle & Exemples
\operatorname{pgcd}(54, 24) = 6
pgcd⁡(a,b)=max⁡{d∈N∗∣d∣a et d∣b}\operatorname{pgcd}(a, b) = \max \{ d \in \mathbb{N}^* \mid d \mid a \text{ et } d \mid b \}

Genèse & Portée historique

Noté pgcd(a,b) ou gcd(a,b), le plus grand commun diviseur est le générateur positif de l'idéal aZ + bZ. Il se calcule très efficacement par l'algorithme d'Euclide et permet de simplifier les fractions sous forme irréductible.

L'algorithme du livre VII des Éléments d'Euclide permettant de trouver le PGCD par soustractions ou divisions répétées est le plus ancien algorithme non trivial toujours utilisé.

« La mesure commune la plus généreuse capable de paver exactement deux longueurs entières. »

Filiations & Relations conceptuelles (0)

Cette notice constitue un axiome autonome sans relations directes enregistrées dans le recueil.

Objet de collection MathTCG

#367
★Commune
ℤ

Plus grand commun diviseur

Arithmétique•CONCEPT

Borne supérieure dans le treillis de la divisibilité de l'ensemble des diviseurs communs.

pgcd⁡(a,b)=max⁡{d∈N∗∣d∣a et d∣b}\operatorname{pgcd}(a, b) = \max \{ d \in \mathbb{N}^* \mid d \mid a \text{ et } d \mid b \}
Antiquité

Dans l'édition physique et numérique de MathTCG, cette carte appartient à l'extension Algebra & Numbers.

Extension : Algebra & Numbers (#067 / 100)
Numéro global MathTCG : MathTCG #367 / 500
Rareté officielle : Commune (★)
Domaine théorique : Arithmétique
Identifiant pérenne : plus-grand-commun-diviseur
Consulter mon classeurExplorer tout le recueil