Calculează cel mai mare divizor comun, cmmdc.
Două metode utilizate mai jos.
Metoda 1. Descompunerea numerelor întregi în factori primi:
Descompunerea în factori primi a unui număr înseamnă găsirea numerelor prime care înmulțite dau ca rezultat acel număr.
5.477 e un număr prim, nu poate fi descompus în alți factori primi;
12 = 22 × 3;
12 nu e prim, e număr compus;
* Numerele pozitive întregi care nu se divid decât cu ele însele și cu 1, se numesc numere prime. Un număr prim are doar doi divizori: 1 și el însuși.
* Un număr compus e un întreg pozitiv care are cel puțin un divizor diferit de 1 și de numărul însuși.
Calculează cel mai mare divizor comun:
Se înmulțesc toți factorii primi comuni, la puterile cele mai mici.
DAR... Cele două numere nu au factori primi comuni.
cmmdc (5.477; 12) = 1;
numere coprime (prime între ele)
Numere coprime (prime între ele) (5.477; 12)? Da.
Numerele nu au factori primi comuni.
cmmdc (12; 5.477) = 1.
Metoda 2. Algoritmul lui Euclid:
Acest algoritm implică operația de împărțire și calcularea resturilor.
'a' și 'b' sunt cele două numere întregi pozitive, 'a' >= 'b'.
Împarte 'a' la 'b' și obține restul, 'r'.
Dacă 'r' = 0, STOP. 'b' = CMMDC al 'a' și 'b'.
Altfel: Înlocuiește ('a' cu 'b') și ('b' cu 'r'). Revino la pasul împărțirii, de mai sus.
Pasul 1. Împarte numărul mai mare la numărul mai mic:
5.477 : 12 = 456 + 5;
Pasul 2. Împarte numărul mai mic la restul operației de mai sus:
12 : 5 = 2 + 2;
Pasul 3. Împarte restul de la pasul 1 la restul de la pasul 2:
5 : 2 = 2 + 1;
Pasul 4. Împarte restul de la pasul 2 la restul de la pasul 3:
2 : 1 = 2 + 0;
La acest moment, restul e zero, ne oprim:
1 e numărul căutat, ultimul rest diferit de zero.
Acesta e cel mai mare divizor comun.
cmmdc (5.477; 12) = 1;
De ce răspunsul este un divizor al valorilor inițiale 'a' și 'b'?
Notă: 'a' : 'b' = 'q' + 'r' este echivalent cu ecuația: 'a' = 'q' × 'b' + 'r', unde 'q' este câtul operației.
Când valoarea finală a lui 'r' = 0, valoarea finală a lui 'b' este un divizor al valorii finale a lui 'a', deoarece 'a' = 'q' × 'b' + 0.
Mergi înapoi prin pașii anteriori și analizează fiecare ecuație, 'a' = 'q' × 'b' + 'r', și observă că la fiecare pas, valoarea finală a lui 'b' este un divizor al fiecărei valori a lui 'r' și a fiecărei valori a lui 'b' și, prin urmare, este un divizor al fiecărei valori a lui 'a'. Deci ultima valoare a lui 'b', care este ultimul rest diferit de zero, este un divizor al valorilor inițiale ale 'a' și 'b'.
De ce e răspunsul egal cu CMMDC?
Ne uităm la toate ecuațiile: 'a' = 'q' × 'b' + 'r'. După cum am văzut mai sus, valoarea finală a lui 'b' este un divizor al tuturor valorilor 'a', 'b' și 'r'.
Prin urmare, valoarea finală a lui 'b' trebuie să fie, de asemenea, un divizor al ultimei valori a lui 'r', cea care e diferită de zero. Iar valoarea finală a 'b' nu poate fi mai mare decât această ultima valoare a lui 'r'. Însă valoarea finală a lui 'b' e egală cu acea ultimă valoare a lui 'r', prin urmare valoarea finală a lui 'b' e cel mai mare divizor al valorilor inițiale ale lui ('a' și 'b'). Și prin definiție se numește cel mai mare divizor comun al numerelor.
Numere coprime (prime între ele) (5.477; 12)? Da.
cmmdc (12; 5.477) = 1.