Arithmétique des entiers (2/4)

• On rappelle que la relation de divisibilité est une relation d’ordre (partiel) sur {\mayhbb{N}}
• On rappelle également que {\mathcal{D}(0)=\mathbb{Z}} donc {\mathcal{D}(0)\cap\mathbb{N}=\mathbb{N}} : tous les entiers divisent {0}0, donc {0} est l’élément maximum de {\mathbb{N}} pour l’ordre défini par la divisibilité.
• En revanche si {n>0}, alors {\mathcal{D}(n)\cap \mathbb{N}} est une partie fini non vide de {[1,n]} (qui contient d’ailleurs {1} et {n}) de maximum {n} à la fois pour l’ordre naturel et pour celui défini par la divisibilité.
• Dans la suite, on considère deux entiers {a} et {b} de {\mathbb{N}} dont l’un au moins est non nul.
• Ainsi {\mathcal{D}(a)\cap\mathcal{D}(b)\cap\mathbb{N}} est une partie finie non vide de {\mathbb{N}^{*}} (elle contient l’entier {1}).

Soit {a} et {b} deux entiers naturels, dont l’un au moins est non nul.
Soit {\mathcal{D}(a)\cap\mathcal{D}(b)\cap\mathbb{N}} l’ensemble des diviseurs communs de {a} et {b} dans {\mathbb{N}}.
Cet ensemble, fini et inclus dans {\mathbb{N}^{*}}, possède un maximum {n\ge1} (pour l’ordre naturel).
Cet entier strictement positif {n} est appelé pgcd de {a} et de {b}.
Il est noté {n=\text{pgcd}(a,b)}, ou {n=a\wedge b}.

Ainsi {a\wedge b = \max\big(\mathcal{D}(a)\cap\mathcal{D}(b)\cap \mathbb{N}\bigr)}, où le « max » s’entend au sens de l’ordre naturel.

On verra bientôt (avec l’algorithme d’Euclide) que {a\wedge b} est aussi le maximum de {\mathcal{D}(a)\cap\mathcal{D}(b)\cap\mathbb{N}} au sens de l’ordre défini par la divisibilité. En d’autres termes, non seulement {d\le a\wedge b} pour tout diviseur positif {d} de {a} et {b}, mais on a mieux : {d\mid a\wedge b}.

Le nom « pgcd » est bien sûr une abréviation de « plus grand commun diviseur ».
En anglais, la dénomination est « gcd » (greatest common divisor).

Il faut mieux utiliser la notation {a\wedge b} qui a le mérite d’être universelle.
Le langage Python possède une fonction intégrée gcd, mais elle fait partie du module fractions.
De toutes façons, on verra qu’il est très simple de programmer soi-même cette fonction

Il est clair que {a\wedge b=b\wedge a}. De même, si {a>0}, la définition donne {a\wedge 0=a}.

Pour tout {a} de {\mathbb{N}}, on a : {\mathcal{D}(a)\cap\mathcal{D}(1)\cap\mathbb{N}=\{1\}} donc {a\wedge 1=1}.

Par définition, l’entier {a\wedge b} est un diviseur commun aux entiers {a} et {b}.
Les diviseurs de {a\wedge b} sont donc également des diviseurs communs à {a} et {b}. On verra que la réciproque est vraie : les diviseurs communs à {a} et {b} divisent {a\wedge b}.

On a l’égalité {a\wedge b=a} si et seulement si {a} est un diviseur de {b}.

La définition {a\wedge b = \max\big(\mathcal{D}(a)\cap\mathcal{D}(b)\cap \mathbb{N}\bigr)}, est celle du programme de la classe de MPSI.

On pose {0\wedge 0=0}, ce qui prolonge l’égalité {a\wedge 0=a} quand {a\ge1}.

Attention : poser {0\wedge 0=0} ne cadre pas avec la définition {a\wedge b = \max\big(\mathcal{D}(a)\cap\mathcal{D}(b)\cap \mathbb{N}\bigr)} si on considère le {\max} au sens de l’ordre naturel, mais ça marche encore si le {\max} est celui de l’ordre défini par la divisibilité dans {\mathbb{N}} (en effet {\mathcal{D}(0)\cap\mathcal{D}(0)\cap \mathbb{N}=\mathbb{N}} dont le maximum pour la divisibilité est {0}).

Par ailleurs, on rappelle que {\mathcal{D}(a)=\mathcal{D}(-a)} pour tout {a} de {\mathbb{Z}}.
On peut donc étendre la définition du pgcd aux entiers relatifs en posant {a\wedge b=\left|a\right|\wedge\left|b\right|}.

Dans la mesure où les propriétés relatives à la divisibilité (donc aux calculs de pgcd) ne dépendent pas du signe des entiers {a} et {b}, on supposera essentiellement que {a} et {b} sont des entiers naturels.