Plus grand commun diviseur

En arithmétique élémentaire, le plus grand commun diviseur, abrégé généralement PGCD, de deux nombres entiers naturels est le plus grand entier naturel qui divise simultanément ces deux entiers.



Catégories :

Divisibilité et factorisation - Arithmétique élémentaire - Mathématiques élémentaires - Opération

Recherche sur Google Images :


Source image : ilemaths.net
Cette image est un résultat de recherche de Google Image. Elle est peut-être réduite par rapport à l'originale et/ou protégée par des droits d'auteur.

Page(s) en rapport avec ce sujet :

  • Le plus grand commun diviseur est le nombre entier le plus grand qui puisse diviser nombre1 et ... = PGCD (5;2), Le plus grand commun diviseur de 5 et 2 (1)... (source : office.microsoft)
  • Le calcul du PGCD (Plus Grand Commun Diviseur) est un algorithme classique.... Soient u et v deux entiers positifs, l'algorithme suivant calcule le pgcd de ... (source : ief.u-psud)

En arithmétique élémentaire, le plus grand commun diviseur, abrégé généralement PGCD, de deux nombres entiers naturels est le plus grand entier naturel qui divise simultanément ces deux entiers.

Par exemple le PGCD de 42 et 56 est 14. En effet,, et 3 et 4 sont premiers entre eux (il n'y a aucun naturel à part 1 qui soit à la fois diviseur de 3 et de 4).

Pour une explication plus détaillée suivant ce sens, voir :

On peut étendre cette notion, dans un premier temps aux entiers relatifs, 0 compris, ainsi qu'aux nombres rationnels, ou alors aux réels. On pose même des définitions s'appliquant pour n'importe quel anneau, en distinguant les propriétés valables pour l'ensemble des anneaux et celles valables pour des anneaux de types spécifiques.

De plus, on peut aussi considérer le PGCD d'un nombre arbitraire d'éléments, et occasionnellementd'une illimitété.

Appellation

L'élément dont nous parlons est le plus grand diviseur commun d'a et b. On pourrait s'attendre à le voir nommé le plus grand diviseur commun, abrégé "PGDC" et non le plus grand commun diviseur. Mais le nom est assez ancien, et en ancien français il était plus normal de dire "commun diviseur" que "diviseur commun" et on retrouve plus fréquemment l'appellation PGCD.

Notations

Le PGCD de deux entiers a et b est fréquemment noté : PGCD (a, b) ou pgcd (a, b). De même, le pgcd d'une séquence d'entiers ai sera notée pgcd (ai) ou PGCD (ai).

Certains auteurs notent le pgcd de deux entiers a et b sous la forme a \wedge b. Cette notation fait référence aux ensembles ordonnés : tout diviseur commun à a et b divise leur pgcd (voir ci-dessous).

Les anglophones le nomment greatest common divisor, noté : gcd (a, b).

Définitions

Pour des entiers

Étant donnée une séquence finie ou illimitée ai d'entiers qui ne sont pas tous nuls, la totalité des diviseurs communs des termes de la séquence est une partie finie et non vide de N

Finie, car un diviseur d'un entier non nul a est borné par |a| ;
Non vide car contient 1, entier qui divise tous les entiers.

Cet ensemble admet par conséquent un élément maximal d, nommé le pgcd de la séquence ai reconnue.

A titre d'exemple, les diviseurs communs de 36, 48 et 60 sont 1, 3, 4 et 12. Le pgcd de 36, 48 et 60 est par conséquent 12.

Rappelons qu'un entier n s'écrit de manière unique à l'ordre près des facteurs et au signe près comme un produit fini de nombres premiers. Le nombre de fois que l'entier premier p apparait dans cette écriture se nomme la valuation p-adique de n, notée vp (n) . Un entier m divise un entier n si et uniquement si pour tout p v_p(m)\leq v_p(n).

De fait, le pgcd d'une séquence ai est donnée par :

pgcd(a_i)=\prod_p pˆ{\min v_p(a_i)}

où le produit portent sur la totalité des nombres premiers (presque l'ensemble des termes du produit, outre une quantité finie, sont égaux à 1).

Tout diviseur commun à une séquence d'entiers relatifs, non tous nuls, divise leur pgcd. Ce constat résulte immédiatement de l'écriture ci-dessus en produit de nombres premiers. Le pgcd apparait de fait comme l'élément maximal de la totalité des diviseurs communs, maximal au sens de la division (avec son opposé : certains préfèrent même préciser "le PGCD positif", cependant lorsque on parle des entiers, si on demande le PGCD, il est évident qu'on parle du PGCD positif).

Quelques précisions sur «plus grand»

Habituellement, pour des nombres entiers, on considère seulement des PGCD positifs et la notion de «plus grand» correspond bien à la notion d'ordre usuelle pour les nombres. Pour d'autres cas, le «plus grand» de PGCD ne correspond pas nécessairement à la relation d'ordre habituelle mais au fait que tout diviseur commun d'a et de b divise PGCD (a, b). L'ou les PGCD d'a et de b sont par conséquent les plus grands éléments de la totalité des diviseurs d'a et de b au sens de la relation de divisibilité, et par conséquent -3 et 3 sont tous deux des PGCD de 6 et de 9. Cette façon de voir les choses est utile pour définir le PGCD, pour des polynômes par exemple, ou pour le PGCD de nombres rationnels. Dans le cas des polynômes, le PGCD est le diviseur de plus haut degré. Pour le cas de nombres entiers, on préfère généralement prendre le PGCD positif, ce qui sert à faire en sorte qu'il soit bien le plus grand au sens normal du terme. Et même, on ne précise pas qu'on souhaite le PGCD positif lorsque on sert à désigner le PGCD comme unique.

Bien entendu, celui des deux pgcd qui est positif est aussi le plus grand diviseur au sens de la relation d'ordre «supérieur ou inférieur», mais ce n'est vrai que pour le cas des nombres (le PGCD couvre à d'autres objets mathématiques). Et toujours, le cas de PGCD (0, 0), que nous examinerons plus loin, contredit cette assertion.

Rappelons que le D de PGCD veut dire toujours diviseur et non dénominateur. Le plus petit commun dénominateur est en fait le PPCM utilisé pour la réduction de fractions. L'emploi de cette expression n'est pas une erreur, c'est un cas spécifique d'emploi du PPCM. L'expression "Plus grand commun dénominateur" est par contre erronée, sauf si on considère "dénominateur" comme synonyme de "diviseur" (ce qu'on fait quelquefois à cause de sa position en bas d'une fraction, le nombre rationnel n/m étant égal à n divisé par m, et m est le dénominateur).

Cas du zéro

Certaines définitions du PGCD autorisent le calcul du PGCD d'un entier quelconque avec 0. Pour tout n entier, pgcd (0, n) = n.

Cette propriété reste vraie pour n=0.

Donc pgcd (0, 0) =0 (c'est la réponse donnée par les calculatrices : elle ne peut se justifier par la définition du PGCD du premier paragraphe).

Ce n'est pas une simple convention, mais la conséquence de la définition formelle du PGCD.

En effet, ce résultat devient évident lorsque on adopte la #Définition par les idéaux (a) + (b) = (pgcd (a, b) ) (" (a) " signifiant "idéal génèré par l'élément a") comme définition du PGCD, ce qui se fait sans problème si on travaille sur les nombres entiers, puisque leur ensemble est un anneau principal.

Il s'agit d'ailleurs du seul cas pour lequel il n'y a pas à choisir entre un PGCD positif et un négatif.

Exemple

On cherche le PGCD de 15 et 12.

Les diviseurs positifs de 15 sont : 1, 3, 5, 15.

Les diviseurs positifs de 12 sont : 1, 2, 3, 4, 6, 12.

On obtient par conséquent d12, 15 = {1, 3}

On en déduit pgcd (12, 15) = 3.

Pour trouver le PGCD de deux nombres plus grands, on peut utiliser l'algorithme d'Euclide

Calcul

On peut calculer le PGCD de deux nombres en écrivant leur décomposition en produit de facteurs premiers et en considérant le produit de certains facteurs premiers communs. Dans la pratique, on utilise rarement cette méthode du fait de sa lenteur, excepté dans les cas évidents (par exemple pour 4 et 6, on trouve immédiatement 4=2*2 et 6=2*3, d'où PGCD (4, 6) =2).

Une méthode bien plus efficace est l'algorithme d'Euclide.

Propriétés

Soit (a,b,c)\in{\mathbb{Z}ˆ*}ˆ3

Généralisations

PGCD de fractions

Dans ce paragraphe, on utilise la définition suivante : d est un pgcd d'a et b si d divise a et b et d est divisible par tout élément divisant a et b. (paragraphe 2)

Premier point de vue : c'est le plus évident : on se place dans le corps \mathbb Q des rationnels. Alors pour p1/q1 et q2/p2 deux rationnels non tous deux nuls, tout rationnel non nul est un PGCD de p1/q1 et q2/p2 (Q étant un corps, tout rationnel autre que 0 divise 1, et 1 divise tout rationnel). Par convention, on choisit 1 comme PGCD. Dans le cas où les deux fractions sont nulles, le PGCD vaut toujours 0.

Note : on montre que A est un corps si et uniquement si A est un anneau unitaire dont les seuls idéaux sont {0} et A. On comprend aisément, avec la définition du paragraphe 2.1, que deux éléments non tous deux nuls de A admettent n'importe quel élément non nul de A comme PGCD, et on choisit 1 (le neutre de la seconde loi) par convention. La notion de PGCD n'a par conséquent pas énormément d'intérêt dans un corps!

Deuxième point de vue : il consiste à considèrer qu'une fraction p/q en divise une autre p'/q'non pas s'il existe une fraction a/b telle que p/q*a/b=p'/q' (toujours vrai si p ne vaut pas 0 : prendre a=q*p'et b=p*q') mais uniquement s'il existe un entier c tel que p/q*c=p'/q'.

De façon analogue au paragraphe sur les idéaux, un pgcd de p1/q1 et q2/p2 est une fraction p/q telle que p1/q1*\mathbb Z+p2/q2*\mathbb Z=p/q*\mathbb Z. Mais attention, les objets manipulés ici ne sont pas des idéaux, ni des pseudo sous-anneaux de Q, uniquement des sous-groupes.

Finalement, on trouve p=+/- pgcd (p1, p2) et q=ppcm (q1, q2).

De même, on a ppcm (p1/q1, p2/q2) = +/- ppcm (p1, p2) /pgcd (q1, q2)

Le PGCD obtenu suivant le deuxième point de vue est aussi un PGCD envisageable lorsque on se place sur le corps Q. Les calculatrices et les logiciels de calcul choisissent l'un ou l'autre suivant le choix des programmeurs (par exemple Maple adopte le premier point de vue, la Casio Graph 100+ et la TI-92 le second).

Un inconvénient du second point de vue est que le PGCD d'une famille illimitée de rationnels n'existe pas forcément. Par exemple la famille des fractions 1/n, n allant de 1 à l'infini parmi les entiers, n'admet pas de PGCD.

Cas des réels

On peut toujours étendre les définitions précédentes avec des nombres réels : le premier point de vue conduit à un PGCD de 1 pour tout couple de réels non tous deux nuls.

Le second point de vue dit que pour deux réels quelconques a et b, s'il existe un réel c tel que a=u*c et b=v*c avec u et v rationnels, on choisit PGCD (a, b) =|c|*PGCD (u, v), suivant la définition des PGCD de rationnels vue ci-dessus (2e point de vue).

Pour deux réels a et b tels que a/b soit irrationnel (si b=0 on est dans la situation précédente) on est obligé de revenir au premier point de vue d'où PGCD (Pi, \sqrt[]{2}) =1; à noter que le PPCM le même problème, mais il est déterminé par PGCD (a, b) *PPCM (a, b) =|a*b|. (PPCM (Pi, \sqrt[]{2}) =Pi*\sqrt[]{2})

Chaque calculateur se plaçant dans la continuité de son comportement concernant les rationnels, Maple répond suivant le premier point de vue, la Casio Graph 100+ selon le second ; la Ti-92 n'a pas de réponse.

Polynômes à cœfficients réels

Le PGCD dans l'anneau \mathbb R[X] vérifie la définition donnée plus haut. Mais cette fois il y a une illimitété de PGCD envisageables pour 2 polynômes : tout PGCD des polynômes A et B multiplié par un réel non nul est aussi un PGCD de A et B. Pour définir un PGCD unique il y a deux conventions envisageables : ou bien on pose par convention que le PGCD doit être un polynôme unitaire, ou bien on choisit le polynôme dont le cœfficient dominant est le PGCD des cœfficients dominants de A et B, en employant la définition du paragraphe précédent pour les PGCD de réels.

À titre d'exemple, Maple choisit la première option lorsque les polynômes sont à cœfficients entiers, la seconde sinon, alors que les calculatrices Casio optent toujours pour la seconde convention.

Dans les anneaux commutatifs

Par extension, le plus grand commun diviseur peut être défini d'une façon plus générale pour les éléments d'un anneau commutatif arbitraire, pas nécessairement unitaire (certains diraient : pseudo-anneau). Le plus grand commun diviseur d'une famille ai d'éléments de A non tous nuls est le plus grand diviseur commun aux ai au sens de la division.

L'existence d'un tel élément (tout comme du PPCM) est certaine dans un anneau factoriel, pas forcément dans d'autres anneaux.

A titre d'exemple, dans l'anneau Z[i\sqrt[]{3}], 4 et 2+2i\sqrt[]{3} admettent 2 et 1+i\sqrt[]{3} comme diviseurs, mais aucun élément divisible simultanément par 2 et 1+i\sqrt[]{3} ne les divise.

Le PGCD de a et b n'est pas forcément unique, mais si A est intègre alors deux quelconques PGCD de a et b sont des éléments associés.

Dans le pseudo-anneau 2 * Z / 20Z, [8] et [12] admettent comme pgcd envisageables [4], [8], [12], [16] , qui ne sont pas associés.

Dans un anneau principal, il existe c et d éléments de A (non uniques) tels que ac + bd = pgcd (a, b) (théorème de Bachet-Bézout)

Si A est un anneau euclidien alors une forme de l'algorithme d'Euclide est parfois utilisée pour calculer le PGCD.

L'unicité peut occasionnellementêtre rétablie en posant une contrainte supplémentaire. Par exemple dans l'anneau des polynômes à cœfficients complexes, le PGCD est unique si on exige qu'il soit un polynôme unitaire.

D'ailleurs dans le cas des nombres entiers, l'unicité du PGCD est obtenue avec la convention "le PGCD est un nombre positif". Sans cette convention, la définition ci-dessus donne deux PGCD différents, opposés.

Tout ce qui précède se généralise à un nombre arbitraire ou même illimité d'éléments, sauf l'algorithme d'Euclide.

Définition par les idéaux

La définition de ce paragraphe est légèrement plus générale que celle du paragraphe précédent, et sert à définir des PGCD dans des cas où ils ne pourraient l'être suivant la définition précédente.

Dans l'anneau commutatif A, on note (x) l'idéal principal génèré par l'élément x, ie l'intersection de l'ensemble des idéaux de A contenant x, (la totalité des éléments xy, y décrivant A si A est unitaire).

Pour a et b éléments de A, (a) + (b) est aussi un parfait.

Alors d est un pgcd d'a et b ssi (d) est le plus petit parfait génèré par un seul élément et incluant (a) + (b), ie (a) + (b) ⊂ (d) et pour tout x ⊂ A, (a) + (b) ⊂ (x) (ce qui équivaut à "x est un diviseur d'a et b" si A est unitaire) ⇒ (d) ⊂ (x) (ce qui équivaut à "x est un diviseur de d" si A est unitaire).

Dans le pseudo-anneau (anneau non unitaire) 2Z, 8 et 12 ont pour PGCD envisageables 4 et -4… En effet, (8) + (12) ⊂ (4) = (-4) = 4Z, et néenmoins il n'existe pas dans 2Z d'élément x tel que 4*x=12.

Dans un anneau principal, ce qui précède équivaut à (a) + (b) = (d)

Comme plus haut, il n'y a pas unicité du pgcd.

Ici encore, on peut étendre à un nombre arbitraire ou alors illimité d'éléments.

Anneaux non-commutatifs

Dans un anneau non-commutatif, un élément peut admettre des "diviseurs à droite" et des "diviseurs à gauche". On peut dans certain cas définir un PGCD à droite et/ou un PGCD à gauche. Mais l'existence de l'un n'implique pas nécessairement celle de l'autre, et l'existence commune n'implique pas nécessairement l'égalité.

Demander à un calculateur électronique le PGCD de deux matrices n'est pas nécessairement interprété au sens de l'algèbre linéaire. Par exemple une TI-92 interrogée sur le PGCD de deux matrices de même taille répond en donnant la matrice composée des PGCD des éléments de même position des deux matrices.

Voir aussi

Liens externes

Recherche sur Amazone (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Plus_grand_commun_diviseur.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 10/03/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu