Pentru a afla cum să găsiți cel mai mare divizor comun a două sau mai multe numere, trebuie să înțelegeți ce sunt numerele naturale, prime și complexe.
Un număr natural este orice număr care este folosit pentru a număra numerele întregi.
Dacă un număr natural poate fi împărțit doar la el însuși și la unu, atunci se numește prim.
Toate numerele naturale pot fi împărțite la ele însele și unul, dar singurul număr prim par este 2, toate celelalte numere prime pot fi împărțite la doi. Prin urmare, numai numerele impare pot fi prime.
Există o mulțime de numere prime, nu există o listă completă a acestora. Pentru a găsi GCD, este convenabil să folosiți tabele speciale cu astfel de numere.
Majoritatea numerelor naturale pot fi împărțite nu numai la unul, ele însele, ci și la alte numere. Deci, de exemplu, numărul 15 poate fi împărțit la 3 și 5. Toate se numesc divizori ai numărului 15.
Astfel, divizorul oricărui A este numărul cu care poate fi împărțit fără rest. Dacă un număr are mai mult de doi divizori naturali, se numește compus.
Numărul 30 are divizori precum 1, 3, 5, 6, 15, 30.
Puteți vedea că 15 și 30 au aceiași divizori 1, 3, 5, 15. Cel mai mare divizor comun al acestor două numere este 15.
Astfel, divizorul comun al numerelor A și B este numărul cu care le puteți împărți complet. Maximul poate fi considerat numărul total maxim cu care pot fi împărțiți.
Pentru a rezolva probleme, se folosește următoarea inscripție prescurtată:
GCD (A; B).
De exemplu, GCD (15; 30) = 30.
Pentru a scrie toți divizorii unui număr natural, se folosește notația:
D(15) = (1, 3, 5, 15)
mcd (9; 15) = 1
În acest exemplu, numerele naturale au un singur divizor comun. Se numesc coprime, respectiv, unitatea este cel mai mare divizor comun al lor.
Cum să găsești cel mai mare divizor comun al numerelor
Pentru a găsi GCD-ul mai multor numere, aveți nevoie de:
Găsiți separat toți divizorii fiecărui număr natural, adică descompuneți-i în factori (numere prime);
Selectați toți aceiași factori pentru numere date;
Înmulțiți-le împreună.
De exemplu, pentru a calcula cel mai mare divizor comun al numerelor 30 și 56, ați scrie următoarele:
Pentru a nu fi confundat cu , este convenabil să scrieți multiplicatorii folosind coloane verticale. În partea stângă a liniei, trebuie să plasați dividendul, iar în dreapta - divizorul. Sub dividend, ar trebui să indicați coeficientul rezultat.
Deci, în coloana din dreapta vor fi toți factorii necesari pentru soluție.
Divizorii identici (factorii găsiți) pot fi subliniați pentru comoditate. Ele ar trebui rescrise și înmulțite, iar cel mai mare divizor comun trebuie notat.
GCD (30; 56) = 2 * 5 = 10
Este chiar atât de simplu să găsești cel mai mare divizor comun al numerelor. Cu puțină practică, o poți face aproape automat.
Se numește cel mai mare număr natural cu care numerele a și b sunt divizibile fără rest cel mai mare divizor comun aceste numere. Notați GCD(a, b).
Luați în considerare găsirea GCD folosind exemplul a două numere naturale 18 și 60:
18 = 2×3×3
60 = 2×2×3×5
18 = 2×3×3
60 = 2×2×3×5
324 , 111 și 432
Să descompunem numerele în factori primi:
324 = 2×2×3×3×3×3
111 = 3×37
432 = 2×2×2×2×3×3×3
Ștergeți din primul număr, ai cărui factori nu sunt în al doilea și al treilea număr, obținem:
2 x 2 x 2 x 2 x 3 x 3 x 3 = 3
Ca rezultat al GCD( 324 , 111 , 432 )=3
Găsirea GCD cu algoritmul lui Euclid
A doua modalitate de a găsi cel mai mare divizor comun folosind algoritmul lui Euclid. Algoritmul lui Euclid este cel mai eficient mod de a găsi GCD, folosindu-l trebuie să găsiți în mod constant restul diviziunii numerelor și să aplicați formulă recurentă.
Formula recurentă pentru GCD, gcd(a, b)=gcd(b, a mod b), unde a mod b este restul împărțirii a la b.
algoritmul lui Euclid
Exemplu Găsiți cel mai mare divizor comun al numerelor 7920 și 594
Să găsim GCD( 7920 , 594 ) folosind algoritmul Euclid, vom calcula restul diviziunii folosind un calculator.
- 7920 mod 594 = 7920 - 13 × 594 = 198
- 594 mod 198 = 594 - 3 × 198 = 0
Ca rezultat, obținem GCD( 7920 , 594 ) = 198
Cel mai mic multiplu comun
Pentru a găsi un numitor comun atunci când adăugați și scădeți fracții cu numitori diferiți, trebuie să știți și să puteți calcula cel mai mic multiplu comun(NOC).
Un multiplu al numărului „a” este un număr care este el însuși divizibil cu numărul „a” fără rest.
Numerele care sunt multipli ai lui 8 (adică aceste numere vor fi împărțite la 8 fără rest): acestea sunt numerele 16, 24, 32...
Multiplii lui 9: 18, 27, 36, 45…
Există infiniti multipli ai unui număr dat a, spre deosebire de divizorii aceluiași număr. Divizori - un număr finit.
Un multiplu comun a două numere naturale este un număr care este divizibil egal cu ambele numere..
Cel mai mic multiplu comun(LCM) a două sau mai multe numere naturale este cel mai mic număr natural care este el însuși divizibil cu fiecare dintre aceste numere.
Cum să găsiți NOC
LCM poate fi găsit și scris în două moduri.
Prima modalitate de a găsi LCM
Această metodă este de obicei folosită pentru numere mici.
- Scriem multiplii pentru fiecare dintre numere într-o linie până când există un multiplu care este același pentru ambele numere.
- Un multiplu al numărului „a” este notat cu litera majusculă „K”.
Exemplu. Găsiți LCM 6 și 8.
A doua modalitate de a găsi LCM
Această metodă este convenabilă de utilizat pentru a găsi LCM pentru trei sau mai multe numere.
Numărul de factori identici în expansiunile numerelor poate fi diferit.
LCM (24, 60) = 2 2 3 5 2
Răspuns: LCM (24, 60) = 120
De asemenea, puteți oficializa găsirea celui mai mic multiplu comun (LCM) după cum urmează. Să găsim LCM (12, 16, 24) .
24 = 2 2 2 3
După cum putem vedea din expansiunea numerelor, toți factorii lui 12 sunt incluși în expansiunea lui 24 (cel mai mare dintre numere), așa că adăugăm doar un 2 din expansiunea numărului 16 la LCM.
LCM (12, 16, 24) = 2 2 2 3 2 = 48
Răspuns: LCM (12, 16, 24) = 48
Cazuri speciale de găsire a NOC
De exemplu, LCM(60, 15) = 60
Deoarece numerele coprime nu au divizori primi comuni, cel mai mic multiplu comun al lor este egal cu produsul acestor numere.
Pe site-ul nostru, puteți folosi și un calculator special pentru a găsi online cel mai mic multiplu comun pentru a vă verifica calculele.
Dacă un număr natural este divizibil doar cu 1 și cu el însuși, atunci se numește prim.
Orice număr natural este întotdeauna divizibil cu 1 și cu el însuși.
Numărul 2 este cel mai mic număr prim. Acesta este singurul număr prim par, restul numerelor prime sunt impare.
Există multe numere prime, iar primul dintre ele este numărul 2. Cu toate acestea, nu există un ultim număr prim. În secțiunea „Pentru studiu”, puteți descărca un tabel cu numere prime până la 997.
Dar multe numere naturale sunt divizibile egal cu alte numere naturale.
- numărul 12 este divizibil cu 1, cu 2, cu 3, cu 4, cu 6, cu 12;
- 36 este divizibil cu 1, cu 2, cu 3, cu 4, cu 6, cu 12, cu 18, cu 36.
- descompuneți divizorii numerelor în factori primi;
Numerele cu care numărul este divizibil egal (pentru 12 acestea sunt 1, 2, 3, 4, 6 și 12) se numesc divizori ai numărului.
Împărțitorul unui număr natural a este un astfel de număr natural care împarte numărul dat „a” fără rest.
Un număr natural care are mai mult de doi factori se numește număr compus.
Rețineți că numerele 12 și 36 au divizori comuni. Acestea sunt numerele: 1, 2, 3, 4, 6, 12. Cel mai mare divizor al acestor numere este 12.
Divizorul comun a două numere date „a” și „b” este numărul cu care ambele numere date „a” și „b” sunt împărțite fără rest.
Cel mai mare divizor comun(GCD) a două numere date „a” și „b” este cel mai mare număr cu care ambele numere „a” și „b” sunt divizibile fără rest.
Pe scurt, cel mai mare divizor comun al numerelor „a” și „b” se scrie după cum urmează:
Exemplu: mcd (12; 36) = 12 .
Divizorii numerelor din înregistrarea soluției sunt notați cu litera „D”.
Numerele 7 și 9 au un singur divizor comun - numărul 1. Se numesc astfel de numere numere coprime.
Numerele coprime sunt numere naturale care au un singur divizor comun - numărul 1. GCD-ul lor este 1.
Cum să găsiți cel mai mare divizor comun
Pentru a găsi mcd a două sau mai multe numere naturale aveți nevoie de:
Calculele sunt scrise convenabil folosind o bară verticală. În stânga liniei, notați mai întâi dividendul, în dreapta - divizorul. Mai departe în coloana din stânga notăm valorile private.
Să explicăm imediat cu un exemplu. Să factorizăm numerele 28 și 64 în factori primi.
- Subliniați aceiași factori primi în ambele numere.
28 = 2 2 7
64 = 2 2 2 2 2 2
Găsim produsul factorilor primi identici și notăm răspunsul;
GCD (28; 64) = 2 2 = 4
Răspuns: GCD (28; 64) = 4
Puteți aranja locația GCD în două moduri: într-o coloană (cum s-a făcut mai sus) sau „în linie”.
Prima modalitate de a scrie GCD
Găsiți GCD 48 și 36.
GCD (48; 36) = 2 2 3 = 12
A doua modalitate de a scrie GCD
Acum să scriem soluția de căutare GCD într-o linie. Găsiți GCD 10 și 15.
Pe site-ul nostru de informații, puteți găsi, de asemenea, cel mai mare divizor comun online, folosind programul de ajutor pentru a vă verifica calculele.
Găsirea celui mai mic multiplu comun, metode, exemple de găsire a LCM.
Materialul prezentat mai jos este o continuare logică a teoriei din articol la rubrica LCM - Least Common Multiple, definiție, exemple, relație dintre LCM și GCD. Aici vom vorbi despre găsirea celui mai mic multiplu comun (LCM), și acordați o atenție deosebită rezolvării exemplelor. Să arătăm mai întâi cum se calculează LCM a două numere în funcție de MCD-ul acestor numere. Apoi, luați în considerare găsirea celui mai mic multiplu comun prin factorizarea numerelor în factori primi. După aceea, ne vom concentra pe găsirea LCM a trei sau mai multe numere și, de asemenea, acordăm atenție calculului LCM a numerelor negative.
Navigare în pagină.
Calculul cel mai mic multiplu comun (LCM) prin mcd
O modalitate de a găsi cel mai mic multiplu comun se bazează pe relația dintre LCM și GCD. Relația existentă între LCM și GCD vă permite să calculați cel mai mic multiplu comun a două numere întregi pozitive prin cel mai mare divizor comun cunoscut. Formula corespunzătoare are forma LCM(a, b)=a b: GCD(a, b). Luați în considerare exemple de găsire a LCM conform formulei de mai sus.
Aflați cel mai mic multiplu comun al celor două numere 126 și 70.
În acest exemplu a=126, b=70. Să folosim legătura LCM cu GCD, care este exprimată prin formula LCM(a, b)=a b: GCM(a, b) . Adică, mai întâi trebuie să găsim cel mai mare divizor comun al numerelor 70 și 126, după care putem calcula LCM-ul acestor numere conform formulei scrise.
Găsiți mcd(126, 70) folosind algoritmul lui Euclid: 126=70 1+56 , 70=56 1+14 , 56=14 4 , deci mcd(126, 70)=14 .
Acum găsim cel mai mic multiplu comun necesar: LCM(126, 70)=126 70:GCD(126, 70)= 126 70:14=630 .
Ce este LCM(68, 34)?
Deoarece 68 este divizibil egal cu 34 , atunci mcd(68, 34)=34 . Acum calculăm cel mai mic multiplu comun: LCM(68, 34)=68 34:GCD(68, 34)= 68 34:34=68 .
Rețineți că exemplul anterior se potrivește cu următoarea regulă pentru găsirea LCM pentru numerele întregi pozitive a și b: dacă numărul a este divizibil cu b , atunci cel mai mic multiplu comun al acestor numere este a .
Găsirea LCM prin factorizarea numerelor în factori primi
O altă modalitate de a găsi cel mai mic multiplu comun se bazează pe factorizarea numerelor în factori primi. Dacă facem un produs al tuturor factorilor primi ai acestor numere, după care excludem din acest produs toți factorii primi comuni care sunt prezenți în expansiunile acestor numere, atunci produsul rezultat va fi egal cu cel mai mic multiplu comun al acestor numere.
Regula anunțată pentru găsirea LCM rezultă din egalitatea LCM(a, b)=a b: GCD(a, b) . Într-adevăr, produsul numerelor a și b este egal cu produsul tuturor factorilor implicați în expansiunile numerelor a și b. La rândul său, mcd(a, b) este egal cu produsul tuturor factorilor primi care sunt prezenți simultan în expansiunile numerelor a și b (care este descrisă în secțiunea despre găsirea mcd folosind descompunerea numerelor în factori primi). ).
Să luăm un exemplu. Să știm că 75=3 5 5 și 210=2 3 5 7 . Alcătuiți produsul tuturor factorilor acestor expansiuni: 2 3 3 5 5 5 7 . Acum excludem din acest produs toți factorii care sunt prezenți atât în extinderea numărului 75, cât și în extinderea numărului 210 (acești factori sunt 3 și 5), atunci produsul va lua forma 2 3 5 5 7 . Valoarea acestui produs este egală cu cel mai mic multiplu comun al lui 75 și 210 , adică LCM(75, 210)= 2 3 5 5 7=1 050 .
După descompunerea numerelor 441 și 700 în factori primi, găsește cel mai mic multiplu comun al acestor numere.
Să descompunem numerele 441 și 700 în factori primi: 
Se obține 441=3 3 7 7 și 700=2 2 5 5 7 .
Acum să facem un produs al tuturor factorilor implicați în expansiunile acestor numere: 2 2 3 3 5 5 7 7 7 . Să excludem din acest produs toți factorii care sunt prezenți simultan în ambele expansiuni (există un singur astfel de factor - acesta este numărul 7): 2 2 3 3 5 5 7 7 . Deci LCM(441, 700)=2 2 3 3 5 5 7 7=44 100 .
LCM(441, 700)= 44 100 .
Regula pentru găsirea LCM folosind descompunerea numerelor în factori primi poate fi formulată puțin diferit. Dacă adunăm factorii lipsă din extinderea numărului b la factorii din extinderea numărului a, atunci valoarea produsului rezultat va fi egală cu cel mai mic multiplu comun al numerelor a și b.
De exemplu, să luăm aceleași numere 75 și 210, expansiunile lor în factori primi sunt după cum urmează: 75=3 5 5 și 210=2 3 5 7 . La factorii 3, 5 și 5 din descompunerea numărului 75, adăugăm factorii lipsă 2 și 7 din descompunerea numărului 210, obținem produsul 2 3 5 5 7 , a cărui valoare este LCM(75 , 210).
Aflați cel mai mic multiplu comun al lui 84 și 648.
Obținem mai întâi descompunerea numerelor 84 și 648 în factori primi. Ele arată ca 84=2 2 3 7 și 648=2 2 2 3 3 3 3 . La factorii 2 , 2 , 3 și 7 din descompunerea numărului 84 adăugăm factorii lipsă 2 , 3 , 3 și 3 din descompunerea numărului 648 , obținem produsul 2 2 2 3 3 3 3 7 , care este egal cu 4 536 . Astfel, cel mai mic multiplu comun dorit al numerelor 84 și 648 este 4.536.
Găsirea LCM a trei sau mai multe numere
Cel mai mic multiplu comun a trei sau mai multe numere poate fi găsit prin găsirea succesivă a LCM a două numere. Amintiți-vă teorema corespunzătoare, care oferă o modalitate de a găsi LCM a trei sau mai multe numere.
Fie date numere întregi pozitive a 1 , a 2 , …, a k, cel mai mic multiplu comun m k dintre aceste numere se găsește în calculul secvenţial m 2 = LCM (a 1 , a 2) , m 3 = LCM (m 2 , a). 3) , … , m k =LCM(m k−1 , a k) .
Luați în considerare aplicarea acestei teoreme pe exemplul găsirii celui mai mic multiplu comun al patru numere.
Aflați LCM a celor patru numere 140, 9, 54 și 250.
Mai întâi găsim m 2 = LCM (a 1 , a 2) = LCM (140, 9) . Pentru a face acest lucru, folosind algoritmul euclidian, determinăm mcd(140, 9) , avem 140=9 15+5 , 9=5 1+4 , 5=4 1+1 , 4=1 4 , prin urmare, mcd( 140, 9)=1, de unde LCM(140, 9)=140 9: GCD(140, 9)= 140 9:1=1 260 . Adică m2 =1 260 .
Acum găsim m 3 = LCM (m 2 , a 3) = LCM (1 260, 54) . Să o calculăm prin mcd(1 260, 54) , care este determinată și de algoritmul Euclid: 1 260=54 23+18 , 54=18 3 . Atunci mcd(1 260, 54)=18 , de unde LCM(1 260, 54)= 1 260 54:gcd(1 260, 54)= 1 260 54:18=3 780 . Adică m 3 \u003d 3 780.
Rămâne de găsit m 4 = LCM (m 3 , a 4) = LCM (3 780, 250) . Pentru a face acest lucru, găsim GCD(3 780, 250) folosind algoritmul Euclid: 3 780=250 15+30 , 250=30 8+10 , 30=10 3 . Prin urmare, mcd(3 780, 250)=10, deci LCM(3 780, 250)= 3 780 250:gcd(3 780, 250)= 3 780 250:10=94 500 . Adică m 4 \u003d 94 500.
Deci cel mai mic multiplu comun al celor patru numere originale este 94.500.
LCM(140, 9, 54, 250)=94500 .
În multe cazuri, cel mai mic multiplu comun de trei sau mai multe numere este găsit în mod convenabil utilizând descompunerea în factori primi a numerelor date. În acest caz, trebuie respectată următoarea regulă. Cel mai mic multiplu comun al mai multor numere este egal cu produsul, care se compune astfel: factorii lipsă din expansiunea celui de-al doilea număr se adaugă la toți factorii din extinderea primului număr, factorii lipsă din expansiunea primului număr. al treilea număr se adaugă factorilor obținuți și așa mai departe.
Luați în considerare un exemplu de găsire a celui mai mic multiplu comun folosind descompunerea numerelor în factori primi.
Aflați cel mai mic multiplu comun al cinci numere 84 , 6 , 48 , 7 , 143 .
Mai întâi, obținem descompunerea acestor numere în factori primi: 84=2 2 3 7 , 6=2 3 , 48=2 2 2 2 3 , 7 (7 este un număr prim, coincide cu descompunerea lui în factori primi) și 143=11 13 .
Pentru a găsi LCM a acestor numere, la factorii primului număr 84 (sunt 2 , 2 , 3 și 7) trebuie să adăugați factorii lipsă din expansiunea celui de-al doilea număr 6 . Extinderea numărului 6 nu conține factori lipsă, deoarece atât 2, cât și 3 sunt deja prezenți în extinderea primului număr 84 . Pe lângă factorii 2 , 2 , 3 și 7 adăugăm factorii 2 și 2 lipsă din expansiunea celui de-al treilea număr 48 , obținem un set de factori 2 , 2 , 2 , 2 , 3 și 7 . Nu este nevoie să adăugați factori la acest set în pasul următor, deoarece 7 este deja conținut în el. În sfârșit, la factorii 2 , 2 , 2 , 2 , 3 și 7 adăugăm factorii 11 și 13 lipsă din expansiunea numărului 143 . Obținem produsul 2 2 2 2 3 7 11 13 , care este egal cu 48 048 .
Prin urmare, LCM(84, 6, 48, 7, 143)=48048 .
LCM(84, 6, 48, 7, 143)=48048 .
Găsirea celui mai mic multiplu comun al numerelor negative
Uneori există sarcini în care trebuie să găsiți cel mai mic multiplu comun al numerelor, printre care unul, mai multe sau toate numerele sunt negative. În aceste cazuri, toate numerele negative trebuie înlocuite cu numerele lor opuse, după care trebuie găsită LCM-ul numerelor pozitive. Acesta este modul de a găsi LCM al numerelor negative. De exemplu, LCM(54, −34)=LCM(54, 34) și LCM(−622, −46, −54, −888)= LCM(622, 46, 54, 888) .
Putem face acest lucru deoarece mulțimea multiplilor lui a este aceeași cu mulțimea multiplilor lui -a (a și -a sunt numere opuse). Într-adevăr, fie b un multiplu al lui a , atunci b este divizibil cu a , iar conceptul de divizibilitate afirmă existența unui astfel de număr întreg q care b=a q . Dar va fi adevărată și egalitatea b=(−a)·(−q), ceea ce, în virtutea aceluiași concept de divizibilitate, înseamnă că b este divizibil cu −a , adică b este un multiplu al −a . Afirmația inversă este de asemenea adevărată: dacă b este un multiplu al lui −a , atunci b este și un multiplu al lui a .
Aflați cel mai mic multiplu comun al numerelor negative −145 și −45.
Să înlocuim numerele negative −145 și −45 cu numerele lor opuse 145 și 45 . Avem LCM(−145, −45)=LCM(145, 45) . După ce am determinat mcd(145, 45)=5 (de exemplu, folosind algoritmul Euclid), calculăm LCM(145, 45)=145 45:gcd(145, 45)= 145 45:5=1 305 . Astfel, cel mai mic multiplu comun al numerelor întregi negative −145 și −45 este 1.305 .
www.cleverstudents.ru
Continuăm să studiem diviziunea. În această lecție, ne vom uita la concepte precum GCDși NOC.
GCD este cel mai mare divizor comun.
NOC este cel mai mic multiplu comun.
Subiectul este destul de plictisitor, dar este necesar să-l înțelegeți. Fără a înțelege acest subiect, nu vei putea lucra eficient cu fracțiile, care reprezintă un adevărat obstacol în matematică.
Cel mai mare divizor comun
Definiție. Cel mai mare divizor comun al numerelor Ași b Ași bîmpărțit fără rest.
Pentru a înțelege bine această definiție, înlocuim variabilele Ași b oricare două numere, de exemplu, în loc de o variabilă Aînlocuiți numărul 12 și în loc de variabilă b numărul 9. Acum să încercăm să citim această definiție:
Cel mai mare divizor comun al numerelor 12 și 9 este cel mai mare număr cu care 12 și 9 împărțit fără rest.
Din definiție reiese clar că vorbim despre un divizor comun al numerelor 12 și 9, iar acest divizor este cel mai mare dintre toți divizorii existenți. Acest cel mai mare divizor comun (mcd) trebuie găsit.
Pentru a găsi cel mai mare divizor comun al două numere, se folosesc trei metode. Prima metodă necesită destul de mult timp, dar vă permite să înțelegeți bine esența subiectului și să simțiți întregul său sens.
A doua și a treia metodă sunt destul de simple și fac posibilă găsirea rapidă a GCD. Vom lua în considerare toate cele trei metode. Și ce să aplici în practică - tu alegi.
Prima modalitate este de a găsi toți divizorii posibili ai două numere și de a alege cel mai mare dintre ei. Să luăm în considerare această metodă în exemplul următor: găsiți cel mai mare divizor comun al numerelor 12 și 9.
În primul rând, găsim toți divizorii posibili ai numărului 12. Pentru a face acest lucru, împărțim 12 în toți divizorii din intervalul de la 1 la 12. Dacă divizorul ne permite să împărțim 12 fără rest, atunci îl vom evidenția cu albastru și faceți o explicație adecvată între paranteze.
12: 1 = 12
(12 împărțit la 1 fără rest, deci 1 este un divizor al lui 12)
12: 2 = 6
(12 împărțit la 2 fără rest, deci 2 este un divizor al lui 12)
12: 3 = 4
(12 împărțit la 3 fără rest, deci 3 este un divizor al lui 12)
12: 4 = 3
(12 împărțit la 4 fără rest, deci 4 este un divizor al lui 12)
12:5 = 2 (2 rămase)
(12 nu este împărțit la 5 fără rest, deci 5 nu este un divizor al lui 12)
12: 6 = 2
(12 împărțit la 6 fără rest, deci 6 este un divizor al lui 12)
12: 7 = 1 (5 rămase)
(12 nu este împărțit la 7 fără rest, deci 7 nu este un divizor al lui 12)
12: 8 = 1 (4 au rămas)
(12 nu este împărțit la 8 fără rest, deci 8 nu este un divizor al lui 12)
12:9 = 1 (3 rămase)
(12 nu este împărțit la 9 fără rest, deci 9 nu este un divizor al lui 12)
12: 10 = 1 (2 au rămas)
(12 nu se împarte la 10 fără rest, deci 10 nu este un divizor al lui 12)
12:11 = 1 (1 rămas)
(12 nu este împărțit la 11 fără rest, deci 11 nu este un divizor al lui 12)
12: 12 = 1
(12 împărțit la 12 fără rest, deci 12 este un divizor al lui 12)
Acum să găsim divizorii numărului 9. Pentru a face acest lucru, verificați toți divizorii de la 1 la 9
9: 1 = 9
(9 împărțit la 1 fără rest, deci 1 este un divizor al lui 9)
9: 2 = 4 (1 rămas)
(9 nu este împărțit la 2 fără rest, deci 2 nu este un divizor al lui 9)
9: 3 = 3
(9 împărțit la 3 fără rest, deci 3 este un divizor al lui 9)
9: 4 = 2 (1 rămas)
(9 nu este împărțit la 4 fără rest, deci 4 nu este un divizor al lui 9)
9:5 = 1 (4 rămase)
(9 nu este împărțit la 5 fără rest, deci 5 nu este un divizor al lui 9)
9: 6 = 1 (3 au rămas)
(9 nu a împărțit la 6 fără rest, deci 6 nu este un divizor al lui 9)
9:7 = 1 (2 rămase)
(9 nu este împărțit la 7 fără rest, deci 7 nu este un divizor al lui 9)
9:8 = 1 (1 rămas)
(9 nu este împărțit la 8 fără rest, deci 8 nu este un divizor al lui 9)
9: 9 = 1
(9 împărțit la 9 fără rest, deci 9 este un divizor al lui 9)
Acum scrieți divizorii ambelor numere. Numerele evidențiate cu albastru sunt divizorii. Să le scriem:
După ce ați scris divizorii, puteți determina imediat care dintre ele este cel mai mare și cel mai comun.
Prin definiție, cel mai mare divizor comun al lui 12 și 9 este numărul cu care 12 și 9 sunt divizibili egal. Cel mai mare și comun divizor al numerelor 12 și 9 este numărul 3
Atât numărul 12, cât și numărul 9 sunt divizibil cu 3 fără rest:
Deci mcd (12 și 9) = 3
A doua modalitate de a găsi GCD
Acum luați în considerare a doua modalitate de a găsi cel mai mare divizor comun. Esența acestei metode este de a descompune ambele numere în factori primi și de a le înmulți pe cei comuni.
Exemplul 1. Găsiți GCD al numerelor 24 și 18
Mai întâi, să factorăm ambele numere în factori primi:
Acum le înmulțim factorii comuni. Pentru a nu se confunda, pot fi subliniați factorii comuni.
Ne uităm la descompunerea numărului 24. Primul său factor este 2. Căutăm același factor în descompunerea numărului 18 și vedem că există și el. Subliniem ambele două:
Din nou ne uităm la descompunerea numărului 24. Al doilea factor al său este, de asemenea, 2. Căutăm același factor în descompunerea numărului 18 și vedem că nu este acolo pentru a doua oară. Atunci nu scoatem în evidență nimic.
Următoarele două din extinderea numărului 24 lipsesc și din extinderea numărului 18.
Trecem la ultimul factor în descompunerea numărului 24. Acesta este factorul 3. Căutăm același factor în descompunerea numărului 18 și vedem că există și el. Subliniem ambele trei:
Deci, factorii comuni ai numerelor 24 și 18 sunt factorii 2 și 3. Pentru a obține GCD, acești factori trebuie înmulțiți:
Deci mcd (24 și 18) = 6
A treia modalitate de a găsi GCD
Acum luați în considerare a treia modalitate de a găsi cel mai mare divizor comun. Esența acestei metode constă în faptul că numerele care trebuie căutate pentru cel mai mare divizor comun sunt descompuse în factori primi. Apoi, din descompunerea primului număr, factorii care nu sunt incluși în descompunerea celui de-al doilea număr sunt șterși. Numerele rămase în prima expansiune sunt înmulțite și obțin GCD.
De exemplu, să găsim GCD pentru numerele 28 și 16 în acest fel. În primul rând, descompunem aceste numere în factori primi:
Avem două extinderi: și
Acum, din extinderea primului număr, ștergem factorii care nu sunt incluși în extinderea celui de-al doilea număr. Extinderea celui de-al doilea număr nu include șapte. O vom șterge din prima extensie:
Acum înmulțim factorii rămași și obținem GCD:
Numărul 4 este cel mai mare divizor comun al numerelor 28 și 16. Ambele numere sunt divizibile cu 4 fără rest:
Exemplul 2 Găsiți MCD al numerelor 100 și 40
Scoaterea în factor a numărului 100
Scoaterea în factor a numărului 40
Avem două extinderi:
Acum, din extinderea primului număr, ștergem factorii care nu sunt incluși în extinderea celui de-al doilea număr. Extinderea celui de-al doilea număr nu include unul cinci (există doar unul cinci). O ștergem din prima descompunere
Înmulțiți numerele rămase:
Am primit răspunsul 20. Deci numărul 20 este cel mai mare divizor comun al numerelor 100 și 40. Aceste două numere sunt divizibile cu 20 fără rest:
GCD (100 și 40) = 20.
Exemplul 3 Aflați mcd-ul numerelor 72 și 128
Scoaterea în factor a numărului 72
Scoaterea în factor a numărului 128
2×2×2×2×2×2×2
Acum, din extinderea primului număr, ștergem factorii care nu sunt incluși în extinderea celui de-al doilea număr. Extinderea celui de-al doilea număr nu include două triplete (nu există deloc). Le ștergem din prima descompunere:
Am primit răspunsul 8. Deci numărul 8 este cel mai mare divizor comun al numerelor 72 și 128. Aceste două numere sunt divizibile cu 8 fără rest:
GCD (72 și 128) = 8
Găsirea GCD pentru numere multiple
Cel mai mare divizor comun poate fi găsit pentru mai multe numere și nu doar pentru două. Pentru aceasta, numerele care trebuie găsite pentru cel mai mare divizor comun sunt descompuse în factori primi, apoi se găsește produsul factorilor primi comuni ai acestor numere.
De exemplu, să găsim GCD pentru numerele 18, 24 și 36
Factorizarea numărului 18
Factorizarea numărului 24
Factorizarea numărului 36
Avem trei extinderi:
Acum selectăm și subliniem factorii comuni din aceste numere. Factorii comuni trebuie incluși în toate cele trei numere:
Vedem că factorii comuni pentru numerele 18, 24 și 36 sunt factorii 2 și 3. Înmulțind acești factori, obținem MCD pe care îl căutăm:
Am primit răspunsul 6. Deci numărul 6 este cel mai mare divizor comun al numerelor 18, 24 și 36. Aceste trei numere sunt divizibile cu 6 fără rest:
GCD (18, 24 și 36) = 6
Exemplul 2 Găsiți mcd pentru numerele 12, 24, 36 și 42
Să factorizăm fiecare număr. Apoi găsim produsul factorilor comuni ai acestor numere.
Factorizarea numărului 12
Factorizarea numărului 42
Avem patru extinderi:
Acum selectăm și subliniem factorii comuni din aceste numere. Factorii comuni trebuie incluși în toate cele patru numere:
Vedem că factorii comuni pentru numerele 12, 24, 36 și 42 sunt factorii 2 și 3. Înmulțind acești factori, obținem MCD pe care îl căutăm:
Am primit răspunsul 6. Deci numărul 6 este cel mai mare divizor comun al numerelor 12, 24, 36 și 42. Aceste numere sunt divizibile cu 6 fără rest:
mcd(12, 24, 36 și 42) = 6
Din lecția anterioară, știm că dacă un număr este împărțit la altul fără rest, se numește multiplu al acestui număr.
Se dovedește că un multiplu poate fi comun mai multor numere. Și acum ne va interesa un multiplu de două numere, în timp ce ar trebui să fie cât mai mic posibil.
Definiție. Cel mai mic multiplu comun (LCM) al numerelor Ași b- Ași b A si numarul b.
Definiția conține două variabile Ași b. Să înlocuim oricare două numere pentru aceste variabile. De exemplu, în loc de o variabilă Aînlocuiți numărul 9 și în locul variabilei b să înlocuim numărul 12. Acum să încercăm să citim definiția:
Cel mai mic multiplu comun (LCM) al numerelor 9 și 12 - este cel mai mic număr care este un multiplu al 9 și 12 . Cu alte cuvinte, este un număr atât de mic care este divizibil fără rest cu numărul 9 iar pe număr 12 .
Este clar din definiție că LCM este cel mai mic număr care este divizibil fără rest cu 9 și 12. Acest LCM este necesar să fie găsit.
Există două moduri de a găsi cel mai mic multiplu comun (LCM). Prima modalitate este că puteți nota primii multipli ai două numere și apoi alegeți dintre acești multipli un astfel de număr care va fi comun ambelor numere și mic. Să aplicăm această metodă.
În primul rând, să găsim primii multipli pentru numărul 9. Pentru a găsi multiplii pentru 9, trebuie să înmulțiți pe rând acesti nouă cu numerele de la 1 la 9. Răspunsurile pe care le obțineți vor fi multipli ai numărului 9. Deci , să începem. Multiplii vor fi evidențiați cu roșu:
Acum găsim multipli pentru numărul 12. Pentru a face acest lucru, înmulțim pe rând 12 cu toate numerele de la 1 la 12.
Luați în considerare două moduri de a găsi cel mai mare divizor comun.
Găsirea prin factorizare
Prima modalitate este de a găsi cel mai mare divizor comun prin factorizarea numerelor date în factori primi.
Pentru a găsi GCD-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).
Descompunem numerele 84 și 90 în factori primi:
Deci, am subliniat toți factorii primi comuni, rămâne să-i înmulțim între ei: 1 2 3 = 6.
Deci mcd(84, 90) = 6.
Exemplul 2 Să găsim GCD (15, 28).
Descompunem 15 și 28 în factori primi:
Numerele 15 și 28 sunt între prime deoarece cel mai mare divizor comun al lor este unul.
mcd (15, 28) = 1.
algoritmul lui Euclid
A doua metodă (denumită altfel metoda Euclid) este de a găsi GCD prin împărțire succesivă.
În primul rând, ne vom uita la această metodă ca fiind aplicată doar la două numere date, apoi ne vom da seama 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 care este mai mic va fi cel mai mare divizor comun al acestora.
Exemplul 1 Luați două numere 27 și 9. Deoarece 27 este divizibil cu 9 și 9 este divizibil cu 9, atunci 9 este un divizor comun al numerelor 27 și 9. Acest divizor este și cel mai mare, deoarece 9 nu poate fi divizibil cu niciun 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, se utilizează următoarea procedură:
- Dintre cele două numere date, numărul mai mare se împarte la cel mai mic.
- Apoi, numărul mai mic este împărțit la restul rezultat din împărțirea numărului mai mare la cel mai mic.
- În plus, 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 și așa mai departe.
- 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, ceea ce înseamnă mcd(140, 96) = 4.
Împărțirea secvențială poate fi scrisă și într-o coloană:
Pentru a găsi cel mai mare divizor comun a trei sau mai multe numere date, utilizați următoarea procedură:
- Mai întâi, găsiți cel mai mare divizor comun al oricăror două numere din mai multe seturi de date.
- Apoi găsim GCD-ul divizorului găsit și un al treilea număr dat.
- Apoi găsim GCD-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. Deci mcd(140, 96, 48) = 4.
Tine minte!
Dacă un număr natural este divizibil doar cu 1 și cu el însuși, atunci se numește prim.
Orice număr natural este întotdeauna divizibil cu 1 și cu el însuși.
Numărul 2 este cel mai mic număr prim. Acesta este singurul număr prim par, restul numerelor prime sunt impare.
Există multe numere prime, iar primul dintre ele este numărul 2. Cu toate acestea, nu există un ultim număr prim. În secțiunea „Pentru studiu”, puteți descărca un tabel cu numere prime până la 997.
Dar multe numere naturale sunt divizibile egal cu alte numere naturale.
De exemplu:
- numărul 12 este divizibil cu 1, cu 2, cu 3, cu 4, cu 6, cu 12;
- 36 este divizibil cu 1, cu 2, cu 3, cu 4, cu 6, cu 12, cu 18, cu 36.
Numerele cu care numărul este divizibil egal (pentru 12 acestea sunt 1, 2, 3, 4, 6 și 12) se numesc divizori ai numărului.
Tine minte!
Împărțitorul unui număr natural a este un astfel de număr natural care împarte numărul dat „a” fără rest.
Un număr natural care are mai mult de doi factori se numește număr compus.
Rețineți că numerele 12 și 36 au divizori comuni. Acestea sunt numerele: 1, 2, 3, 4, 6, 12. Cel mai mare divizor al acestor numere este 12.
Divizorul comun a două numere date „a” și „b” este numărul cu care ambele numere date „a” și „b” sunt împărțite fără rest.
Tine minte!
Cel mai mare divizor comun(GCD) a două numere date „a” și „b” - acesta este cel mai mare număr prin care ambele numere „a” și „b” sunt împărțite fără rest.
Pe scurt, cel mai mare divizor comun al numerelor „a” și „b” se scrie după cum urmează:
gcd (a; b) .
Exemplu: mcd (12; 36) = 12 .
Divizorii numerelor din înregistrarea soluției sunt notați cu litera „D”.
D(7) = (1, 7)
D(9) = (1, 9)
mcd (7; 9) = 1
Numerele 7 și 9 au un singur divizor comun - numărul 1. Se numesc astfel de numere numere coprime.
Tine minte!
Numerele coprime sunt numere naturale care au un singur divizor comun - numărul 1. GCD-ul lor este 1.
Cum să găsiți cel mai mare divizor comun
Pentru a găsi mcd a două sau mai multe numere naturale aveți nevoie de:
- descompuneți divizorii numerelor în factori primi;
Calculele sunt scrise convenabil folosind o bară verticală. În stânga liniei, notați mai întâi dividendul, în dreapta - divizorul. Mai departe în coloana din stânga notăm valorile private.
Să explicăm imediat cu un exemplu. Să factorizăm numerele 28 și 64 în factori primi.
- Subliniați aceiași factori primi în ambele numere.
28 = 2 2 764 = 2 2 2 2 2 2
- Găsim produsul factorilor primi identici și notăm răspunsul;
GCD (28; 64) = 2 2 = 4Răspuns: GCD (28; 64) = 4
Puteți aranja locația GCD în două moduri: într-o coloană (cum s-a făcut mai sus) sau „în linie”.
Acum și în cele ce urmează, vom presupune că cel puțin unul dintre aceste numere este diferit de zero. Dacă toate numerele date sunt egale cu zero, atunci divizorul lor comun este orice număr întreg și, deoarece există infinit de numere întregi, nu putem vorbi despre cel mai mare dintre ele. Prin urmare, nu se poate vorbi de cel mai mare divizor comun al numerelor, fiecare dintre acestea fiind egal cu zero.
Acum putem da găsirea celui mai mare divizor comun doua numere.
Definiție.
Cel mai mare divizor comun a două numere întregi este cel mai mare număr întreg care împarte cele două numere întregi date.
Abrevierea GCD este adesea folosită pentru a scurta cel mai mare divizor comun - Greatest Common Divisor. De asemenea, cel mai mare divizor comun al două numere a și b este adesea notat ca mcd(a, b) .
Să aducem Cel mai mare divizor comun (mcd). două numere întregi. Cel mai mare divizor comun al lui 6 și −15 este 3 . Să argumentăm acest lucru. Să notăm toți divizorii numărului șase: ±6, ±3, ±1, iar divizorii numărului −15 sunt numerele ±15, ±5, ±3 și ±1. Acum puteți găsi toți divizorii comuni ai numerelor 6 și −15, acestea sunt numerele −3, −1, 1 și 3. Din moment ce −3<−1<1<3 , то 3 – это наибольший общий делитель чисел 6 и −15 . То есть, НОД(6, −15)=3 .
Definiția celui mai mare divizor comun a trei sau mai multe numere întregi este similară cu definiția mcd a două numere.
Definiție.
Cel mai mare divizor comun trei sau mai multe numere întregi este cel mai mare număr întreg care împarte simultan toate numerele date.
Cel mai mare divizor comun al n numere întregi a 1 , a 2 , …, a n îl vom nota ca mcd(a 1 , a 2 , …, a n) . Dacă se găsește valoarea b al celui mai mare divizor comun al acestor numere, atunci putem scrie GCD(a 1 , a 2 , …, a n)=b.
De exemplu, având în vedere mcd a patru numere întregi −8 , 52 , 16 și −12 , este egal cu 4 , adică mcd(−8, 52, 16, −12)=4 . Acest lucru poate fi verificat notând toți divizorii numerelor date, selectând divizorii comuni dintre aceștia și determinând cel mai mare divizor comun.
Rețineți că cel mai mare divizor comun al numerelor întregi poate fi egal cu unul dintre aceste numere. Această afirmație este adevărată dacă toate numerele date sunt divizibile cu unul dintre ele (dovada este dată în paragraful următor al acestui articol). De exemplu, mcd(15, 60, −45)=15 . Acest lucru este adevărat deoarece 15 împarte 15 , 60 și −45 și nu există un divizor comun al 15 , 60 și −45 care să fie mai mare decât 15 .
De un interes deosebit sunt așa-numitele numere prime relativ, - astfel de numere întregi, cel mai mare divizor comun al cărora este egal cu unu.
Proprietățile celui mai mare divizor comun, algoritmul lui Euclid
Cel mai mare divizor comun are o serie de rezultate caracteristice, cu alte cuvinte, o serie de proprietăți. Vom enumera acum principalele proprietățile celui mai mare divizor comun (mcd), le vom formula sub formă de teoreme și imediat vom da dovezi.
Vom formula toate proprietățile celui mai mare divizor comun pentru numere întregi pozitive, în timp ce vom lua în considerare doar divizorii pozitivi ai acestor numere.
Cel mai mare divizor comun al lui a și b este egal cu cel mai mare divizor comun al lui b și a , adică mcd(a, b)=mcd(a, b) .
Această proprietate GCD rezultă direct din definiția celui mai mare divizor comun.
Dacă a este divizibil cu b , atunci mulțimea divizorilor comuni ai lui a și b este aceeași cu mulțimea divizorilor lui b , în special mcd(a, b)=b .
Dovada.
Orice divizor comun al numerelor a și b este un divizor al fiecăruia dintre aceste numere, inclusiv al numărului b. Pe de altă parte, deoarece a este un multiplu al lui b, atunci orice divizor al numărului b este și un divizor al numărului a datorită faptului că divizibilitatea are proprietatea tranzitivității, prin urmare, orice divizor al numărului b este a divizor comun al numerelor a și b. Aceasta dovedește că dacă a este divizibil cu b, atunci mulțimea divizorilor numerelor a și b coincide cu mulțimea divizorilor unui număr b. Și deoarece cel mai mare divizor al numărului b este numărul b însuși, atunci și cel mai mare divizor comun al numerelor a și b este egal cu b , adică mcd(a, b)=b .
În special, dacă numerele a și b sunt egale, atunci mcd(a, b)=gcd(a, a)=gcd(b, b)=a=b. De exemplu, mcd(132, 132)=132 .
Proprietatea dovedită a celui mai mare divizor ne permite să găsim mcd a două numere atunci când unul dintre ele este divizibil cu celălalt. În acest caz, GCD este egal cu unul dintre aceste numere, cu care un alt număr este divizibil. De exemplu, mcd(8, 24)=8 deoarece 24 este un multiplu al lui opt.
Dacă a=b q+c , unde a , b , c și q sunt numere întregi, atunci mulțimea divizorilor comuni ai numerelor a și b coincide cu mulțimea divizorilor comuni ai numerelor b și c , în special, mcd( a, b)=gcd (b, c) .
Să justificăm această proprietate a GCD.
Deoarece egalitatea a=b·q+c este valabilă, atunci orice divizor comun al numerelor a și b împarte și c (acest lucru rezultă din proprietățile divizibilității). Din același motiv, fiecare divizor comun al lui b și c împarte a . Prin urmare, mulțimea divizorilor comuni ai numerelor a și b este aceeași cu mulțimea divizorilor comuni ai numerelor b și c. În special, și cel mai mare dintre acești divizori comuni trebuie să se potrivească, adică următoarea egalitate trebuie să fie validă mcd(a, b)=gcd(b, c) .
Acum formulăm și demonstrăm o teoremă, care este algoritmul lui Euclid. Algoritmul lui Euclid vă permite să găsiți GCD-ul a două numere (vezi găsirea GCD folosind algoritmul Euclid). Mai mult, algoritmul lui Euclid ne va permite să demonstrăm următoarele proprietăți ale celui mai mare divizor comun.
Înainte de a da enunțul teoremei, recomandăm reîmprospătarea memoriei teoremei din secțiunea de teorie, care afirmă că dividendul a poate fi reprezentat ca b q + r, unde b este un divizor, q este un număr întreg numit coeficient parțial, iar r este un întreg care satisface condiția, numit rest.
Deci, fie pentru două numere întregi pozitive diferite de zero a și b, o serie de egalități este adevărată 
care se termină când r k+1 =0 (ceea ce este inevitabil, deoarece b>r 1 >r 2 >r 3 , … este o serie de numere întregi descrescătoare, iar această serie nu poate conține mai mult de un număr finit de numere pozitive), atunci r k – este cel mai mare divizor comun al lui a și b , adică r k =gcd(a, b) .
Dovada.
Să demonstrăm mai întâi că r k este un divizor comun al numerelor a și b , după care vom arăta că r k nu este doar un divizor, ci cel mai mare divizor comun al numerelor a și b .
Ne vom deplasa de-a lungul egalităților scrise de jos în sus. Din ultima egalitate, putem spune că r k−1 este divizibil cu r k . Având în vedere acest fapt, precum și proprietatea anterioară GCD, penultima egalitate r k−2 =r k−1 q k +r k ne permite să afirmăm că r k−2 este divizibil cu r k , deoarece r k−1 este divizibil cu r k și r k este divizibil de r k . Prin analogie, din a treia egalitate de jos concluzionăm că r k−3 este divizibil cu r k . etc. Din a doua egalitate obținem că b este divizibil cu r k , iar din prima egalitate obținem că a este divizibil cu r k . Prin urmare, r k este un divizor comun al lui a și b.
Rămâne de demonstrat că r k =gcd(a, b) . Căci, este suficient să arătăm că orice divizor comun al numerelor a și b (notăm cu r 0 ) împarte r k .
Ne vom deplasa de-a lungul egalităților inițiale de sus în jos. În virtutea proprietății anterioare, din prima egalitate rezultă că r 1 este divizibil cu r 0 . Apoi din a doua egalitate obținem că r 2 este divizibil cu r 0 . etc. Din ultima egalitate obținem că r k este divizibil cu r 0 . Astfel, r k =gcd(a, b) .
Din proprietatea considerată a celui mai mare divizor comun rezultă că mulțimea divizorilor comuni ai numerelor a și b coincide cu mulțimea divizorilor celui mai mare divizor comun al acestor numere. Acest corolar din algoritmul lui Euclid ne permite să găsim toți divizorii comuni ai două numere ca divizori ai mcd-ului acestor numere.
Fie a și b numere întregi care nu sunt egale simultan cu zero, atunci există astfel de numere întregi u 0 și v 0 , atunci egalitatea gcd(a, b)=a u 0 +b v 0 este valabilă. Ultima egalitate este o reprezentare liniară a celui mai mare divizor comun al numerelor a și b, această egalitate se numește raportul Bezout, iar numerele u 0 și v 0 sunt coeficienții Bezout.
Dovada.
Conform algoritmului lui Euclid, putem scrie următoarele egalități
Din prima egalitate avem r 1 =a−b q 1 , iar, notând 1=s 1 și −q 1 =t 1 , această egalitate ia forma r 1 =s 1 a+t 1 b , iar numerele s 1 și t 1 sunt numere întregi. Apoi din a doua egalitate obținem r 2 =b−r 1 q 2 = b−(s 1 a+t 1 b) q 2 =−s 1 q 2 a+(1−t 1 q 2) b. Notând −s 1 q 2 =s 2 și 1−t 1 q 2 =t 2 , ultima egalitate poate fi scrisă ca r 2 =s 2 a+t 2 b , iar s 2 și t 2 sunt numere întregi (deoarece suma , diferența și produsul numerelor întregi este un număr întreg). În mod similar, din a treia egalitate obținem r 3 =s 3 ·a+t 3 ·b, din a patra r 4 =s 4 ·a+t 4 ·b și așa mai departe. În cele din urmă, r k =s k ·a+t k ·b , unde s k și t k sunt numere întregi. Deoarece r k =gcd(a, b) , și notând s k =u 0 și t k =v 0 , obținem o reprezentare liniară a mcd de forma cerută: gcd(a, b)=a u 0 +b v 0 .
Dacă m este orice număr natural, atunci gcd(m a, m b)=m gcd(a, b).
Motivul pentru această proprietate a celui mai mare divizor comun este următorul. Dacă înmulțim cu m ambele părți ale fiecăreia dintre egalitățile algoritmului Euclid, obținem că gcd(m a, m b)=m r k , iar r k este mcd(a, b) . Prin urmare, gcd(m a, m b)=m gcd(a, b).
Această proprietate a celui mai mare divizor comun stă la baza metodei de găsire a GCD folosind factorizarea primilor.
Fie p orice divizor comun al numerelor a și b , atunci gcd(a:p, b:p)=gcd(a, b):p, în special, dacă p=gcd(a, b) avem gcd(a:gcd(a, b), b:gcd(a, b))=1, adică numerele a:gcd(a, b) și b:gcd(a, b) sunt între prime.
Deoarece a=p (a:p) și b=p (b:p) și datorită proprietății anterioare, putem scrie un lanț de egalități de forma mcd(a, b)=gcd(p (a:p), p (b:p))= p·gcd(a:p, b:p) , de unde rezultă egalitatea de demonstrat.
Cea mai mare proprietate comună divizor tocmai dovedită stă la baza .
Acum să exprimăm proprietatea GCD, care reduce problema găsirii celui mai mare divizor comun a trei sau mai multe numere la găsirea succesivă a GCD a două numere.
Cel mai mare divizor comun al numerelor a 1 , a 2 , ..., a k este egal cu numărul d k , care se găsește în calculul succesiv al MCD(a 1 , a 2)=d 2 , MCD(d 2 , a 3)=d3, GCD(d3, a4)=d4, …, GCD(dk-1, ak)=dk.
Dovada se bazează pe un corolar din algoritmul lui Euclid. Divizorii comuni ai numerelor a 1 și a 2 sunt aceiași cu divizorii lui d 2 . Atunci divizorii comuni ai numerelor a 1 , a 2 și a 3 coincid cu divizorii comuni ai numerelor d 2 și a 3 , prin urmare, ei coincid cu divizorii lui d 3 . Divizorii comuni ai numerelor a 1 , a 2 , a 3 și a 4 sunt aceiași cu divizorii comuni ai lui d 3 și a 4 , deci la fel ca și divizorii lui d 4 . etc. În cele din urmă, divizorii comuni ai numerelor a 1 , a 2 , …, a k coincid cu divizorii lui d k . Și întrucât cel mai mare divizor al numărului d k este numărul d k însuși, atunci GCD(a 1 , a 2 , …, a k)=d k.
Aceasta încheie trecerea în revistă a principalelor proprietăți ale celui mai mare divizor comun.
Bibliografie.
- Vilenkin N.Ya. etc.Matematica. Clasa a VI-a: manual pentru instituțiile de învățământ.
- Vinogradov I.M. Fundamentele teoriei numerelor.
- Mihailovici Sh.Kh. Teoria numerelor.
- Kulikov L.Ya. şi altele.Culegere de probleme de algebră şi teoria numerelor: Manual pentru studenţii de fiz.-mat. specialităţile institutelor pedagogice.
