$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th

pgcd

Pgcd de deux entiers
  Si a et b sont deux entiers non nuls, l'ensemble de leur diviseur commun est une partie de Z non vide, et majorée par min(|a|,|b|). Il possède donc un plus grand élément qui est le plus grand diviseur commum, ou pgcd de a et b. On convient que pgcd(a,0)=a.

  Le pgcd de a et b est le plus grand des diviseurs pour l'ordre usuel. C'est aussi le plus grand des diviseurs pour la divisibilité, comme l'indique la proposition suivante :
Proposition : Soit a et b deux entiers, et d un diviseur commun à a et b. Alors a divise pgcd(a,b).

  On dispose essentiellement de deux algorithmes pour déterminer le pgcd de deux entiers a et b :
  1. la division euclidienne : cet algorithme est basé sur le fait que si r est le reste dans la division euclidienne de a par b, alors pgcd(a,b)=pgcd(b,r). On réitère alors ces divisions jusqu'à trouver un reste nul. Le premier reste non nul est le pgcd de a et b.
  2. la décomposition en facteurs premiers : si a et b s'écrivent
    alors
On définit de même le pgcd de plus de deux entiers comme le plus grand élément de l'ensemble des diviseurs communs de ces entiers.

Pgcd de deux polynômes
  On suppose désormais que K est un corps. On peut également définir la notion de pgcd de deux polynômes de K[X]. Toutefois, on ne dispose plus de la relation d'ordre naturelle qui existe sur les entiers, et l'extension de la notion de pgcd se fait par la relation "être plus grand pour la relation de divisibilité". On a ainsi la proposition et définition suivante :
Proposition et Définition: Soient P et Q deux éléments de K[X]. Il existe un unique polynôme D nul ou unitaire tel que, pour tout R de K[X], on ait :
(R|P et R|Q) si et seulement si R|D.
Ce polynôme D est appelé le pgcd de P et Q.

  Le pgcd de deux polynômes satisfait les mêmes propriétés que le pgcd de deux entiers. En particulier, on peut également le calculer en utilisant l'algorithme d'Euclide.

Pgcd dans un anneau principal
  On peut étendre la définition du pgcd à d'autres anneaux que Z et K[X] en partant de la remarque suivante. Si a et b sont deux entiers, alors d=pgcd(a,b) est l'unique entier naturel tel que aZ+bZ=dZ. De même, si P et Q sont deux polynômes, alors D=pgcd(A,B) est l'unique polynôme unitaire ou nul tel que PK[X]+QK[X]=DK[X]. Ainsi, si a et b sont deux éléments d'un anneau A, il est naturel de définir leur pgcd comme l'élément d tel que aA+bA=dA. Cela pose deux problèmes :
  • Il faut être sûr qu'un tel élément d va exister. Pour cela, il suffit de remarquer que aA+bA est un idéal de A. Pour être sûr qu'il soit de la forme dA, il suffit que l'anneau soit principal, c'est-à-dire que tous ses idéaux sont engendrés par un seul élément.
  • Il faut garantir l'unicité d'un tel élément. Cela n'est en général pas possible. Par exemple, sur les entiers, dZ=(-d)Z. Pour les polynômes, si x est un réel non nul, (xP)K[X]=PK[X]. Même pour ces deux exemples, avec la définition précédente, le pgcd n'aurait été défini qu'à un élément inversible près. On a dû en plus choisi une normalisation appropriée.
  Si l'on résume ces considérations, on a la proposition suivante :
Proposition et Définition: Soient A un anneau principal, a et b deux éléments de A. Aux inversibles près, il existe un unique d de A tel que aA+bA=dA. d satisfait que, pour tout c de A, on a :
(c|a et c|b) si et seulement si c|d.
d est appelé pgcd de a et b.

Pgcd dans un anneau factoriel
  Une autre façon d'étendre la définition du pgcd est de partir de la décomposition en facteurs premiers et de définir le pgcd de a et b comme dans l'algorithme de calcul ci-dessus. Ceci n'est possible que dans un anneau où tout élément non nul admet une décomposition unique, aux inversibles près, en produits de facteurs irréductibles (dans un anneau, on emploie plutôt le théorème de facteur irréductible que de facteur premier). De tels anneaux sont appelés anneaux factoriels. On a alors :
Proposition et Définition: Soient A un anneau factoriel, a et b deux éléments de A. Soit
leur décomposition respective en produit de facteurs irréductibles (u et v sont des éléments inversibles, les pi sont des éléments irréductibles). Alors le pgcd de a et b est défini par
Il est tel que, pour tout c de A on a :
(c|a et c|b) si et seulement si c|pgcd(a,b).

Consulter aussi...