Plus grand commun diviseur
En arithmétique élémentaire, le plus grand commun diviseur ou PGCD de deux nombres entiers non nuls est le plus grand entier qui les divise simultanément. Par exemple, le PGCD de 20 et de 30 est 10, puisque leurs diviseurs communs sont 1, 2, 5 et 10. Cette notion s'étend aux entiers relatifs grâce aux propriétés de la division euclidienne. Elle se généralise aussi aux anneaux euclidiens comme l'anneau des polynômes sur un corps commutatif. La notion de PGCD peut être définie dans tout anneau commutatif. Cependant, l'existence d'un PGCD de deux éléments quelconques n'est plus garantie, mais c'est le cas pour des classes d'anneaux (plus générales que les seuls anneaux euclidiens) comme les anneaux factoriels. Un anneau pour lequel cette propriété d'existence est satisfaite est appelé anneau à PGCD. Le PGCD de deux entiers et se note : . Par extension, le PGCD d'une famille d'entiers est noté . est parfois noté . Cette notation fait référence aux ensembles ordonnés : tout diviseur commun à et divise leur PGCD. Plus grand commun diviseur de nombres entiers Étant donné une famille (finie ou infinie) d'entiers relatifs non tous nuls, l'ensemble des diviseurs communs aux est une partie finie et non vide de : finie, car un diviseur d'un entier non nul est borné par ; non vide car contient 1. Cet ensemble admet donc un plus grand élément , appelé le PGCD de la famille des . Par exemple, les diviseurs communs à 36, 48 et 60 sont 1, 2, 3, 4, 6 et 12 donc . Rappelons que le D de PGCD signifie toujours diviseur et non dénominateur. Lors de la réduction de fractions au même dénominateur, on peut être amené à chercher le plus petit commun dénominateur qui est en fait le PPCM des dénominateurs. L'emploi de cette expression n'est pas une erreur, c'est un cas particulier d'emploi du PPCM. L'expression « Plus grand commun dénominateur » est en revanche erronée. Usuellement, pour des nombres entiers, on considère uniquement des PGCD positifs et la notion de « plus grand » correspond bien à la notion d'ordre usuelle pour les nombres.