Pgcd et algorithme d’Euclide

• Divisibilité et division euclidienne
• Pgcd et algorithme d'Euclide
• Entiers premiers entre eux
• Nombres premiers
• Congruences

Pgcd de {a,b} dans {\mathbb{N}} (avec {a\ne 0} ou {b\ne0})

On rappelle que la relation de divisibilité est une relation d’ordre (partiel) sur $\mathbb{N}$.

On rappelle également que {\mathcal{D}(0)=\mathbb{Z}} donc {\mathcal{D}(0)\cap\mathbb{N}=\mathbb{N}} : tous les entiers divisent $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.

Il en résulte que {\mathcal{D}(a)\cap\mathcal{D}(b)\cap\mathbb{N}} est une partie finie non vide de {\mathbb{N}^{*}} (elle contient l’entier {1}).

Choix d’une notation

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

Premières propriétés