Să luăm în considerare două moduri de a găsi cel mai mare divizor comun.
Constatare prin factorizare
Prima metodă este de a găsi cel mai mare divizor comun prin factorizarea numerelor date în factori primi.
Pentru a găsi mcd-ul mai multor numere, este suficient să le descompunem în factori primi și să-i înmulțim între ei pe cei care sunt comuni tuturor numerelor date.
Exemplul 1. Să găsim GCD (84, 90).
Factorăm numerele 84 și 90 în factori primi:
Deci, am evidențiat toți factorii primi comuni, nu rămâne decât să-i înmulțim: 1 · 2 · 3 = 6.
Astfel, GCD (84, 90) = 6.
Exemplul 2. Să găsim GCD (15, 28).
Factorim 15 și 28 în factori primi:
Numerele 15 și 28 sunt relativ prime deoarece cel mai mare divizor comun al lor este unul.
GCD (15, 28) = 1.
algoritmul lui Euclid
A doua metodă (altfel numită metoda euclidiană) este de a găsi GCD prin împărțire secvențială.
Mai întâi ne vom uita la această metodă aplicată doar la două numere date, apoi ne vom uita la cum să o aplicăm la trei sau mai multe numere.
Dacă cel mai mare dintre două numere date este divizibil cu cel mai mic, atunci numărul mai mic va fi cel mai mare divizor comun al lor.
Exemplul 1. Să luăm două numere 27 și 9. Deoarece 27 este divizibil cu 9 și 9 este divizibil cu 9, înseamnă că 9 este divizorul comun al numerelor 27 și 9. Acest divizor este în același timp și cel mai mare, deoarece 9 nu poate fi împărțit la orice număr, mai mare decât 9. Prin urmare, mcd (27, 9) = 9.
În alte cazuri, pentru a găsi cel mai mare divizor comun a două numere, utilizați următoarea procedură:
- Dintre două numere date, numărul mai mare este împărțit la numărul mai mic.
- Apoi, numărul mai mic este împărțit la restul obținut din împărțirea numărului mai mare la numărul mai mic.
- În continuare, primul rest este împărțit la al doilea rest, care se obține prin împărțirea numărului mai mic la primul rest.
- Al doilea rest se împarte la al treilea, care se obține prin împărțirea primului rest la al doilea etc.
- Astfel, împărțirea continuă până când restul este zero. Ultimul divizor va fi cel mai mare divizor comun.
Exemplul 2. Să găsim cel mai mare divizor comun al numerelor 140 și 96:
1) 140: 96 = 1 (restul 44)
2) 96: 44 = 2 (restul 8)
3) 44: 8 = 5 (restul 4)
Ultimul divizor este 4 - asta înseamnă că mcd (140, 96) = 4.
Împărțirea consecutivă poate fi scrisă și într-o coloană:
Pentru a găsi cel mai mare divizor comun a trei sau mai multe numere date, folosim următoarea procedură:
- În primul rând, găsim cel mai mare divizor comun al oricăror două numere din mai multe date.
- Apoi găsim mcd-ul divizorului găsit și un al treilea număr dat.
- Apoi găsim mcd-ul ultimului divizor găsit și al patrulea număr dat și așa mai departe.
Exemplul 3. Să găsim cel mai mare divizor comun al numerelor 140, 96 și 48. Am găsit deja mcd-ul numerelor 140 și 96 în exemplul anterior (acesta este numărul 4). Rămâne de găsit cel mai mare divizor comun al numărului 4 și al treilea număr dat - 48:
48 este divizibil cu 4 fără rest. Astfel, mcd (140, 96, 48) = 4.
Reprezentarea unui număr ca produs al numerelor prime se numește prin factorizarea acestui număr în factori primi.
De exemplu, scrierea 110 = 2 5 11 înseamnă că numărul 110 este factorizat în factori primi 2, 5 și 11.
În general, orice număr compus poate fi descompus în factori primi, iar cu orice metodă se obține aceeași descompunere, dacă nu se ține cont de ordinea factorilor. Prin urmare, reprezentările numărului 110 sub forma unui produs de 2 · 5 · 11 sau a unui produs de 5 · 2 · 11 sunt, în esență, aceeași descompunere a numărului 110 în factori primi.
Când descompunem numerele în factori primi, folosind semnele împărțirii cu 2, 3, 5 etc., să ne amintim modul de a scrie descompunerea unui număr în factori primi. Să descompunăm, de exemplu, numărul 720 în factori primi Numărul 720 este divizibil cu 2. Aceasta înseamnă că 2 este unul dintre factorii primi în descompunerea numărului 720. Împărțiți 720 la 2. Se scrie numărul 2. în dreapta semnului egal, iar câtul 360 este scris sub numărul 720. Număr Împărțiți 360 la 2, obținem 180. Împărțiți 180 la 2, obținem 90, împărțim 90 la 2, obținem 45, împărțim 45 la 3, obținem 15, împărțim 15 la 3, obținem 5. Numărul 5 este prim, când îl împărțim la 5 obținem 1. Factorizarea este completă.
720 = 2 2 2 2 3 3 5
Produsul factorilor identici este de obicei înlocuit cu o putere: 720 = 5. Această reprezentare a numărului 720 se numește vedere canonică acest număr.
Factorizarea unui număr în factori primi este folosită pentru a-și găsi cel mai mare divizor comun și cel mai mic multiplu comun.
Să găsim, de exemplu, cel mai mare divizor comun și cel mai mic multiplu comun al numerelor 3600 și 288.
Să reprezentăm fiecare dintre aceste numere în formă canonică.
3600 = 2 · 2 · 2 · 2 · 3 · 3 · 5 · 5 = · · ; 288 = 2 2 2 2 2 3 3 =
În descompunerea în factori primi a celui mai mare divizor comun al numerelor 3600 și 288, toate trebuie incluse înmulțiți numere prime comune, care sunt cuprinse în expansiunile acestor numere și fiecare dintre ele trebuie luat din cea mai mică rată cu care intră ambele expansiuni. Prin urmare, extinderea celui mai mare divizor comun al numerelor 3600 și 288 va include factorii și . Deci D (3600? 288) = · = 144.
Descompunerea în factori primi a celui mai mic multiplu comun al lui 3600 și 288 trebuie să includă toți factorii primi conținuti în cel putin intr-una din expansiunile numerelor 3600 si 288 si trebuie luate fiecare dintre ele cu cea mai mare rată incluse în ambele extinderi ale acestor numere. Prin urmare, extinderea celui mai mic multiplu comun al lui 3600 și 288 va include factorii , , 5. Aceasta înseamnă
K (3600, 288) = · · 5 = 7200.
În general, pentru a găsi cel mai mare divizor comun al numerelor date:
2) Formăm produsul factorilor primi comuni tuturor numerelor date și luăm fiecare dintre ei cu cel mai mic exponent cu care este inclus în toate expansiunile acestor numere;
3) Aflați valoarea acestui produs - acesta va fi cel mai mare divizor comun al acestor numere.
Pentru a găsi cel mai mic multiplu comun al numerelor date:
1) Reprezentăm fiecare număr dat în formă canonică;
2) Formăm un produs din toți factorii primi găsiți în expansiunile acestor numere și luăm pe fiecare cu cel mai mare exponent cu care este inclus în toate expansiunile numerelor date;
3) Aflați valoarea acestui produs - acesta va fi cel mai mic multiplu comun al acestor numere.
Să luăm în considerare două metode principale pentru a găsi GCD în două moduri principale: folosind algoritmul euclidian și prin factorizarea în factori primi. Să aplicăm ambele metode pentru două, trei sau mai multe numere.
Yandex.RTB R-A-339285-1
Algoritm euclidian pentru găsirea GCD
Algoritmul euclidian facilitează calcularea celui mai mare factor comun a două numere pozitive. Am prezentat formulările și dovezile algoritmului Euclid în secțiunea „Cel mai mare divizor comun: determinant, exemple”.
Esența algoritmului este de a efectua secvențial împărțirea cu un rest, timp în care se obțin o serie de egalități de formă:
a = b q 1 + r 1 , 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1
Putem termina diviziunea când r k + 1 = 0, în timp ce r k = mcd (a, b).
Exemplul 1
64 Şi 48 .
Soluţie
Să introducem următoarele notații: a = 64, b = 48.
Pe baza algoritmului euclidian, vom efectua împărțirea 64 pe 48 .
Obținem 1 și restul 16. Se dovedește că q 1 = 1, r 1 = 16.
Al doilea pas este împărțirea 48 până la 16, obținem 3. Adică q 2 = 3, A r 2 = 0 . Astfel, numărul 16 este cel mai mare divizor comun pentru numerele din condiție.
Răspuns: GCD (64, 48) = 16.
Exemplul 2
Care este GCD-ul numerelor? 111 Şi 432 ?
Soluţie
Ne împărțim 432 pe 111 . Conform algoritmului euclidian, obținem lanțul de egalități 432 = 111 · 3 + 99, 111 = 99 · 1 + 12, 99 = 12 · 8 + 3, 12 = 3 · 4.
Astfel, cel mai mare divizor comun al numerelor este 111 Şi 432 – acesta este 3.
Răspuns: GCD (111, 432) = 3.
Exemplul 3
Aflați cel mai mare divizor comun al numerelor 661 și 113.
Soluţie
Să împărțim succesiv numerele și să obținem GCD (661 , 113) = 1 . Aceasta înseamnă că 661 și 113 sunt numere relativ prime. Am putea să ne dăm seama înainte de a începe calculul dacă am consulta un tabel cu numere prime.
Răspuns: GCD (661, 113) = 1.
Găsirea GCD prin factorizarea numerelor în factori primi
Pentru a găsi cel mai mare divizor comun a două numere folosind metoda descompunerea în factori, este necesar să înmulțiți toți factorii primi obținuți prin factorizarea acestor două numere și care le sunt comuni.
Exemplul 4
Dacă factorăm numerele 220 și 600 în factori primi, obținem două produse: 220 = 2 2 5 11Şi 600 = 2 2 2 3 5 5. Factorii comuni în aceste două produse sunt 2, 2 și 5. Aceasta înseamnă că GCD (220, 600) = 2 2 5 = 20.
Exemplul 5
Găsiți cel mai mare divizor comun al numerelor 72 Şi 96 .
Soluţie
Găsiți toți factorii primi ai numerelor 72 Şi 96 :
72 36 18 9 3 1 2 2 2 3 3
96 48 24 12 6 3 1 2 2 2 2 2 3
Factorii primi comuni pentru două numere sunt 2, 2, 2 și 3. Aceasta înseamnă că GCD (72, 96) = 2 2 2 3 = 24.
Răspuns: GCD (72, 96) = 24.
Regula pentru găsirea celui mai mare divizor comun a două numere se bazează pe proprietățile celui mai mare divizor comun, conform cărora mcd (m a 1, m b 1) = m mgcd (a 1, b 1), unde m este orice număr întreg pozitiv .
Găsirea mcd-ului a trei sau mai multe numere
Indiferent de numărul de numere pentru care trebuie să găsim GCD-ul, vom urma același algoritm, care constă în găsirea secvenţială a GCD-ului a două numere. Acest algoritm se bazează pe aplicarea următoarei teoreme: GCD a mai multor numere a 1 , a 2 , … , a k egală cu numărul dk, care se găsește prin calcularea secvenţială a mcd (a 1 , a 2) = d 2, GCD (d 2 , a 3) = d 3 , GCD (d 3 , a 4) = d 4 , … , GCD (d k - 1 , a k) = d k .
Exemplul 6
Aflați cel mai mare divizor comun al patru numere 78, 294, 570 și 36 .
Soluţie
Să introducem notația: a 1 = 78, a 2 = 294, a 3 = 570, a 4 = 36.
Să începem prin a găsi mcd-ul numerelor 78 și 294: d 2 = GCD (78 , 294) = 6 .
Acum să începem să găsim d 3 = GCD (d 2 , a 3) = GCD (6, 570). Conform algoritmului euclidian 570 = 6 95. Aceasta înseamnă că d 3 = GCD (6 , 570) = 6 .
Să aflăm d 4 = GCD (d 3 , a 4) = GCD (6, 36). 36 divizibil cu 6 fara rest. Acest lucru ne permite să obținem d 4 = GCD (6 , 36) = 6 .
d4 = 6, adică GCD (78 , 294 , 570 , 36) = 6 .
Răspuns:
Acum să ne uităm la un alt mod de a calcula GCD pentru acele numere și mai multe. Putem găsi mcd înmulțind toți factorii primi comuni ai numerelor.
Exemplul 7
Calculați MCD-ul numerelor 78, 294, 570 și 36 .
Soluţie
Să descompunăm aceste numere în factori primi: 78 = 2 3 13, 294 = 2 3 7 7, 570 = 2 3 5 19, 36 = 2 2 3 3.
Pentru toate cele patru numere, factorii primi comuni vor fi numerele 2 și 3.
Se pare că GCD (78, 294, 570, 36) = 2 3 = 6.
Răspuns: GCD (78, 294, 570, 36) = 6.
Găsirea GCD de numere negative
Dacă avem de-a face cu numere negative, atunci putem folosi modulele acestor numere pentru a găsi cel mai mare divizor comun. Putem face acest lucru, cunoscând proprietatea numerelor cu semne opuse: numerele nŞi - n au aceiași divizori.
Exemplul 8
Găsiți mcd-ul numerelor întregi negative − 231 Şi − 140 .
Soluţie
Pentru a efectua calcule, luăm modulele numerelor date în condiție. Acestea vor fi numerele 231 și 140. Să-l notăm pe scurt: GCD (− 231 , − 140) = GCD (231, 140). Acum aplicăm algoritmul Euclid pentru a găsi factori primi ai două numere: 231 = 140 · 1 + 91 ; 140 = 91 · 1 + 49; 91 = 49 · 1 + 42; 49 = 42 1 + 7 și 42 = 7 6. Obținem că GCD (231, 140) = 7 .
Și de când GCD (− 231 , − 140) = GCD (231 , 140) , apoi mcd de numere − 231 Şi − 140 egală 7 .
Răspuns: GCD (− 231, − 140) = 7.
Exemplul 9
Determinați mcd a trei numere − 585, 81 și − 189 .
Soluţie
Vom înlocui numere negativeîn lista dată pe lor valori absolute, obținem gcd (− 585 , 81 , − 189) = GCD (585 , 81 , 189) . Apoi factorăm toate aceste numere în factori primi: 585 = 3 3 5 13, 81 = 3 3 3 3 și 189 = 3 3 3 7. Comuni celor trei numere sunt factorii primi 3 și 3. Se pare că GCD (585, 81, 189) = GCD (− 585, 81, − 189) = 9.
Răspuns: GCD (− 585, 81, − 189) = 9.
Dacă observați o eroare în text, vă rugăm să o evidențiați și să apăsați Ctrl+Enter