Cel mai mare divizor comun

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

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

  • și ( este divizor comun al numerelor și );
  • orice alt divizor comun al numerelor și divide pe (adică ( și )).
Teorema:

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

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

Teorema:

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

Exemplu:

Dacă , atunci există numerele întregi și , astfel încât .

Observatii: Două numere întregi și se numesc prime între ele dacă . Deducem că două numere întregi și sunt prime între ele dacă și numai dacă există două numere întregi, și , astfel încât .[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:
  • ,
  • ,
  • ,

Deci:

Prin urmare:

Note modificare