Cel mai mare divizor comun

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

Este numit c.m.m.d.c. un număr întreg ${\displaystyle d}$ având proprietățile:

• ${\displaystyle d|a}$ și ${\displaystyle d|b}$ (${\displaystyle d}$ este divizor comun al numerelor ${\displaystyle a}$ și ${\displaystyle b}$);
• orice alt divizor comun ${\displaystyle d'}$ al numerelor ${\displaystyle a}$ și ${\displaystyle b}$ divide pe ${\displaystyle d}$ (adică (${\displaystyle d'|a}$ și ${\displaystyle d'|b=>d'|d}$)).

Teorema:

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

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

Teorema:

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

Exemplu:

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

Observatii: Două numere întregi ${\displaystyle a}$ și ${\displaystyle b}$ se numesc prime între ele dacă ${\displaystyle (a;b)=1}$. Deducem că două numere întregi ${\displaystyle a}$ și ${\displaystyle b}$ sunt prime între ele dacă și numai dacă există două numere întregi, ${\displaystyle k1}$ și ${\displaystyle k2}$, astfel încât ${\displaystyle 1}$ ${\displaystyle =}$ ${\displaystyle k}$${\displaystyle 1}$ ${\displaystyle .}$ ${\displaystyle a}$ ${\displaystyle +}$ ${\displaystyle k}$${\displaystyle 2}$ ${\displaystyle .}$ ${\displaystyle 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:

• ${\displaystyle a=12=2^{2}\cdot 3}$,
• ${\displaystyle b=8=2^{3}}$,
• ${\displaystyle c=20=2^{2}\cdot 5}$,

Deci:

${\displaystyle d=2^{2}=4}$

Prin urmare:

${\displaystyle d=(12,8,20)=4}$

Note

Acest articol legat de matematică este deocamdată un ciot. Poți ajuta Wikipedia prin completarea lui.