pgcdcm

Plus grand commun diviseur et plus petit commun multiple

Pour comprendre la définition de diviseurs, multiplesdans $\mathbb{N}$ prenez deux entiers naturelsstrictement positifs
et puis la liste des diviseurs de ces deux nombres et la listes des premiers multiples :

Définition du $\mathrm{pgcd}$ ( plus grand diviseur commun ) à deux entiers naturels non nuls

Soient $a$ et $b$ deux entiers naturels non nuls, et soit $D_a$ l'ensemble des diviseurs de $a$ et $D_b$ l'ensemble des diviseurs de $b$, l'ensemble $D_a\cap D_b$ est l'ensemble des diviseurs communs de $a$ et de $b$, ce sous ensemble non vide de $\mathbb{N}$ ( $1 \in D_a\cap D_b$ ) majoré par $a$ et par $b$ admet donc un plus grand élément appelé plus grand diviseur commun de $a$ et $b$ .
Notation : $\mathrm{pgcd}(a,b) = a \wedge b$

Définition du $\mathrm{ppcm}$ ( plus petit commun multiple ) à deux entiers naturels non nuls
Soient $a$ et $b$ deux entiers naturels non nuls, et soit $M_a$ l'ensemble des multiples de $a$ et $M_b$ l'ensemble des multiples de $b$, l'ensemble $M_a\cap M_b$ est l'ensemble des multiples communs de $a$ et de $b$, ce sous ensemble non vide de $\mathbb{N}$ ( $ab \in M_a\cap M_b$ ) minoré par $a$ et par $b$ admet donc un plus petit élément appelé plus petit commun multiple de $a$ et $b$ .
Notation : $\mathrm{ppcm}(a,b) = a \vee b$

Propriétés du $\mathrm{pgcd}$ et du $\mathrm{ppcm}$ :

• $\vee$ et $\wedge$ sont des lois de composition interne sur $\mathbb{N}^*$
• $\vee$ et $\wedge$ sont des lois commutatives et associatives.
• la multiplication sur $\mathbb{N}^*$ est distributive par rapport à la loi $\wedge$ et par rapport à la loi $\vee$.
• $a × b = ( a \wedge b ) × ( a \vee b ) $
  

Liens :

• PGCD et combinaison linéaire de deux entiers
• Algorithme de soustraction de recherche du PGCD
• Algorithme d' Euclide de recherche du PGCD