Cel mai mare divizor comun

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$ , $c$ este un divizor al lui $d$ .

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$ $=$ $k$ $1$ $.$ $a$ $+$ $k$ $2$ $.$ $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$ $=$ $k$ $1$ $.$ $a$ $+$ $k$ $2$ $.$ $b$ .^[1]