Modalități interesante de a găsi noduri și noduri. Nod și nok de numere - cel mai mare divizor comun și cel mai mic multiplu comun al mai multor numere

Mulți divizori

Să luăm în considerare următoarea problemă: găsiți divizorul numărului 140. Evident, numărul 140 nu are un divizor, ci mai mulți. În astfel de cazuri se spune că problema are o multime de decizii. Să le găsim pe toate. În primul rând, să ne descompunem număr datîn factori primi:

140 = 2 ∙ 2 ∙ 5 ∙ 7.

Acum putem nota cu ușurință toți divizorii. Să începem cu factorii primi, adică cei care sunt prezenți în expansiunea dată mai sus:

Apoi le notăm pe cele care sunt obținute prin înmulțirea pe perechi a divizorilor primi:

2∙2 = 4, 2∙5 = 10, 2∙7 = 14, 5∙7 = 35.

Apoi - cele care conțin trei divizori primi:

2∙2∙5 = 20, 2∙2∙7 = 28, 2∙5∙7 = 70.

În cele din urmă, să nu uităm unitatea și numărul descompus în sine:

Toți divizorii pe care i-am găsit formează o multime de divizori ai numărului 140, care se scrie folosind acolade:

Setul de divizori ai numărului 140 =

{1, 2, 4, 5, 7, 10, 14, 20, 28, 35, 70, 140}.

Pentru a ușura percepția, am notat divizorii aici ( elemente ale ansamblului) în ordine crescătoare, dar, în general, acest lucru nu este necesar. În plus, introducem o abreviere a notației. În loc de „Setul de divizori ai numărului 140” vom scrie „D(140)”. Prin urmare,

În același mod, puteți găsi mulțimea divizorilor pentru orice alt număr natural. De exemplu, din descompunere

105 = 3 ∙ 5 ∙ 7

primim:

D(105) = (1, 3, 5, 7, 15, 21, 35, 105).

Din mulțimea tuturor divizorilor, ar trebui să distingem mulțimea divizorilor simpli, care pentru numerele 140 și, respectiv, 105 sunt egale:

PD(140) = (2, 5, 7).

PD(105) = (3, 5, 7).

De subliniat mai ales că în descompunerea numărului 140 în factori primi cei doi apar de două ori, în timp ce în mulțimea PD(140) există doar una. Mulțimea lui PD(140) este, în esență, toate răspunsurile la problema: „Găsiți factorul prim al numărului 140”. Este clar că același răspuns nu trebuie repetat de mai multe ori.

Fracții reducătoare. Cel mai mare divizor comun

Luați în considerare fracția

Știm că această fracție poate fi redusă cu un număr care este atât divizor al numărătorului (105) cât și divizor al numitorului (140). Să aruncăm o privire la mulțimile D(105) și D(140) și să scriem elementele lor comune.

D(105) = (1, 3, 5, 7, 15, 21, 35, 105);

D(140) = (1, 2, 4, 5, 7, 10, 14, 20, 28, 35, 70, 140).

Elemente comune ale mulțimilor D(105) și D(140) =

Ultima egalitate poate fi scrisă mai pe scurt și anume:

D(105) ∩ D(140) = (1, 5, 7, 35).

Aici pictograma specială „∩” („sacul cu gaura în jos”) indică cea dintre cele două seturi scrise conform laturi diferite din el, trebuie să selectați numai elemente comune. Intrarea „D(105) ∩ D(140)” se citește „ intersecție seturi de De de la 105 și De de la 140.”

[Rețineți pe parcurs că puteți efectua diverse operații binare cu mulțimi, aproape ca în cazul numerelor. O altă operație binară comună este Uniune, care este indicat de pictograma „∪” („pungă cu orificiul în sus”). Unirea a două mulțimi include toate elementele ambelor mulțimi:

PD(105) = (3, 5, 7);

PD(140) = (2, 5, 7);

PD(105) ∪ PD(140) = (2, 3, 5, 7). ]

Deci, am aflat că fracția

poate fi redus cu oricare dintre numerele aparținând setului

D(105) ∩ D(140) = (1, 5, 7, 35)

și nu poate fi redus cu niciun alt număr natural. Asta e tot moduri posibile abrevieri (cu excepția abrevierilor neinteresante cu unu):

Evident, este cel mai practic să reduceți fracția cu un număr cât mai mare posibil. ÎN în acest caz, acesta este numărul 35, despre care se spune că este cel mai mare divizor comun (GCD) numerele 105 și 140. Aceasta se scrie ca

GCD(105, 140) = 35.

Cu toate acestea, în practică, dacă ni se dau două numere și trebuie să găsim cel mai mare divizor comun al lor, nu ar trebui să construim deloc mulțimi. Este suficient să descompuneți pur și simplu ambele numere în factori primi și să evidențiați pe cei din acești factori care sunt comuni ambelor descompunere, de exemplu:

105 = 3 ∙ 5 ∙ 7 ;

140 = 2 ∙ 2 ∙ 5 ∙ 7 .

Înmulțind numerele subliniate (în oricare dintre expansiuni), obținem:

mcd(105, 140) = 5 ∙ 7 = 35.

Desigur, este posibil să existe mai mult de doi factori subliniați:

168 = 2 ∙ 2 ∙ 2 ∙ 3 ∙ 7;

396 = 2 ∙ 2 ∙ 3 ∙ 3 ∙ 11.

Din aceasta este clar că

mcd(168, 396) = 2 ∙ 2 ∙ 3 = 12.

Situația merită o mențiune specială atunci când nu există deloc factori comuni și nu este nimic de subliniat, de exemplu:

42 = 2 ∙ 3 ∙ 7;

În acest caz,

GCD(42, 55) = 1.

Sunt numite două numere naturale pentru care GCD este egal cu unul prim reciproc. Dacă faci o fracție din astfel de numere, de exemplu,

atunci o astfel de fracție este ireductibil.

În general, regula pentru reducerea fracțiilor poate fi scrisă după cum urmează:

		A/ gcd( A, b)
		b/ gcd( A, b)

Aici se presupune că AȘi b sunt numere naturale, iar întreaga fracție este pozitivă. Dacă acum adăugăm un semn minus la ambele părți ale acestei egalități, obținem regula corespunzătoare pentru fracțiile negative.

Adunarea și scăderea fracțiilor. Cel mai mic multiplu comun

Să presupunem că trebuie să calculați suma a două fracții:

Știm deja cum numitorii sunt factorii primi:

105 = 3 ∙ 5 ∙ 7 ;

140 = 2 ∙ 2 ∙ 5 ∙ 7 .

Din această expansiune rezultă imediat că, pentru a reduce fracțiile la numitor comun, este suficient să înmulțiți numărătorul și numitorul primei fracții cu 2 ∙ 2 (produsul factorilor primi nesubliniați ai celui de-al doilea numitor), iar numărătorul și numitorul celei de-a doua fracții cu 3 („produsul” factori primi nesubliniaţi ai primului numitor). Ca urmare, numitorii ambelor fracții vor deveni egali cu numărul, care poate fi reprezentat după cum urmează:

2 ∙ 2 ∙ 3 ∙ 5 ∙ 7 = 105 ∙ 2 ∙ 2 = 140 ∙ 3 = 420.

Este ușor de observat că ambii numitori originali (atât 105, cât și 140) sunt divizori ai numărului 420, iar numărul 420, la rândul său, este un multiplu al ambilor numitori - și nu doar un multiplu, este cel mai mic multiplu comun (NOC) numerele 105 și 140. Se scrie astfel:

LCM(105, 140) = 420.

Aruncând o privire mai atentă la descompunerea numerelor 105 și 140, vedem că

105 ∙ 140 = GCD(105, 140) ∙ GCD(105, 140).

În mod similar, pentru numere naturale arbitrare bȘi d:

b ∙ d= LOC( b, d) ∙ GCD( b, d).

Acum să completăm însumarea fracțiilor noastre:


3 ∙ 5 ∙ 7		2 ∙ 2 ∙ 5 ∙ 7


2 ∙ 2 ∙ 3 ∙ 5 ∙ 7		2 ∙ 2 ∙ 3 ∙ 5 ∙ 7


2 ∙ 2 ∙ 3 ∙ 5 ∙ 7


2 ∙ 2 ∙ 3 ∙ 5 ∙ 7


2 ∙ 2 ∙ 3 ∙ 5

Notă. Pentru a rezolva unele probleme trebuie să știi care este pătratul unui număr. Pătrat numărul A număr numit A, înmulțit cu el însuși, adică A∙A. (După cum este ușor de văzut, este egal cu aria unui pătrat cu latura A).

Cel mai mare divizor comun și cel mai mic multiplu comun sunt concepte aritmetice cheie care fac lucrul cu fracții fără efort. LCM și sunt cel mai adesea folosite pentru a găsi numitorul comun al mai multor fracții.

Noțiuni de bază

Împărțitorul unui întreg X este un alt întreg Y prin care X este împărțit fără a lăsa rest. De exemplu, divizorul lui 4 este 2, iar 36 este 4, 6, 9. Un multiplu al unui număr întreg X este un număr Y care este divizibil cu X fără rest. De exemplu, 3 este un multiplu al lui 15, iar 6 este un multiplu al lui 12.

Pentru orice pereche de numere putem găsi divizorii și multiplii lor comuni. De exemplu, pentru 6 și 9, multiplu comun este 18, iar divizorul comun este 3. Evident, perechile pot avea mai mulți divizori și multipli, așa că calculele folosesc cel mai mare divizor MCD și cel mai mic multiplu LCM.

Cel mai mic divizor este lipsit de sens, deoarece pentru orice număr este întotdeauna unul. Cel mai mare multiplu este, de asemenea, lipsit de sens, deoarece succesiunea multiplilor merge la infinit.

Găsirea gcd

Există multe metode pentru a găsi cel mai mare divizor comun, dintre care cele mai faimoase sunt:

căutarea secvențială a divizorilor, selectarea celor comuni pentru o pereche și căutarea celui mai mare dintre ei;
descompunerea numerelor în factori indivizibili;
algoritm euclidian;
algoritm binar.

Astăzi, în instituțiile de învățământ cele mai populare metode sunt descompunerea în factori primi și algoritmul euclidian. Acesta din urmă, la rândul său, este utilizat atunci când se rezolvă ecuații diofante: căutarea GCD este necesară pentru a verifica ecuația pentru posibilitatea rezoluției în numere întregi.

Găsirea NOC

Cel mai mic multiplu comun este determinat și de căutarea secvențială sau descompunerea în factori indivizibili. În plus, este ușor să găsiți LCM dacă cel mai mare divizor a fost deja determinat. Pentru numerele X și Y, LCM și GCD sunt legate prin următoarea relație:

LCD(X,Y) = X × Y / GCD(X,Y).

De exemplu, dacă MCM(15,18) = 3, atunci LCM(15,18) = 15 × 18 / 3 = 90. Cel mai evident exemplu de utilizare a MCM este găsirea numitorului comun, care este cel mai mic multiplu comun al fracții date.

Numerele coprime

Dacă o pereche de numere nu are divizori comuni, atunci o astfel de pereche se numește coprim. MCD pentru astfel de perechi este întotdeauna egal cu unu, iar pe baza conexiunii dintre divizori și multipli, mcd pentru perechile coprime este egal cu produsul lor. De exemplu, numerele 25 și 28 sunt relativ prime, deoarece nu au divizori comuni, iar LCM(25, 28) = 700, care corespunde produsului lor. Orice două numere indivizibile vor fi întotdeauna relativ prime.

Divizor comun și calculator multiplu

Folosind calculatorul nostru, puteți calcula GCD și LCM pentru un număr arbitrar de numere din care să alegeți. Sarcinile privind calcularea divizorilor comuni și multiplilor se găsesc în aritmetica de clasele 5 și 6, dar GCD și LCM sunt concepte cheie matematică și sunt utilizate în teoria numerelor, planimetrie și algebra comunicativă.

Exemple din viața reală

Numitorul comun al fracțiilor

Cel mai mic multiplu comun este utilizat la găsirea numitorului comun al fracțiilor multiple. Să presupunem că într-o problemă de aritmetică trebuie să însumați 5 fracții:

1/8 + 1/9 + 1/12 + 1/15 + 1/18.

Pentru a adăuga fracții, expresia trebuie redusă la un numitor comun, care se reduce la problema găsirii LCM. Pentru a face acest lucru, selectați 5 numere în calculator și introduceți valorile numitorilor în celulele corespunzătoare. Programul va calcula LCM (8, 9, 12, 15, 18) = 360. Acum trebuie să calculați factori suplimentari pentru fiecare fracție, care sunt definiți ca raportul dintre LCM și numitorul. Deci, multiplicatorii suplimentari ar arăta astfel:

360/8 = 45
360/9 = 40
360/12 = 30
360/15 = 24
360/18 = 20.

După aceasta, înmulțim toate fracțiile cu factorul suplimentar corespunzător și obținem:

45/360 + 40/360 + 30/360 + 24/360 + 20/360.

Putem aduna cu ușurință astfel de fracții și obținem rezultatul ca 159/360. Reducem fracția cu 3 și vedem răspunsul final - 53/120.

Rezolvarea ecuațiilor diofantine liniare

Ecuațiile diofantine liniare sunt expresii de forma ax + by = d. Dacă raportul d / mcd(a, b) este un număr întreg, atunci ecuația este rezolvabilă în numere întregi. Să verificăm câteva ecuații pentru a vedea dacă au o soluție întreagă. Mai întâi, să verificăm ecuația 150x + 8y = 37. Folosind un calculator, găsim GCD (150.8) = 2. Împărțim 37/2 = 18.5. Numărul nu este un întreg, prin urmare ecuația nu are rădăcini întregi.

Să verificăm ecuația 1320x + 1760y = 10120. Folosiți un calculator pentru a găsi GCD(1320, 1760) = 440. Împărțiți 10120/440 = 23. Ca rezultat, obținem un număr întreg, prin urmare, ecuația diofantică este coeficientă în coeficienti .

Concluzie

GCD și LCM joacă un rol important în teoria numerelor, iar conceptele în sine sunt utilizate pe scară largă în cele mai multe zone diferite matematică. Folosește calculatorul nostru pentru a calcula cei mai mari divizori și cei mai mici multipli ai oricărui număr de numere.

Cel mai mare divizor comun

Definiția 2

Dacă un număr natural a este divizibil cu un număr natural $b$, atunci $b$ se numește divizor al lui $a$, iar $a$ este numit multiplu al lui $b$.

Fie $a$ și $b$ numere naturale. Numărul $c$ se numește divizor comun atât al lui $a$ cât și al $b$.

Mulțimea divizorilor comuni ai numerelor $a$ și $b$ este finită, deoarece niciunul dintre acești divizori nu poate fi mai mare decât $a$. Aceasta înseamnă că printre acești divizori există unul mai mare, care se numește cel mai mare divizor comun al numerelor $a$ și $b$ și este notat cu următoarea notație:

$GCD\(a;b)\ sau \D\(a;b)$

Pentru a găsi cel mai mare divizor comun al două numere aveți nevoie de:

Găsiți produsul numerelor găsite la pasul 2. Numărul rezultat va fi cel mai mare divizor comun dorit.

Exemplul 1

Găsiți mcd-ul numerelor $121$ și $132.$

$242=2\cdot 11\cdot 11$

$132=2\cdot 2\cdot 3\cdot 11$

Alegeți numerele care sunt incluse în extinderea acestor numere

$242=2\cdot 11\cdot 11$

$132=2\cdot 2\cdot 3\cdot 11$

Găsiți produsul numerelor găsite la pasul 2. Numărul rezultat va fi cel mai mare divizor comun dorit.

$GCD=2\cdot 11=22$

Exemplul 2

Găsiți mcd-ul monomiilor $63$ și $81$.

Vom găsi conform algoritmului prezentat. Pentru aceasta:

Să factorăm numerele în factori primi

$63=3\cdot 3\cdot 7$

$81=3\cdot 3\cdot 3\cdot 3$

Selectăm numerele care sunt incluse în extinderea acestor numere

$63=3\cdot 3\cdot 7$

$81=3\cdot 3\cdot 3\cdot 3$

Să găsim produsul numerelor găsite la pasul 2. Numărul rezultat va fi cel mai mare divizor comun dorit.

$GCD=3\cdot 3=9$

Puteți găsi mcd-ul a două numere într-un alt mod, folosind un set de divizori de numere.

Exemplul 3

Găsiți mcd-ul numerelor $48$ și $60$.

Soluţie:

Să găsim mulțimea de divizori ai numărului $48$: $\left$(\rm 1,2,3.4.6,8,12,16,24,48)\right$$

Acum să găsim setul de divizori ai numărului $60$:$\ \left$(\rm 1,2,3,4,5,6,10,12,15,20,30,60)\right$ $

Să găsim intersecția acestor mulțimi: $\left$(\rm 1,2,3,4,6,12)\right$$ - această mulțime va determina mulțimea divizorilor comuni ai numerelor $48$ și $60 $. Cel mai mare element din acest set va fi numărul $12$. Aceasta înseamnă că cel mai mare divizor comun al numerelor $48$ și $60$ este $12$.

Definiţia NPL

Definiția 3

Multipli comuni ai numerelor naturale$a$ și $b$ este un număr natural care este un multiplu atât al lui $a$ cât și al $b$.

Multiplii comuni ai numerelor sunt numere care sunt divizibile cu numerele originale fără rest. De exemplu, pentru numerele $25$ și $50$, multiplii comuni vor fi numerele $50.100.150.200$ etc.

Cel mai mic multiplu comun va fi numit cel mai mic multiplu comun și va fi notat LCM$(a;b)$ sau K$(a;b).$

Pentru a găsi LCM a două numere, trebuie să:

Factorizați numerele în factori primi
Notați factorii care fac parte din primul număr și adăugați la ei factorii care fac parte din al doilea și nu fac parte din primul

Exemplul 4

Găsiți LCM al numerelor $99$ și $77$.

Vom găsi conform algoritmului prezentat. Pentru aceasta

Factorizați numerele în factori primi

$99=3\cdot 3\cdot 11$

Notați factorii incluși în primul

adăugați la ei multiplicatori care fac parte din al doilea și nu din primul

Găsiți produsul numerelor găsite la pasul 2. Numărul rezultat va fi cel mai mic multiplu comun dorit

$NOK=3\cdot 3\cdot 11\cdot 7=693$

Compilarea listelor de divizori ai numerelor este adesea o sarcină foarte intensivă în muncă. Există o modalitate de a găsi GCD numit algoritmul euclidian.

Afirmații pe care se bazează algoritmul euclidian:

Dacă $a$ și $b$ sunt numere naturale și $a\vdots b$, atunci $D(a;b)=b$

Dacă $a$ și $b$ sunt numere naturale astfel încât $b

Folosind $D(a;b)= D(a-b;b)$, putem reduce succesiv numerele luate în considerare până ajungem la o pereche de numere astfel încât unul dintre ele să fie divizibil cu celălalt. Apoi, cel mai mic dintre aceste numere va fi cel mai mare divizor comun dorit pentru numerele $a$ și $b$.

Proprietățile GCD și LCM

Orice multiplu comun al lui $a$ și $b$ este divizibil cu K$(a;b)$
Dacă $a\vdots b$ , atunci К$(a;b)=a$

Dacă K$(a;b)=k$ și $m$ este un număr natural, atunci K$(am;bm)=km$

Dacă $d$ este un divizor comun pentru $a$ și $b$, atunci K($\frac(a)(d);\frac(b)(d)$)=$\ \frac(k)(d); ) $

Dacă $a\vdots c$ și $b\vdots c$ , atunci $\frac(ab)(c)$ este multiplu comun al lui $a$ și $b$

Pentru orice numere naturale $a$ și $b$, egalitatea este valabilă

$D(a;b)\cdot К(a;b)=ab$

Orice divizor comun al numerelor $a$ și $b$ este un divizor al numărului $D(a;b)$

Dar multe numere naturale sunt, de asemenea, divizibile cu alte numere naturale.

De exemplu:

Numărul 12 este divizibil cu 1, cu 2, cu 3, cu 4, cu 6, cu 12;

Numărul 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 cu un întreg (pentru 12 acestea sunt 1, 2, 3, 4, 6 și 12) se numesc divizori de numere. Împărțitor al unui număr natural A- este un număr natural care împarte un număr dat A fără urmă. Un număr natural care are mai mult de doi divizori se numește compozit. Vă rugăm să rețineți că numerele 12 și 36 au factori comuni. Aceste numere sunt: 1, 2, 3, 4, 6, 12. Cel mai mare divizor al acestor numere este 12.

Divizor comun a două numere date AȘi b- acesta este numărul cu care ambele numere date sunt împărțite fără rest AȘi b. Divizor comun al mai multor numere (GCD) este un număr care servește drept divizor pentru fiecare dintre ele.

Pe scurt, cel mai mare divizor comun al numerelor AȘi b scrie asa:

Exemplu: GCD (12; 36) = 12.

Divizorii numerelor din înregistrarea soluției sunt notați cu litera majusculă „D”.

Exemplu:

GCD (7; 9) = 1

Numerele 7 și 9 au un singur divizor comun - numărul 1. Astfel de numere sunt numite prim reciprocchi slami.

Reciproc numere prime - acestea sunt numere naturale care au un singur divizor comun - numărul 1. MCD-ul lor este 1.

Cel mai mare divizor comun (GCD), proprietăți.

Proprietatea de bază: cel mai mare divizor comun mȘi n este divizibil cu orice divizor comun al acestor numere. Exemplu: Pentru numerele 12 și 18, cel mai mare divizor comun este 6; este împărțit la toți divizorii comuni ai acestor numere: 1, 2, 3, 6.
Corolarul 1: mulțime de divizori comuni mȘi n coincide cu setul de divizori GCD( m, n).
Corolarul 2: set de multipli comuni mȘi n coincide cu setul de LCM-uri multiple ( m, n).

Aceasta înseamnă, în special, că pentru a reduce o fracție la o formă ireductibilă, trebuie să împărțiți numărătorul și numitorul acesteia la mcd-ul lor.

Cel mai mare divizor comun al numerelor mȘi n poate fi definit ca cel mai mic element pozitiv al mulțimii tuturor combinațiilor lor liniare:

și, prin urmare, o reprezintă ca o combinație liniară de numere mȘi n:

Acest raport se numește Relația lui Bezout, și coeficienții uȘi v — Coeficienții Bezout. Coeficienții Bezout sunt calculați eficient prin algoritmul euclidian extins. Această afirmație se generalizează la mulțimi de numere naturale - semnificația sa este că subgrupul grupului generat de mulțime este ciclic și generat de un element: GCD ( A 1 , A 2 , … , un n).

Calculați cel mai mare divizor comun (MCD).

Modalități eficiente de a calcula mcd-ul a două numere sunt Algoritmul euclidianȘi binaralgoritm. În plus, valoarea mcd ( m,n) poate fi ușor de calculat dacă se cunoaște extinderea canonică a numerelor mȘi nîn factori primi:

unde sunt numere prime distincte și și sunt numere întregi nenegative (pot fi zero dacă primul corespunzător nu este în expansiune). Apoi GCD ( m,n) și NOC ( m,n) sunt exprimate prin formulele:

Dacă există mai mult de două numere: , gcd-ul lor este găsit folosind următorul algoritm:

- acesta este GCD-ul dorit.

De asemenea, pentru a găsi cel mai mare divizor comun, puteți factoriza fiecare dintre numerele date în factori primi. Apoi notați separat doar acei factori care sunt incluși în toate numerele date. Apoi înmulțim numerele scrise împreună - rezultatul înmulțirii este cel mai mare divizor comun .

Să ne uităm la calculul celui mai mare divizor comun pas cu pas:

1. Descompuneți divizorii numerelor în factori primi:

Este convenabil să scrieți calcule folosind o bară verticală. În stânga liniei scriem mai întâi dividendul, în dreapta - divizorul. Apoi, în coloana din stânga notăm valorile coeficientilor. Să explicăm imediat cu un exemplu. Să factorăm numerele 28 și 64 în factori primi.

2. Subliniem aceiași factori primi în ambele numere:

28 = 2 . 2 . 7

64 = 2 . 2 . 2 . 2 . 2 . 2

3. Găsiți produsul factorilor primi identici și scrieți răspunsul:

mcd (28; 64) = 2. 2 = 4

Răspuns: GCD (28; 64) = 4

Puteți oficializa locația GCD în două moduri: într-o coloană (așa cum s-a făcut mai sus) sau „într-un rând”.

Prima modalitate de a scrie GCD:

Găsiți mcd 48 și 36.

GCD (48; 36) = 2. 2. 3 = 12

A doua modalitate de a scrie GCD:

Acum să notăm soluția la căutarea GCD într-o linie. Găsiți mcd 10 și 15.

D (10) = (1, 2, 5, 10)

D (15) = (1, 3, 5, 15)

D (10, 15) = (1, 5)

Acest articol este dedicat problemei găsirii celui mai mare divizor comun. Mai întâi vom explica ce este și vom da câteva exemple, vom introduce definițiile celui mai mare divizor comun al 2, 3 sau mai multe numere și apoi ne vom concentra pe proprietăți generale acest conceptși le vom dovedi.

Yandex.RTB R-A-339285-1

Care sunt divizorii comuni

Pentru a înțelege care este cel mai mare divizor comun, mai întâi formulăm ce este în general un divizor comun pentru numere întregi.

În articolul despre multipli și divizori, am spus că un număr întreg are întotdeauna mai mulți divizori. Aici ne interesează divizorii unui anumit număr de numere întregi deodată, în special cele comune (identice) pentru toți. Să scriem definiția principală.

Definiția 1

Divizorul comun al mai multor numere întregi este un număr care poate fi un divizor al fiecărui număr din mulțimea specificată.

Exemplul 1

Iată exemple de astfel de divizor: trei va fi un divizor comun pentru numerele - 12 și 9, deoarece egalitățile 9 = 3 · 3 și − 12 = 3 · (− 4) sunt adevărate. Numerele 3 și - 12 au alți factori comuni, cum ar fi 1, - 1 și - 3. Să luăm un alt exemplu. Cele patru numere întregi 3, − 11, − 8 și 19 vor avea doi factori comuni: 1 și - 1.

Cunoscând proprietățile divizibilității, putem spune că orice număr întreg poate fi împărțit la unu și minus unu, ceea ce înseamnă că orice mulțime de numere întregi va avea deja cel puțin doi divizori comuni.

De asemenea, rețineți că dacă avem un divizor comun b pentru mai multe numere, atunci aceleași numere pot fi împărțite la număr opus, adică pe - b. În principiu, putem lua doar divizori pozitivi, atunci toți divizorii comuni vor fi, de asemenea, mai mari decât 0. Această abordare poate fi, de asemenea, utilizată, dar complet ignorată numere negative nu o face.

Care este cel mai mare divizor comun (GCD)

Conform proprietăților divizibilității, dacă b este un divizor al unui număr întreg a care nu este egal cu 0, atunci modulul lui b nu poate fi mai mare decât modulul lui a, prin urmare, orice număr care nu este egal cu 0 are un număr finit de divizori. Aceasta înseamnă că numărul de divizori comuni ai mai multor numere întregi, dintre care cel puțin unul este diferit de zero, va fi, de asemenea, finit, iar din întreaga lor mulțime putem selecta întotdeauna cel mai mult număr mare(am vorbit anterior despre conceptul de cel mai mare și cel mai mic număr întreg, vă sfătuim să repetați acest material).

În discuțiile ulterioare vom presupune că cel puțin unul din setul de numere pentru care trebuie să găsim cel mai mare divizor comun va fi diferit de 0. Dacă toate sunt egale cu 0, atunci divizorul lor poate fi orice număr întreg și, deoarece există infinit de mulți dintre ei, nu îl putem alege pe cel mai mare. Cu alte cuvinte, este imposibil să găsiți cel mai mare divizor comun pentru o mulțime de numere egale cu 0.

Să trecem la formularea definiției principale.

Definiția 2

Cel mai mare divizor comun al mai multor numere este cel mai mare număr întreg care împarte toate acele numere.

În scris, cel mai mare divizor comun este cel mai adesea notat cu abrevierea GCD. Pentru două numere se poate scrie ca mcd (a, b).

Exemplul 2

Care este un exemplu de mcd pentru două numere întregi? De exemplu, pentru 6 și - 15 ar fi 3. Să justificăm asta. În primul rând, notăm toți divizorii lui șase: ± 6, ± 3, ± 1, iar apoi toți divizorii lui cincisprezece: ± 15, ± 5, ± 3 și ± 1. După aceea, le alegem pe cele comune: acestea sunt − 3, − 1, 1 și 3. Dintre acestea, trebuie să alegeți cel mai mare număr. Acesta va fi 3.

Pentru trei sau mai multe numere, determinarea celui mai mare factor comun va fi aproape aceeași.

Definiția 3

Cel mai mare divizor comun a trei sau mai multe numere va fi cel mai mare număr întreg care va împărți toate aceste numere în același timp.

Pentru numerele a 1, a 2, …, a n, este convenabil să notăm divizorul ca MCD (a 1, a 2, …, a n). Valoarea divizorului în sine este scrisă ca GCD (a 1, a 2, ..., a n) = b.

Exemplul 3

Iată exemple de cel mai mare divizor comun al mai multor numere întregi: 12, - 8, 52, 16. Va fi egal cu patru, ceea ce înseamnă că putem scrie că GCD (12, - 8, 52, 16) = 4.

Puteți verifica corectitudinea acestei afirmații notând toți divizorii acestor numere și apoi alegând cel mai mare dintre ei.

În practică, există adesea cazuri când cel mai mare divizor comun este egal cu unul dintre numere. Acest lucru se întâmplă atunci când toate celelalte numere pot fi împărțite la un număr dat (în primul paragraf al articolului am oferit o dovadă a acestei afirmații).

Exemplul 4

Astfel, cel mai mare divizor comun al numerelor 60, 15 și - 45 este 15, deoarece cincisprezece este divizibil nu numai cu 60 și - 45, ci și prin el însuși și nu există un divizor mai mare pentru toate aceste numere.

Un caz special constă din numere coprime. Sunt numere întregi cu cel mai mare divizor comun de 1.

Proprietățile de bază ale GCD și algoritmul euclidian

Cel mai mare divizor comun are unele proprietăți caracteristice. Să le formulăm sub formă de teoreme și să demonstrăm fiecare dintre ele.

Rețineți că aceste proprietăți sunt formulate pentru numere întregi mai mari decât zero și vom lua în considerare doar divizori pozitivi.

Definiția 4

Numerele a și b au cel mai mare divizor comun egal cu mcd pentru b și a, adică mcd (a, b) = mcd (b, a). Inversarea numerelor nu afectează rezultatul final.

Această proprietate decurge din însăși definiția GCD și nu are nevoie de dovezi.

Definiția 5

Dacă numărul a poate fi împărțit la numărul b, atunci mulțimea divizorilor comuni ai acestor două numere va fi similară cu mulțimea divizorilor numărului b, adică mcd (a, b) = b.

Să demonstrăm această afirmație.

Dovada 1

Dacă numerele a și b au divizori comuni, atunci oricare dintre ele poate fi împărțit la ei. În același timp, dacă a este un multiplu al lui b, atunci orice divizor al lui b va fi, de asemenea, un divizor al lui a, deoarece divizibilitatea are o proprietate ca tranzitivitatea. Aceasta înseamnă că orice divizor b va fi comun numerelor a și b. Aceasta demonstrează că dacă putem împărți a la b, atunci mulțimea tuturor divizorilor ambelor numere va coincide cu mulțimea divizorilor unui număr b. Și deoarece cel mai mare divizor al oricărui număr este acest număr în sine, atunci cel mai mare divizor comun al numerelor a și b va fi, de asemenea, egal cu b, adică. GCD (a, b) = b. Dacă a = b, atunci mcd (a, b) = mcd (a, a) = mcd (b, b) = a = b, de exemplu, mcd (132, 132) = 132.

Folosind această proprietate, putem găsi cel mai mare divizor comun a două numere dacă unul dintre ele poate fi împărțit la celălalt. Acest divizor este egal cu unul dintre aceste două numere cu care al doilea număr poate fi împărțit. De exemplu, mcd (8, 24) = 8, deoarece 24 este un multiplu de opt.

Definiția 6 Dovada 2

Să încercăm să dovedim această proprietate. Avem inițial egalitatea a = b q + c, iar orice divizor comun al lui a și b va împărți și c, ceea ce se explică prin proprietatea de divizibilitate corespunzătoare. Prin urmare, orice divizor comun al lui b și c va împărți a. Aceasta înseamnă că mulțimea divizorilor comuni a și b va coincide cu mulțimea divizorilor b și c, inclusiv pe cel mai mare dintre ei, ceea ce înseamnă că egalitatea mcd (a, b) = mcd (b, c) este adevărată.

Definiția 7

Următoarea proprietate se numește algoritmul euclidian. Cu ajutorul acestuia, puteți calcula cel mai mare divizor comun a două numere, precum și puteți demonstra alte proprietăți ale GCD.

Înainte de a formula proprietatea, vă sfătuim să repetați teorema pe care am demonstrat-o în articolul despre împărțirea cu rest. Potrivit acestuia, numărul divizibil a poate fi reprezentat ca b · q + r, cu b aici fiind un divizor, q fiind un număr întreg (numit și coeficient incomplet), iar r fiind un rest care satisface condiția 0 ≤ r ≤ b.

Să presupunem că avem două numere întregi mai mari decât 0, pentru care următoarele egalități vor fi adevărate:

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

Aceste egalități se termină când r k + 1 devine egal cu 0. Acest lucru se va întâmpla cu siguranță, deoarece șirul b > r 1 > r 2 > r 3, ... este o serie de numere întregi descrescătoare, care pot include doar un număr finit dintre ele. Aceasta înseamnă că r k este cel mai mare divizor comun al lui a și b, adică r k = mcd (a, b).

În primul rând, trebuie să demonstrăm că r k este divizorul comun al numerelor a și b și, după aceea, că r k nu este doar un divizor, ci mai degrabă cel mai mare divizor comun a două numere date.

Să ne uităm la lista de egalități de mai sus, de jos în sus. Conform ultimei egalități,
r k − 1 poate fi împărțit la r k . Pe baza acestui fapt, precum și a proprietății dovedite anterioare a celui mai mare divizor comun, se poate argumenta că r k − 2 poate fi împărțit la r k , deoarece
r k − 1 este împărțit la r k și r k este împărțit la r k .

A treia egalitate de jos ne permite să concluzionam că r k − 3 poate fi împărțit la r k , etc. Al doilea de jos este că b este divizibil cu r k , iar primul este că a este divizibil cu r k . Din toate acestea concluzionăm că r k este divizorul comun al lui a și b.

Acum să demonstrăm că r k = GCD (a , b) . Ce trebuie sa fac? Arătați că orice divizor comun al lui a și b va împărți r k. Să-l notăm r 0 .

Să ne uităm la aceeași listă de egalități, dar de sus în jos. Pe baza proprietății anterioare, putem concluziona că r 1 este divizibil cu r 0, ceea ce înseamnă că, conform celei de-a doua egalități, r 2 este împărțit la r 0. Coborâm toate egalitățile și din ultimele concluzionăm că r k este divizibil cu r 0 . Prin urmare, r k = mcd (a , b) .

Având în vedere această proprietate, concluzionăm că mulțimea divizorilor comuni a și b este similară cu mulțimea divizorilor GCD ai acestor numere. Această afirmație, care este o consecință a algoritmului lui Euclidian, ne va permite să calculăm toți divizorii comuni ai două numere date.

Să trecem la alte proprietăți.

Definiția 8

Dacă a și b sunt numere întregi care nu sunt egale cu 0, atunci trebuie să existe alte două numere întregi u 0 și v 0 pentru care egalitatea GCD (a, b) = a · u 0 + b · v 0 va fi valabilă.

Egalitatea dată în declarația de proprietate este o reprezentare liniară a celui mai mare divizor comun al lui a și b. Se numește relația Bezout, iar numerele u 0 și v 0 se numesc coeficienți Bezout.

Dovada 3

Să demonstrăm această proprietate. Să scriem șirul de egalități folosind algoritmul euclidian:

Prima egalitate ne spune că r 1 = a − b · q 1 . Să notăm 1 = s 1 și − q 1 = t 1 și să rescriem această egalitate sub forma r 1 = s 1 · a + t 1 · b. Aici numerele s 1 și t 1 vor fi numere întregi. A doua egalitate ne permite să concluzionam că 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 . Să notăm − s 1 · q 2 = s 2 și 1 − t 1 · q 2 = t 2 și să rescriem egalitatea ca r 2 = s 2 · a + t 2 · b, unde s 2 și t 2 vor fi de asemenea numere întregi. Acest lucru se datorează faptului că suma numerelor întregi, produsul și diferența lor sunt, de asemenea, numere întregi. Exact în același mod obținem din a treia egalitate r 3 = s 3 · a + t 3 · b, din următoarea r 4 = s 4 · a + t 4 · b etc. În final concluzionăm că r k = s k · a + t k · b pentru întreg s k și t k . Deoarece r k = GCD (a, b), notăm s k = u 0 și t k = v 0. Ca rezultat, putem obține o reprezentare liniară a GCD în forma cerută: GCD (a, b) = a · u 0 + b · v 0.

Definiția 9

GCD (m a, m b) = m GCD (a, b) pentru orice valoare naturală a lui m.

Dovada 4

Această proprietate poate fi justificată după cum urmează. Să înmulțim ambele părți ale fiecărei egalități din algoritmul euclidian cu numărul m și să obținem că GCD (m · a, m · b) = m · r k, iar r k este GCD (a, b). Aceasta înseamnă mcd (m a, m b) = m gcd (a, b). Această proprietate a celui mai mare divizor comun este utilizată la găsirea GCD folosind metoda factorizării.

Definiția 10

Dacă numerele a și b au un divizor comun p, atunci mcd (a: p, b: p) = mcd (a, b): p. În cazul în care p = GCD (a, b) obținem GCD (a: GCD (a, b), b: GCD (a, b) = 1, prin urmare, numerele a: GCD (a, b) și b : GCD (a , b) sunt relativ prime.

Deoarece a = p (a: p) și b = p (b: p), atunci, pe baza proprietății anterioare, putem crea egalități de forma mcd (a, b) = mcd (p (a: p), p · (b: p)) = p · GCD (a: p , b: p) , printre care va exista o dovada a acestei proprietati. Folosim această afirmație atunci când dăm fracții comune la formă ireductibilă.

Definiția 11

Cel mai mare divizor comun al a 1, a 2, …, a k va fi numărul d k, care poate fi găsit prin calcularea secvenţială MCD (a 1, a 2) = d 2, MCD (d 2, a 3) = d 3 , GCD (d 3 , a 4) = d 4 , … , GCD (d k - 1 , a k) = d k .

Această proprietate este utilă atunci când găsiți cel mai mare divizor comun a trei sau mai multe numere. Folosind-o, puteți reduce această acțiune la operațiuni cu două numere. Baza sa este un corolar al algoritmului euclidian: dacă mulțimea divizorilor comuni a 1, a 2 și a 3 coincide cu mulțimea d 2 și a 3, atunci va coincide și cu divizorii d 3. Divizorii numerelor a 1, a 2, a 3 și a 4 vor coincide cu divizorii lui d 3, ceea ce înseamnă că vor coincide și cu divizorii lui d 4 etc. În final, obținem că divizorii comuni ai numerelor a 1, a 2, ..., a k vor coincide cu divizorii d k, iar din moment ce cel mai mare divizor al numărului d k va fi acest număr însuși, atunci GCD (a 1, a 2, ..., a k) = d k.

Atât am dori să vă spunem despre proprietățile celui mai mare divizor comun.

Dacă observați o eroare în text, vă rugăm să o evidențiați și să apăsați Ctrl+Enter