Cet article est organisé en trois étapes.
Dans une première partie, vous trouverez les définitions du $\pgcd$ et du $\ppcm.$
Dans une deuxième partie, $a$ et $b$ désignent deux entiers naturels non nuls. Vous allez démontrer que :
Dans une dernière partie, un exemple détaillé vous permettra de comprendre comment calculer un $\pgcd$ sans utiliser l’algorithme d’Euclide.
Cet article utilise le théorème de Gauss en arithmétique. Il peut être démontré directement.
Pour en savoir davantage, allez lire le contenu rédigé dans l'article 310.
Première partie : définissez les notions de $\pgcd$ et de $\ppcm$
$\pgcd$ et plus grand commun diviseur
Soient $a$ et $b$ deux entiers naturels différents de $0.$ Notez que $a$ et $b$ sont des multiples de $1.$ L’ensemble des entiers naturels non nuls $n\comma$ tels que $a$ soit un multiple de $n\comma$ et $b$ un multiple de $n\comma$ est non vide.
Or, si $n$ est un entier naturel non nul qui divise $a\comma$ il existe un entier naturel $m$ tel que $a=nm.$ L’entier $a$ étant non nul, $m$ est non nul, donc $1\leq m$ et par produit, $n \leq nm$ donc $n\leq a.$
Ainsi, l’ensemble $\{n\in\N^{*}, n\mid a\text{ et }n\mid b\}$ est une partie de $\N$ non vide qui est majorée par $a.$ Son plus grand élément est noté $\pgcd(a,b).$
$\ppcm$ et plus petit commun multiple
Soient $a$ et $b$ deux entiers naturels différents de $0.$ Notez que le produit $ab\comma$ non nul, est à la fois un multiple de $a$ et de $b.$ L’ensemble des entiers naturels non nuls qui sont à la fois des multiples de $a$ et de $b$ est non vide. Soit :
Or, cet ensemble est une partie non vide de $\N\comma$ qui admet un plus petit élément. Il est noté $\ppcm(a,b).$
Deuxième partie : calculez le produit du $\pgcd$ et du $\ppcm$ de deux entiers naturels non nuls
Soient $a$ et $b$ deux entiers naturels non nuls. Vous allez démontrer que :
Vous notez $d =\pgcd(a ,b)$ et $\mu=\ppcm(a ,b).$
Par définition du $\ppcm\comma$ il existe deux entiers naturels $k$ et $\ell$ tels que $\mu = ak = b\ell.$
Or, $d$ est un diviseur commun à $a$ et à $b.$ Il existe deux entiers naturels $a^{\prime}$ et $b^{\prime}$ tels que $a=da^{\prime}$ et $b=db^{\prime}.$ Les entiers $a$ et $b$ étant non nuls, il en est de même pour $a^{\prime}\comma$ $b^{\prime}$ et $d.$
De $ak = b\ell$ vous déduisez $da^{\prime}k=db^{\prime}\ell\comma$ ce qui fournit après division par l’entier $d\comma$ que $a^{\prime}k=b^{\prime}\ell.$
Notez $d^{\prime}=\pgcd(a^{\prime},b^{\prime}).$ L’entier $d^{\prime}$ est supérieur ou égal à $1\comma$ en tant que $\pgcd$ de deux entiers naturels non nuls. Il existe deux entiers naturels $a^{\pprime}$ et $b^{\pprime}$ non nuls tels que $a^{\prime} = d^{\prime}a^{\pprime}$ et $b^{\prime}=d^{\prime}b^{\pprime}.$
Vous en déduisez que $a = dd^{\prime}a^{\pprime}$ et que $b = dd^{\prime}b^{\pprime}$ donc l’entier $dd^{\prime}$ est un diviseur commun à $a$ et à $b.$
Or, par définition de l’entier $d$ qui est un $\pgcd\comma$ le produit $dd^{\prime}$ est inférieur ou égal à $d.$ Après simplification, il vient $d^{\prime}\leq 1.$
Vous en déduisez que $d^{\prime}=1.$ Les entiers $a^{\prime}$ et $b^{\prime}$ sont premiers entre eux, et $a^{\prime}$ est un diviseur de $b^{\prime}\ell.$ Par le théorème de Gauss, $a^{\prime}$ est un diviseur de $\ell.$
Il existe un entier naturel $m$ non nul tel que $\ell = a^{\prime}m.$
De $\mu = b\ell = ba^{\prime}m$ vous déduisez que $ba^{\prime}\leq \mu.$
Or, $ba^{\prime}$ est un multiple de $b.$ Comme $ba^{\prime}=(db^{\prime})a^{\prime} = b^{\prime}(da^{\prime})=b^{\prime}a\comma$ vous déduisez que $ba^{\prime}$ est un multiple de $a.$ Par définition de $\mu$ qui est un $\ppcm\comma$ vous avez $\mu \leq ba^{\prime}.$
Ainsi $ba^{\prime} = \mu$. En multipliant par $d$, vous obtenez $dba^{\prime} = d\mu$ soit $(da^{\prime})b = d\mu$ ce qui fournit le résultat annoncé : $ab = d\mu.$
Troisième partie : calculez le $\pgcd$ sans utiliser l’algorithme d’Euclide
Pour fixer les idées, seule la situation du $\pgcd$ de trois entiers sera explicitée dans ce contenu.
Soient $a$, $b$ et $c$ trois entiers naturels non nuls.
Vous définissez de la même façon que précédemment le $\pgcd$ de trois entiers naturels, c’est le plus grand entier supérieur ou égal à $1$ qui est un diviseur de $a\comma$ $b$ et $c.$
Soit $p$ un nombre premier. On rappelle qu’un nombre premier désigne un entier naturel non nul qui admet exactement deux diviseurs. Par conséquent, $1$ n’est pas un nombre premier.
Supposez que $p$ divise les trois entiers $a$, $b$ et $c$
Dans cette situation, il existe un triplet $(a^{\prime},b^{\prime},c^{\prime})$ d’entiers naturels non nuls tel que $a=pa^{\prime}\comma$ $b=pb^{\prime}$ et $c=pc^{\prime}$. Alors, vous allez montrer que :
En effet, vous notez $d =\pgcd(a, b, c)$ et $d^{\prime}=\pgcd(a^{\prime}, b^{\prime}, c^{\prime}).$
L’entier $d^{\prime}$ divise $a^{\prime}$ donc $pd^{\prime}$ divise $pa^{\prime}$ donc $pd^{\prime}$ divise $a.$ Vous procédez de la même façon avec les entiers $b$ et $c.$ Vous déduisez que l’entier $pd^{\prime}$ divise les trois entiers $a\comma$ $b$ et $c.$ Comme $d$ est un $\pgcd\comma$ il vient $pd^{\prime}\leq d.$
Pour la suite, vous considérez le $\pgcd$ des entiers $d$ et $p.$ Comme $p$ est un nombre premier, nécessairement, $\pgcd(d,p)\in\{1,p\}.$
Supposez que $\pgcd(d,p)=1.$ Comme $d$ divise $a\comma$ $d$ divise le produit $pa^{\prime}$ et par le théorème de Gauss, $d$ divise $a^{\prime}$. Vous répétez le même raisonnement avec les entiers $b$ et $c\comma$ vous déduisez que $d$ divise $a^{\prime}\comma$ $b^{\prime}$ et $c^{\prime}$ donc, puisque $d^{\prime}$ est un $\pgcd\comma$ vous obtenez que $d\leq d^{\prime}.$ Après multiplication par $p\comma$ vous avez $pd\leq pd^{\prime}.$ Or, il a été vu précédemment que $pd^{\prime} \leq d.$ Du coup, $pd\leq d\comma$ et après simplification par $d\comma$ vous avez $p\leq 1\comma$ ce qui contredit le fait que $p$ est premier.
Il en résulte que $\pgcd(d,p)=p\comma$ donc $p$ divise $d.$ Il existe un entier naturel non nul $\delta$ tel que $d=p\delta.$ Comme $d$ divise $a\comma$ vous avez $p\delta \mid pa^{\prime}.$ Après simplification par $p\comma$ vous avez $\delta \mid a^{\prime}.$ Vous répétez ce raisonnement avec les entiers $b$ et $c.$ Vous déduisez que $\delta$ divise les trois entiers $a^{\prime}\comma$ $b^{\prime}$ et $c^{\prime}.$ Comme $d^{\prime}$ est un $\pgcd\comma$ vous avez $\delta \leq d^{\prime}.$ Vous multipliez par $p$ et obtenez $p\delta \leq pd^{\prime}\comma$ d’où $d\leq pd^{\prime}.$
Ainsi, vous avez bien $d=pd^{\prime}.$
Supposez que $p$ divise l’entier $a$ mais que $p$ ne divise pas l’entier $b$
Dans ce cas, il existe un entier naturel non nul $a^{\prime}$ tel que $a=pa^{\prime}.$ Vous allez montrer que le $\pgcd$ est inchangé, soit :
En effet, vous notez $d=\pgcd(a, b, c)$ et $\delta = \pgcd(a^{\prime},b, c).$
Comme l’entier $\delta$ divise $a^{\prime}\comma$ $\delta$ divise aussi $pa^{\prime}$ donc $\delta \mid a.$ Ainsi, l’entier $\delta$ est un diviseur commun à $a\comma$ $b$ et $c$ donc $\delta\leq d.$
Pour la suite, vous savez déjà que $d\mid a$ donc $d\mid pa^{\prime}.$
Considérez le $\pgcd$ des entiers $d$ et $p.$ Comme $p$ est un nombre premier vous avez $\pgcd(d,p)\in\{1,p\}.$
Si $\pgcd(d,p)=p\comma$ alors $p$ divise $d.$ Or l’entier $d$ divise $b.$ Ainsi $p$ divise $b\comma$ ce qui est absurde.
Donc $\pgcd(d,p)=1.$ Comme $d\mid pa^{\prime}\comma$ vous appliquez le théorème de Gauss et déduisez que $d \mid a^{\prime}.$ Alors l’entier $d$ divise $a^{\prime}\comma$ $b$ et $c\comma$ d’où $d\leq \delta.$
Il est ainsi prouvé que $d=\delta.$
Application : un exemple de calcul du $\pgcd$
Pour des petits nombres, la connaissance du début de la suite des nombres premiers $2$, $3$, $5$, $7$ suffit dans la plupart des situations
Soit à calculer $\pgcd(12, 36, 50).$
Le nombre premier $2$ divise $12\comma$ $36$ et $50\comma$ donc :
Le nombre premier $2$ divise $6$ mais ne divise pas $25\comma$ d’où :
De même, le nombre premier $2$ divise $18$ mais ne divise pas $3\comma$ donc :
Ensuite, le nombre premier $3$ divise $3$ mais ne divise pas $25\comma$ donc :
Le dernier $\pgcd$ est égal à $1.$ En définitive :
Prolongement
Lorsque les nombres dont on veut calculer le $\pgcd$ sont élevés, déterminer un nombre premier pour poursuivre peut être difficile.
La technique précédente peut être utilisée, de façon hybride, et notamment avec les ordinateurs, avec seulement le nombre premier $2.$ Quand les deux nombres sont impairs, une soustraction permet de se ramener à un entier pair, ce qui permet de poursuivre.
Plus précisément, si $a$ et $b$ sont deux entiers naturels non nuls, vous avez :