Définitions
Rappelons les définitions des PGCD et PPCM.
Par exemple, on a $(15,20)=5$.
On a par exemple $[15,20] = 60$.
Remarque : Ces deux notions ne sont pas bien définies lorsque les deux nombres sont nuls. On supposera donc toujours être dans le cas où l'un des deux nombres est différent de $0$. Par contre, elles ont tout à fait un sens lorsqu'un seul des deux nombres est nul. Dans ce cas, on a $(a,0) = a$ et $[a, 0] = 0$ car tous les entiers non-nuls divisent $0$ et $0$ ne divise aucun entier non-nul.
Calcul
Si les décompositions en facteurs premiers de $x$ et de $y$ sont connues, alors il est aisé de calculer leur PGCD et PPCM. En effet, notons
$$x = p_1^{e_1} \cdot p_2^{e_2} \cdot \ldots \cdot p_n^{e_n},$$ $$y = q_1^{f_1} \cdot q_2^{f_2} \cdot \ldots \cdot q_m^{f_m}$$ les décompositions des deux nombres. Quitte à rajouter des termes avec exposant $0$ (rappelons que $x^0 = 1$ par convention si $x \neq 0$), nous pouvons supposer que les $p_i$ et $q_i$ apparaissant dans les deux décompositions sont les mêmes (par exemple, au lieu d'écrire $15 = 3^1 \cdot 5^1$ et $20 = 2^2 \cdot 5^1$, on peut écrire $15 = 2^0 \cdot 3^1 \cdot 5^1$ et $20 = 2^2 \cdot 3^0 \cdot 5^1$) :
$$x = p_1^{e_1} \cdot p_2^{e_2} \cdot \ldots \cdot p_n^{e_n},$$ $$y = p_1^{f_1} \cdot p_2^{f_2} \cdot \ldots \cdot p_n^{f_n}.$$ De là, nous pouvons déduire la décomposition en facteurs premiers de $(x,y)$ et $[x,y]$. En effet, $(x,y)$ doit tout d'abord diviser les deux nombres $x$ et $y$, donc ses facteurs premiers doivent forcément être des éléments $p_i$. Et à chaque facteur $p_i$, vu que nous cherchons le plus grand diviseur, il est optimal de mettre le plus grand exposant possible. Pour continuer à diviser $x$ et $y$, l'exposant à mettre est $\min(e_i,f_i)$. Ainsi, on en déduit
$$(x,y) = p_1^{\min(e_1,f_1)} \cdot p_2^{\min(e_2,f_2)} \cdot \ldots \cdot p_n^{\min(e_n,f_n)}.$$ De la même façon, on trouve que
$$[x,y] = p_1^{\max(e_1,f_1)} \cdot p_2^{\max(e_2,f_2)} \cdot \ldots \cdot p_n^{\max(e_n,f_n)}.$$ Ainsi, pour notre exemple, on retrouve bien
$$(15,20) = 2^{\min(0,2)} \cdot 3^{\min(1,0)} \cdot 5^{\min(1,1)} = 2^0 \cdot 3^0 \cdot 5^1 = 5,$$ $$[15,20] = 2^{\max(0,2)} \cdot 3^{\max(1,0)} \cdot 5^{\max(1,1)} = 2^2 \cdot 3^1 \cdot 5^1 = 60.$$
Première propriété
Cette constatation nous permet de démontrer le résultat suivant :
Propriété
Si $x, y \in \mathbb{N}_0$, on a toujours
$$(x,y) \cdot [x,y]=x \cdot y.$$
Démonstration
Si on regarde un seul facteur premier $p$ de la décomposition, il apparaît avec l'exposant $\min(e,f)$ dans $(x,y)$ et avec l'exposant $\max(e,f)$ dans $[x,y]$. Dans le membre de gauche de l'égalité, son exposant sera donc $\min(e,f)+\max(e,f)$. Dans le membre de droite, son exposant sera $e+f$, et la conclusion découle du fait que $$\min(e,f)+\max(e,f) = e+f.$$
Sur notre exemple, remarquons que l'on a bien
$$(15,20) \cdot [15,20] = 5 \cdot 60 = 300 = 15 \cdot 20.$$
Difficulté
Malheureusement, on ne connaît pas toujours la décomposition en facteurs premiers des nombres qui nous intéressent. Nous allons cependant voir qu'il existe un moyen très efficace pour calculer le PGCD de deux nombres : l'algorithme d'Euclide. De plus, au vu de la formule précédente reliant le PGCD et le PPCM, on sera également en mesure de calculer le PPCM de deux nombres.