Cel mai mare divizor comun

Cel mai mare divizor comun (GCD) a două numere întregi m și n este cel mai mare divizor comun al acestora. [1] Exemplu: pentru numerele 70 și 105 este cel mai mare divizor comun al 35.

Cmmdc există și este unic determinată dacă cel puțin unul dintre numerele m sau n nu este zero.

Posibil denota cel mai mare divizor comun al numerelor m și n:

Conceptul de cmmdc fi în mod natural generalizat la seturi de mai mult de două numere întregi.

Cel mai puțin frecvente multiple

NOC pentru numere întregi nenule m și n sunt întotdeauna există și este asociată cu GCD următoarea relație:

Acesta este un caz special al unei teoreme mai general: dacă un 1. un 2. .... a n, o _, \ dots, a_> - numărul de zero, D - oricare, cu următoarea formulă lor multiplu comun deține:

relativ prim-

M și n sunt numite relativ prim. în cazul în care nu au divizori comuni, altele decât unitatea. Pentru aceste numere cmmdc (m, n) = 1. In schimb, daca cmmdc (m, n) = 1, atunci numerele sunt prime între ele.

În mod similar, numerele întregi un 1. 2. ... un k, o _, \ dots a_>. unde k ≥ 2. a declarat a fi relativ simplu. în cazul în care cea mai mare divizor comun este egal cu unu.

Este necesar să se facă distincția conceptului de ușurință reciprocă. când GCD set de numere este egal cu 1 și relativ prim pairwise. în cazul în care este GCD 1 pentru fiecare pereche de numere din setul. Din pairwise relativ prim implică simplitate, dar nu și invers. De exemplu, GCD (6,10,15) = 1, dar o pereche de oricare din acest set nu sunt relativ prime.

modalități eficiente de calculare a GCD a două numere sunt algoritmul lui Euclid și algoritmul binar.

unde p 1. .... p k, puncte \, P_> - amorse distincte, și d 1. .... d k, \ puncte, D_> și e 1. .... e k, \ puncte, E-> - numere întregi ne-negative (acestea pot fi zero în cazul în care pur și simplu corespunzător absent în expansiune). Apoi GCD (m, n) și NOC (m, n) sunt date de:

În cazul în care mai mult de două numere: a 1. 2. ... a n, o _, \ dots a_>. GCD lor este următorul algoritm:

  • Principala caracteristică: cel mai mare divizor comun al m și n este divizibil cu orice divizor comun al acestor numere. Exemplu: pentru numerele 12 și 18, cel mai mare divizor comun este egal cu 6; este divizibil cu toate divizorii comune ale numerelor 1, 2, 3, 6.
    • Corolar 1: o pluralitate de divizori comuni de m și n coincide cu GCD divizorilor set (n m.).
    • Corolar 2: o multitudine de multipli comuni de m și n coincide cu multimea LCM multiple (m n.).
  • Dacă m este împărțit de n. GCD (m. n) = n. În particular, GCD (n. N) = n.
  • (. A ⋅ m a ⋅ n) = | o | ⋅ (m n.) - factor comun poate fi luat ca un semn al GCD.
  • Dacă D = (m. N). după împărțirea la numărul de D sunt prime între ele, adică, (m D. n D) = 1>, >> \ dreapta) = 1>. Acest lucru înseamnă, printre altele, că, pentru a aduce împușcat la ireductibilă înseamnă că este necesar să se împartă numărătorul și numitorul prin GCD lor.
  • Multiplicativity. în cazul în care un 1. un 2, a_> sunt relativ prim, atunci:
(A 1 ⋅ a 2. b) = (a 1 b) ⋅ (a 2. b) \ cdot a_, b) = (a_, b) \ cdot (a_, b)>
  • Cel mai mare divizor comun al numerelor m și n poate fi definită ca fiind cel mai mic element pozitiv al setului de toate combinațiile liniare ale acestora:
\ Dreapta \ >> și deci (m. N) reprezentat ca o combinație liniară numerele m și n. (M. N) = u ⋅ m + v ⋅ n. Acest raport se numește Bézout relație. și coeficienții u și v - coeficienții Bézout. Coeficienții Bézout sunt calculate algoritmul euclidian extins în mod eficient. Această afirmație poate fi generalizat la seturi de numere naturale - sensul său este că subgrupul Z>. set generat ,o _, \ puncte, o _ \ >>. - ciclic și este generat de un singur element: GCD (a1 a2 ... o ...).

Variații și generalizări

Conceptul de divizibilitate de întregi natural fi generalizate la inel comutativ arbitrar. cum ar fi inelul polinoamelor numere întregi sau Gaussian. Cu toate acestea, pentru a determina cmmdc (a. B), ca cel mai mare divizor comun al unui. b este imposibilă, deoarece în astfel de inele, în general, nu este determinată de relație. Prin urmare, deoarece definiția este luat GCD proprietatea sa de bază:

Cea mai mare GCD divizor comun (a. B) se numește divizor comun, care este împărțit în toți ceilalți factori a și b comun.

Pentru numere naturale o nouă definiție este echivalentă cu cel vechi. Pentru numere întregi GCD într-un nou sens nu este deja clar: numărul său opus va, de asemenea, GCD. Pentru numărul de numere Gaussian de NOD diferite crește la 4.

GCD a două elemente ale unui inel comutativ, în general vorbind, nu trebuie să existe. De exemplu, pentru următoarele elemente a și b ale inelului Z [- 3] \ stânga [> \ dreapta]> nu există nici cel mai mare divizor comun:

În inele euclidiene cel mai mare divizor comun există întotdeauna și este determinată de până la divizorii unității. adică numărul de noduri este numărul de divizori de unitate în ring.