eBabylone
.com

Un article de Wikipedia.y-project.com.

En mathématiques, le plus grand commun diviseur (abrégé PGCD) de deux entiers, dont l'un au moins est non nul, est le plus grand nombre entier naturel qui divise les deux nombres.

Le PGCD de a et b est souvent noté : PGCD(a,b), pgcd(a,b) ou a?b (il y a alors confusion avec le et logique, c'est pourquoi cette notation ne sera pas utilisée ici).

Deux nombres entiers sont dits « premiers entre eux » si leur plus grand commun diviseur égale 1.

On peut étendre le PGCD à un nombre d'entiers n supérieur à deux: le PGCD est le plus grand entier naturel divisant simultanément les n nombres.

Sommaire 1 Définition 2 Exemple 3 Calcul du PGCD 4 Propriétés 5 PGCD dans les anneaux commutatifs 6 Voir aussi 6.1 A lire avant 6.2 A lire après

[] Définition

Soit <math>(a,b)\in^*\times\mathbb}</math>.

On note <math>d_=\left\{ d\in\mathbb^* / d|a \land d|b \right\}</math>

On vérifie alors :

• <math>d_ \subset \mathbb</math>
• <math>d_ \ne \empty</math> (car <math>1 \in d_</math>)
• <math>\forall n\in d_, n \le a</math>

En effet, soit n dans <math>d_</math>. On a donc n|a. On en déduit qu'il existe un k dans <math>\mathbb^*</math> tel que n.k=a. Comme <math>k \ge 1</math>, <math>n \le a</math>.

Par axiome, <math>\max(d_)</math> exsite.

On définit <math>\operatorname(a,b)=\max(d_)</math>.

[] 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 donc <math>d_=\{1, 3\}</math>

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

Dans la pratique, on utilise l'algorithme d'Euclide

[] Calcul du PGCD

On pourrait 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, mais 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 beaucoup plus efficace est l'algorithme d'Euclide.

[] Propriétés

Soit <math>(a,b,c)\in^*}^3</math>

• <math>\operatorname(a,b) \land \operatorname(a,b)|b</math>
• <math>c|a \land c|b \Leftrightarrow c|\operatorname(a,b)</math>
• <math>\operatorname(ac,bc) = |c|\operatorname(a,b)</math>
• <math>\operatorname(a,b)=\min\left\{|au+bv| / (u,v)\in\mathbb^2 \right\}</math>
• <math>\operatorname(a,b) = \operatorname(a+cb,b)</math>
• <math>\operatorname(a,b) \operatorname(a,b) = |ab|</math>
• <math>\operatorname(a,\operatorname(b,c)) = \operatorname(\operatorname(a,b),\operatorname(a,c))</math>
• <math>\operatorname(a,\operatorname(b,c)) = \operatorname(\operatorname(a,b),\operatorname(a,c))</math>
• <math>\operatorname(a,b,c) = \operatorname(\operatorname(a,b),c) = \operatorname(a,\operatorname(b,c))</math>, on peut étendre à un nombre arbitraire d'entier
• Géométriquement, pgcd(a,b) est le nombre de points de coordonnées entières sur le segment d'extrémités les points (0,0) et (a,b), sans compter (0,0).

[] PGCD dans les anneaux commutatifs

Le plus grand commun diviseur peut être défini plus généralement pour les éléments d'un anneau commutatif arbitraire.

Si A est un anneau commutatif, et a et b sont dans A, alors un élément c de A est appelé un diviseur commun de a et b s'il divise à la fois a et b (c'est-à-dire s'il existe des éléments x et y de A tels que cx = a et cy = b). Si c est un diviseur commun de a et b, et chaque diviseur commun de a et b divise c, alors c est appelé un plus grand commun diviseur de a et b.

Notons que le PGCD de a et b n'est pas unique, mais si A est intègre alors deux quelconques PGCD de a et b sont des éléments associés. Aussi, a et b ne peuvent avoir un PGCD à moins que A soit un anneau factoriel. Si A est un anneau euclidien alors une forme de l'algorithme d'Euclide peut être utilisée pour calculer le PGCD.

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

[] Voir aussi

[] A lire avant

• Divisibilité

[] A lire après

• Plus petit commun multiple
• Nombres premiers entre eux

DernierMirror  

Réagissez

Commentez l'encyclopédie:
Attention! tous les commentaites inaproprié seront supprimés

Titre:
Video YouTube ou google:	(doit être en rapport avec le sujet)
Votre mail:	(ne sera pas affiché sur le site)
Un pseudo:
Votre site:
Commentaire	(le html n'est pas autorisé, nombre de caractère maximum = 400)
	(Comment eBabylone 1.0 beta)

Le Texte ci-dessus est disponible sous GNU Free Documentation License.
La source est wikipedia http://fr.wikipedia.org/wiki/ plus grand commun diviseur