Cel mai mare divizor comun

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

În matematică cel mai mare divizor comun al a două numere întregi Și , care nu sunt ambele egale cu zero , este indicat de și este cel mai mare număr natural prin care ambele pot fi împărțite. Dacă numerele Și sunt egale cu, atunci apare [1] .

De exemplu, , Și .

Adesea cel mai mare divizor comun este indicat mai simplu cu .

Două numere se numesc coprimă sau prime între ele , dacă cel mai mare divizor comun al lor este egal cu . De exemplu, numerele Și sunt prime între ele (chiar dacă nu sunt numere prime ).

Cel mai mare divizor comun este util pentru reducerea unei fracții la termenii săi cei mai mici. De exemplu, în următoarea fracție:

factorul a fost simplificat , cel mai mare divizor comun al Și .

Calculul celui mai mare factor comun

Cel mai mare factor comun poate fi calculat, în principiu, prin determinarea factorizării prime a celor două numere date și înmulțirea factorilor comuni, considerați o singură dată cu cel mai mic exponent al acestora . De exemplu, pentru a calcula mai întâi descompunem cele două numere în factori primi, obținând Și , și apoi luăm în considerare factorii comuni cu un exponent mai mic la cele două numere, Și : ambele apar cu un exponent minim egal cu , și atunci obținem asta . Dacă nu există factori primi comuni, GCD este iar cele două numere se numesc coprimă ; de exemplu: .

În practică, această metodă poate fi utilizată doar pentru numere foarte mici: descompunerea în factori primi a unui număr durează în general prea mult timp.

O metodă mult mai eficientă este oferită de algoritmul lui Euclid : acesta se împarte pentru obținerea unui coeficient de și un rest de . Apoi se desparte pentru obținerea unui coeficient de și un rest de . În cele din urmă se desparte pentru obținerea unui rest de, ceea ce înseamnă este cel mai mare divizor comun.

Proprietate

  • Fiecare divizor comun al Și este divizorul lui .
  • The , unde este Și nu sunt simultan egale cu zero, poate fi definit într-un mod alternativ și echivalent ca cel mai mic întreg pozitiv care poate fi scris în formă unde este Și sunt întregi. Această expresie se numește identitate Bézout .
  • De sine împarte produsul , Și , asa de împarte .
  • De sine este un număr întreg diferit de zero, atunci Și . De sine este un divizor comun diferit de zero al Și , asa de .
  • GCD este o funcție multiplicativă , adică dacă Și ei sunt mai întâi printre ei , apoi .
  • GCD de trei numere poate fi calculat ca . Deci MCD este o operație asociativă .
  • The este legat de cel mai mic multiplu comun : da
.
Această formulă este adesea utilizată pentru a calcula cel mai mic multiplu comun: calculați mai întâi GCD cu algoritmul lui Euclid și apoi împărțiți produsul celor două numere date cu GCD-ul lor.
.
  • Este util să se definească Și deoarece în acest fel numerele naturale devin o rețea distributivă completă cu GCD și MCM ca operații. Această extensie este, de asemenea, compatibilă cu generalizarea pentru inelele comutative date mai jos.
  • Într-un sistem de coordonate cartezian , poate fi interpretat ca numărul de puncte cu coordonate întregi pe segmentul de linie care unește punctele Și , excluzând punctul .

MCD în inele comutative

Cel mai mare divizor comun poate fi definit mai general pentru elementele unui inel comutativ arbitrar.

De sine este un inel comutativ și Și apartine , apoi un element din se numește divizorul comun al Și dacă le împarte pe amândouă acea (adică dacă există două elemente Și în astfel încât Și ). De sine este un divizor comun al Și , și orice divizor comun al Și împarte , asa de este numit cel mai mare divizor comun al Și .

Rețineți că, conform acestei definiții, două elemente Și pot avea mai mult de un cel mai mare divizor comun sau nici unul. Dar dacă este un domeniu de integritate, apoi orice două GCD Și trebuie să fie elemente asociate. De asemenea, dacă este un domeniu de factorizare unic , apoi orice două elemente au un GCD. De sine este un inel euclidian atunci GCD-urile pot fi calculate cu o variantă a algoritmului euclidian.

Următorul este un exemplu de domeniu de integritate cu două elemente care nu permit un MCD:

Elementele Și sunt doi „divizori comuni maximi” (adică orice divizor comun care este multiplu de Este asociat cu , și același lucru este valabil și pentru ), dar nu sunt asociate, deci nu există cel mai mare divizor comun al Și .

În mod similar cu proprietatea Bezout, putem considera, în orice inel comutativ, colecția de elemente din formă , unde este Și variază în interiorul inelului. Obținem idealul generat de Și , care este pur și simplu notat cu . Într-un inel ale cărui idealuri sunt toate principale (un „domeniu ideal principal” sau inel PID), acest ideal va fi identic cu setul de multipli ai unui element a inelului; apoi asta este cel mai mare divizor comun al Și . Dar idealul poate fi util chiar și atunci când nu există MCD Și (de fapt, Ernst Kummer a folosit acest ideal ca înlocuitor al GCD în studiul său asupra ultimei teoreme a lui Fermat , chiar dacă l-a considerat ca fiind setul de multipli ai unui element ipotetic sau ideal a inelului, de unde termenul ideal ).

Pseudo cod

În pseudocod , algoritmul poate fi explicat atât ca un algoritm recursiv, cât și într-un mod iterativ : în primul caz pur și simplu avem

  1. a = | a |, b = | b |
  2. sortează a și b în așa fel încât a > b
  3. dacă b = 0 atunci GCD ( a , b ) = a ; altfel GCD ( a , b ) = GCD ( b , a mod b )

În schimb, algoritmul iterativ poate fi descris ca

  1. a = | a |, b = | b |
  2. sortează a și b în așa fel încât a > b
  3. în timp ce b este diferit de 0
    1. t = b
    2. b = a mod b
    3. a = t
  4. GCD ( a , b ) = a

Notă

  1. ^ Hasse , p. 10 .

Bibliografie

Elemente conexe

Alte proiecte

linkuri externe

Controlul autorității Tezaur BNCF 34805
Matematica Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică