Considerăm mai întâi o metodă bazată pe descompunerea acestor numere în factori primari.
Se dau două numere 3600 și 288. Noi le reprezentăm în formă canonică: 3600 = 2 4 × 3 2 × 5 2; 288 = 2 5 × 3 2. Să găsim cel mai mare divizor comun al acestor numere. Descompunerea sa ar trebui să includă toți factorii primari comuni cuprinși în expansiunile numerelor 3600 și 288, fiecare dintre acestea urmând să fie luate cu cel mai mic exponent. cu care intră în ambele expansiuni. Prin urmare, D (3600, 288) = 2 4 × 3 2 = 144.
În general, pentru a găsi cel mai mare divizor comun al acestor numere:
1) reprezintă fiecare număr dat în forma canonică;
2) formează un produs de multiplicatori similari comune tuturor numerelor date, fiecare având cel mai mic exponent când intră în toate expansiunile acestor numere;
3) găsiți valoarea acestui produs - acesta va fi cel mai mare divizor comun al acestor numere.
Vom găsi cel mai mic multiplu comun al 3600 și 288. În extinderea sa trebuie să intre toți factorii principali, care sunt cuprinse în cel puțin una dintre reprezentările de numere 3600 și 288, iar fiecare dintre ele trebuie să ia cu cea mai mare rată, cu care este inclusă în ambele extinderi. Prin urmare,
K (3600, 288) = 2 5 x 3 2 x 5 = 7200.
În general, pentru a găsi cel mai mic număr comun dintre aceste numere:
1) reprezintă fiecare număr dat în forma canonică;
2) formează produsul tuturor factorilor primari în extinderea acestor numere, fiecare cu cel mai mare exponent cu care intră în toate expansiunile acestor numere;
3) găsiți valorile acestui produs, acesta va fi cel mai mic număr comun de numere.
Problema 1. Găsiți cel mai mare divizor comun și cel mai puțin comun multiplu al numerelor 60, 252 și 264.
Soluția. Reprezentăm fiecare număr în forma canonică: 60 = 2 2 × 3 × 5, 252 = 2 2 × 3 2 × 7, 264 = 2 3 × 3 × 11.
Pentru a găsi cel mai mare divizor comun al acestor numere forma produsul sunt comune tuturor acestor expansiunile factori de prim, fiecare cu cea mai scăzută rată, cu care este inclusă în toate deciziile de numere date: D (60252264) = 02 februarie × 3 = 12.
Cel mai mic multiplu comun al numerelor pot fi găsite, formând PRODUCEREA denie toți factorii principali care sunt în aceste extinderi, fiecare cu cea mai mare rată, cu care el intră în toate numerele de date de expansiune-TION, și anume K (60, 252, 264) = 2 3 x 3 2 x 5 x 7 x 11 = 27 7 20.
Problema 2. Găsiți cel mai mare divizor comun și cel mai puțin comun multiplu al numerelor 48 și 245.
Soluția. Reprezentăm fiecare număr în forma canonică: 48 = 2 4 × 3, 245 = 5 × 7 2.
Deoarece extensiile acestor numere nu conțin factori primari comuni, atunci D (48, 245) = 1 și K (48, 245) = 48 × 245 = 10760.
Găsirea celui mai mare divizor comun a două numere naturale prin forma lor canonică necesită o descompunere preliminară a numerelor în primii factori. Acest lucru nu este greu de făcut dacă numerele nu sunt mari, dar pentru numerele cu valoare mare este dificil să se găsească descompunerea lor canonică. Există o modalitate de a găsi cel mai mare divizor comun, care necesită doar divizarea cu restul. Această metodă a fost propusă de Euclid și se numește algoritmul euclidian. Se bazează pe următoarele trei afirmații, dovada căruia omitem:
1. Dacă a este divizibil cu b, atunci D (a, b) = b.
2. Dacă a = bq + r și r 3. Dacă a = bq + r și r Formulăm acum algoritmul lui Euclid pentru a găsi cel mai mare divizor comun al numerelor naturale a și b. Dacă a este divizibil cu b, atunci D (a, b) = b. În cazul în care divizarea unei prin b, reziduul obținut prin r, atunci a = bq + r și D (a, b) = D (b, r) și problema se reduce la găsirea celui mai mare divizor comun al numerelor b și r. Dacă b este divizibil cu r, atunci D (b, r) = r și apoi D (a, b) = r. Dacă restul r este obținut împărțind b cu r. atunci b = rq1 + r1 și prin urmare D (r, r1) = D (b, r) = D (a, b). Continuând procesul descris, obținem toate reziduurile mai mici și mai mici. În cele din urmă, vom obține restul, la care se va împărți soldul anterior. Acest rest mic cel mai mic u va fi cel mai mare divizor comun al numerelor a și A. Să găsim prin algoritmul lui Euclid cel mai mare divizor comun al numerelor 2585 și 7975. Procesul de diviziune secvențială va fi scris astfel: 7755 3 975 = 2585 3 + 220. 220 11 2585 = 220 x 11 + 165 165 1 220 = 165 × 1 + 55