Matematică Aritmetică
Formula de calcul pentru cmmdc
Formula de calcul pentru cmmdc (cel mai mare divizor comun) a două numere se bazează pe algoritmul lui Euclid, care folosește împărțiri succesive. Cmmdc-ul este cel mai mare număr care divide ambele numere fără rest. De exemplu, cmmdc(12, 18) = 6.
Algoritmul lui Euclid
- 1 Pasul 1: Împarte numărul mai mare la cel mai mic Fie a și b două numere, cu a ≥ b. Calculează restul r = a mod b.
- 2 Pasul 2: Înlocuiește a cu b și b cu r Dacă r ≠ 0, repetă procesul cu a = b și b = r.
- 3 Pasul 3: Continuă până când restul este 0 Când r = 0, cmmdc este ultimul divizor nenul, adică b din pasul anterior.
Exemple de calcul
- Exemplul 1: cmmdc(48, 18) 48 : 18 = 2 rest 12, 18 : 12 = 1 rest 6, 12 : 6 = 2 rest 0, deci cmmdc = 6.
- Exemplul 2: cmmdc(35, 14) 35 : 14 = 2 rest 7, 14 : 7 = 2 rest 0, deci cmmdc = 7.
- Exemplul 3: cmmdc(17, 5) 17 : 5 = 3 rest 2, 5 : 2 = 2 rest 1, 2 : 1 = 2 rest 0, deci cmmdc = 1 (numere prime între ele).
Folosește algoritmul lui Euclid pentru numere mari, este mai rapid decât descompunerea în factori primi.