Plus grand commun diviseur

À propos de ce écoles sélection Wikipedia

SOS Enfants a fait cette sélection Wikipedia aux côtés d'autres écoles des ressources . Une bonne façon d'aider d'autres enfants est de parrainer un enfant

En mathématiques , le plus grand commun diviseur (PGCD de), parfois connu comme le plus grand facteur commun (GCF) ou un facteur plus commune (HCF), de deux non-zéro entiers , est le plus grand entier positif qui divise les deux numéros sans reste.

Vue d'ensemble

Le plus grand commun diviseur de a et b se écrit pgcd (a, b), ou parfois simplement en tant que (a, b). Par exemple, gcd (12, 18) = 6, gcd (-4, 14) = 2 et pgcd (5, 0) = 5. Deux nombres sont appelés premiers entre eux ou relativement premier si leur plus grand commun diviseur est égal à 1. Par exemple, 9 et 28 sont premiers.

Le plus grand commun diviseur est utile pour réduire fractions vulgaires être en termes plus bas. Par exemple, gcd (42, 56) = 14, par conséquent,

${42 \ plus de 56} = {3 \ cdot 14 \ plus de 4 \ cdot 14} = {3 \ plus de 4}.$

Calcul du pgcd

Plus grands communs diviseurs peuvent en principe être calculé en déterminant le facteurs premiers des deux numéros et comparant des facteurs, comme dans l'exemple suivant: pour calculer PGCD (18,84), on trouve les facteurs premiers 18 = 2 · 3 ² et 84 = 2 ² · 3 · 7 et notez que le " chevauchement "des deux expressions est 2 · 3; si pgcd (18,84) = 6. Dans la pratique, cette méthode ne est possible que pour les très petits nombres; calcul facteurs premiers en général prend trop longtemps.

Un procédé beaucoup plus efficace est le Algorithme d'Euclide, qui utilise le algorithme de division en combinaison avec l'observation que le pgcd de deux nombres divise aussi leur différence: diviser 84 par 18 pour obtenir un quotient de 4 et un reste de 12. Ensuite, divisez 18 par 12 pour obtenir un quotient de 1 et un reste de 6 . Ensuite, divisez 12 par 6 pour obtenir un reste de 0, ce qui signifie que 6 est le pgcd.

La série de quotients générés par l'algorithme d'Euclide composer un fraction continue.

Si A et B ne sont pas tous deux zéro, le plus grand commun diviseur de a et b peut être calculée en utilisant moins commun multiple (LCM) de a et b:

$\ Operatorname {} pgcd (a, b) = \ frac {a \ cdot b} {\ operatorname {} LCM (a, b)}.$

Propriétés

Chaque grand commun diviseur de a et b est un diviseur de pgcd (a, b).

pgcd (a, b), où a et b sont pas tous deux zéro, peut être définie alternativement et de façon équivalente comme le plus petit entier positif d qui peut être écrit sous la forme d = a · p + B · q où p et q sont des nombres entiers . Cette expression est appelé L'identité de Bézout. Numéros de p et q comme ceci peuvent être calculés avec le algorithme d'Euclide étendu.

pgcd (a, 0) = | a |, pour a ≠ 0, étant donné que ne importe quel nombre est un diviseur de 0, et le plus grand diviseur de a est | a |. Ceci est habituellement utilisé en tant que cas de référence à l'algorithme d'Euclide.

Si a divise le produit b · c et pgcd (a, b) = D, puis un / d divise c.

Si m est un entier non-négatif, alors pgcd (m · a, m · b) = m · pgcd (a, b).

Si m est un nombre entier, alors pgcd (a + b · m, b) = pgcd (a, b). Si m est un diviseur commun non nul de A et B, puis pgcd (a / m, b / m) = pgcd (a, b) / m.

Le GCD est un fonction multiplicative dans le sens suivant: si un ₁ et ₂ sont relativement premier, alors pgcd (a ₁ · _2, b) = pgcd (a _1, b) · pgcd (a _2, b).

Le GCD est un commutative fonction: PGCD (a, b) = pgcd (b, a).

Le GCD est un associative fonction: pgcd (a, pgcd (b, c)) = PGCD (gcd (a, b), c).

Le pgcd de trois chiffres peut être calculée comme pgcd (a, b, c) = PGCD (gcd (a, b), c), ou dans quelque autre manière en appliquant la commutativité et l'associativité. Ceci peut être étendu à un nombre quelconque de nombres.

pgcd (a, b) est étroitement liée à la LCM plus petit commun multiple (a, b): nous avons

pgcd (a, b) · LCM (a, b) = a · b.

Cette formule est souvent utilisée pour calculer multiples moins communs: on calcule d'abord le PGCD avec l'algorithme d'Euclide, puis divise le produit des chiffres donnés par leur pgcd. Les versions suivantes de Distributivité être vrai:

pgcd (a, LCM (b, c)) = LCM (PGCD (a, b), pgcd (a, c))

LCM (a, pgcd (b, c)) = pgcd (LCM (a, b), LCM (a, c)).

Il est utile de définir pgcd (0, 0) = 0 et LCM (0, 0) = 0 car alors les nombres naturels deviennent une complet distributif treillis avec pgcd que se rencontrent et LCM comme opération de jointure. Cette extension de la définition est également compatible avec la généralisation des anneaux commutatifs ci-dessous.

Dans un système de coordonnées cartésiennes , pgcd (a, b) peut être interprété comme le nombre de points de coordonnées intégrée pour la ligne droite reliant les points (0, 0) et (a, b), à l'exclusion (0, 0).

Probabilités et valeur attendue

La probabilité que deux entiers choisis au hasard (illimité) $Un$ et $B$ avoir un plus grand commun diviseur donné $ré$ est $6 \ over {\ pi ^ 2 d ^ 2}$ . Cela découle de la caractérisation de $PGCD (A, B)$ comme le nombre entier $ré$ tel que $d | A, B$ et $A / d$ et $B / d$ sont premiers entre eux. La probabilité de deux entiers partager un facteur $ré$ est $d ^ {- 2}$ . La probabilité que deux entiers premiers entre eux sont est $1 / \ zeta (2) = 6 / \ pi ^ 2$ . (Voir premiers entre eux pour une dérivation).

En utilisant cette information, la valeur attendue du plus grand commun diviseur de fonction peut être calculée. C'est

$\ Mathrm {E} (\ mathrm {2}) = \ sum_ {d = 1} ^ {\ infty} d \ frac {6} {\ pi ^ 2 d ^ 2} = \ frac {6} {\ pi ^ 2} \ sum_ {d = 1} ^ {\ infty} \ frac {1} {d}.$

Cette dernière est la sommation Série harmonique, qui diverge. D'où la valeur attendue du plus grand commun diviseur des deux variables ne est pas bien définie. Ce ne est pas le cas en général, cependant. Pour le plus grand commun diviseur de $k \ ge 3$ des variables, la valeur attendue est bien défini, et par l'argument ci-dessus, il est

$\ Mathrm {} E (k) = \ sum_ {d = 1} ^ {\ infty} d ^ {k-1} \ zeta (k) ^ {- 1} = \ frac {\ zeta (k-1)} {\ zeta (k)}.$

où $\ Zeta (k)$ est le Fonction zêta de Riemann.

Pour $k = 3$ , Ce est approximativement égale à 1,3684. Pour $k = 4$ , Il est d'environ 1,1106.

si tous les nombres entiers x sont limités $m \ ge x \ ge 1$ les résultats peuvent être étendus à

$\ Mathrm {} E (k, m) = \ frac {\ sum_ {d = 1} ^ {m} d ^ {k-1}} {\ sum_ {t = 1} ^ {m} t ^ {- k }} = \ frac {\ zeta (k-1) - \ zeta (k-1, m + 1)} {\ zeta (k) - \ zeta (k, m + 1)}.$

où $\ Zeta (k, m)$ est le Fonction zeta Hurwitz.

se ils sont différents $m$ 'S sont connus pour différents $x$ puis le meilleur $m$ est pris.

Le PGCD dans les anneaux commutatifs

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

Si R est un anneau commutatif, et a et b sont dans R, un élément de R d est appelé un grand commun diviseur de a et b se il divise la fois A et B (qui est, si il ya des éléments x et y dans R tel que d · x = a et d · y = b). Si d est un diviseur commun de A et B, et chaque grand commun diviseur de a et b divise d, alors d est appelé un plus grand commun diviseur de a et b.

Notez qu'avec cette définition, deux éléments a et b peuvent très bien avoir plusieurs diviseurs plus communs, ou pas du tout. Mais si R est un domaine intégrante alors toutes les deux pgcd de a et b doit être éléments associés. En outre, si R est un Anneau factoriel, puis deux éléments ont un pgcd. Si R est un Domaine euclidienne alors une forme de l'algorithme d'Euclide peuvent être utilisés pour calculer diviseurs plus communs.

Ce qui suit est un exemple d'un domaine solidaire de deux éléments qui ne ont pas de GCD:

$R = \ mathbb {Z} \ left [\ sqrt {-3} \ right], \ quad a = 4 = 2 \ cdot 2 = \ left (1+ \ sqrt {-3} \ right) \ left (1- \ sqrt {-3} \ right), \ quad b = \ left (1+ \ sqrt {-3} \ right) \ cdot 2.$

Les éléments $1+ \ sqrt {-3}$ et $2$ deux diviseurs communs "extrêmes" (ce est à dire ne importe quel diviseur commun qui est un multiple de 2 est associé à deux, il en est de même pour $1+ \ sqrt {-3}$ ), Mais ils ne sont pas associés, donc il n'y a pas de plus grand commun diviseur de a et b.

Correspondant à la propriété Bezout nous peut, en tout anneau commutatif, envisager la collecte des éléments de la forme $P A + q b$ , Où p et q gamme sur l'anneau. Ceci est le idéal engendré par a et b, et est noté tout simplement $(A, b)$ . Dans un anneau dont tous les idéaux sont les principaux (un anneau principal ou PID), cet idéal sera identique à l'ensemble des multiples de certains éléments de l'anneau D; puis ce d est un plus grand commun diviseur de a et b. Mais l'idéal $(A, b)$ peuvent être utiles, même lorsqu'il n'y a pas plus grand commun diviseur de a et b. (En Effet, Ernst Kummer utilisé cet idéal comme un remplacement pour un GCD dans son traitement de dernier théorème de Fermat , bien qu'il l'envisageait comme l'ensemble des multiples de certains hypothétique ou idéal, élément annulaire d, d'où le terme de cycle théorique.)

Récupéré à partir de " http://en.wikipedia.org/w/index.php?title=Greatest_common_divisor&oldid=203192050 "