Cel mai mare divizor comun

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare

Un număr întreg d se numește cel mai mare divizor comun (prescurtat c.m.m.d.c.) a numerelor întregi a și b dacă și numai dacă pentru orice divizor comun c al lui a și b, d este un divizor al lui c.

Este numit c.m.m.d.c. un număr întreg d având proprietățile:

  • d|a și d|b (d este divizor comun al numerelor a și b);
  • orice alt divizor comun d' al numerelor a și b divide pe d (adică (d'|a și d'|b = > d'|d)).
Teorema:

Fie a și b două numere întregi. Atunci există exact două numere întregi opuse, d și (-d), cu statut de c.m.m.d.c. al numerelor a și b.

Observație: Numărul pozitiv dintre cele două se noteaza (a;b), iar valoarea sa se calculează folosind algoritmul lui Euclid.

Teorema:

Fie a și b două numere întregi și d un c.m.m.d.c. al lor (oricare din cei doi). Atunci există două numere întregi, k1 și k2, astfel încât d = k1 . a + k2 . b.

Exemplu:

Dacă -3 = (6;9), atunci există numerele întregi -2 și 1, astfel încât -3 = (-2) . 6 + 1 . 9.

Observatii: Două numere întregi a și b se numesc prime între ele dacă (a;b) = 1. Deducem că două numere întregi a și b sunt prime între ele dacă și numai dacă există două numere întregi, k1 și k2, astfel încât 1 = k1 . a + k2 . b.[1]

Algoritmul privind calculul c.m.m.d.c.:
  1. Se descompun numerele în factori primi;
  2. Se aleg factorii primi comuni (o singură dată fiecare), cu exponentul cel mai mic și se înmulțesc între ei.

Produsul obținut este c.m.m.d.c. căutat.

Exemplu:
  • a = 12 = 2^2 \cdot 3,
  • b = 8 = 2^3,
  • c = 20 = 2^2 \cdot 5,

Deci:

d = 2^2 = 4

Prin urmare:

d = [12, 8, 20] = 4

Note[modificare | modificare sursă]