Mnogi djelitelji
Razmotrite sljedeći problem: pronađite djelitelj broja 140. Očigledno je da broj 140 nema jedan djelitelj, već nekoliko. U takvim slučajevima se kaže da zadatak ima gomila rješenja. Nađimo ih sve. Prije svega, razlažemo ovaj broj na proste faktore:
140 = 2 ∙ 2 ∙ 5 ∙ 7.
Sada možemo lako ispisati sve djelitelje. Počnimo s jednostavnim djeliteljima, odnosno onima koji su prisutni u gornjoj ekspanziji:
Zatim ispisujemo one koji se dobiju parnim množenjem prostih djelitelja:
2∙2 = 4, 2∙5 = 10, 2∙7 = 14, 5∙7 = 35.
Zatim - one koje sadrže tri jednostavna djelitelja:
2∙2∙5 = 20, 2∙2∙7 = 28, 2∙5∙7 = 70.
Na kraju, ne zaboravimo jedinicu i sam broj koji se može razložiti:
Svi djelitelji koje smo pronašli formiraju se gomila djelitelji broja 140, koji se piše pomoću vitičastih zagrada:
Skup djelitelja broja 140 =
{1, 2, 4, 5, 7, 10, 14, 20, 28, 35, 70, 140}.
Radi lakše percepcije, ovdje smo napisali djelitelje ( set elemenata) u rastućem redoslijedu, ali općenito govoreći, to nije neophodno. Uz to, uvodimo i skraćenicu. Umjesto "Skup djelitelja broja 140" pisaćemo "D (140)". dakle,
Slično, može se pronaći skup djelitelja za bilo koji drugi prirodni broj. Na primjer, iz ekspanzije
105 = 3 ∙ 5 ∙ 7
dobijamo:
D(105) = (1, 3, 5, 7, 15, 21, 35, 105).
Od skupa svih djelitelja treba razlikovati skup prostih djelitelja, koji su za brojeve 140 i 105 jednaki, redom:
PD(140) = (2, 5, 7).
PD(105) = (3, 5, 7).
Treba naglasiti da je kod dekompozicije broja 140 na proste faktore dva prisutna dva puta, dok je u skupu PD(140) samo jedan. Skup PD(140) je, u suštini, svi odgovori na problem: "Pronađi prost faktor broja 140". Jasno je da isti odgovor ne treba ponoviti više od jednom.
Smanjenje frakcije. Najveći zajednički djelitelj
Uzmite u obzir razlomak
Znamo da se ovaj razlomak može smanjiti za broj koji je i djelilac brojnika (105) i djelitelj nazivnika (140). Pogledajmo skupove D(105) i D(140) i zapišimo njihove zajedničke elemente.
D(105) = (1, 3, 5, 7, 15, 21, 35, 105);
D(140) = (1, 2, 4, 5, 7, 10, 14, 20, 28, 35, 70, 140).
Zajednički elementi skupova D(105) i D(140) =
Posljednja jednakost se može napisati kraće, i to:
D(105) ∩ D(140) = (1, 5, 7, 35).
Ovdje posebna ikona "∩" ("torba sa rupom prema dolje") samo ukazuje na to da od dva seta ispisana na suprotnim stranama nje treba odabrati samo zajedničke elemente. Unos "D (105) ∩ D (140)" glasi " raskrsnica setovi Te od 105 i Te od 140.
[Imajte na umu da možete izvoditi razne binarne operacije sa skupovima, skoro kao sa brojevima. Još jedna uobičajena binarna operacija je Union, što je označeno ikonom "∪" ("torba sa rupom gore"). Unija dva skupa uključuje sve elemente oba skupa:
PD(105) = (3, 5, 7);
PD(140) = (2, 5, 7);
PD(105) ∪ PD(140) = (2, 3, 5, 7). ]
Dakle, saznali smo da je razlomak
može se svesti na bilo koji od brojeva koji pripadaju skupu
D(105) ∩ D(140) = (1, 5, 7, 35)
i ne može se smanjiti ni za jedan drugi prirodni broj. Evo svih mogućih načina za smanjenje (osim nezanimljivog smanjenja za jedan):
Očigledno je da je najpraktičnije razlomak smanjiti za broj, ako je moguće i veći. U ovom slučaju, to je broj 35, za koji se kaže da jeste najveći zajednički djelitelj (GCD) brojevi 105 i 140. Ovo se piše kao
gcd(105, 140) = 35.
Međutim, u praksi, ako su nam data dva broja i trebamo pronaći njihov najveći zajednički djelitelj, ne moramo uopće graditi nikakve skupove. Dovoljno je jednostavno faktorizirati oba broja u proste faktore i podvući one od ovih faktora koji su zajednički za obje faktorizacije, na primjer:
105 = 3 ∙ 5 ∙ 7 ;
140 = 2 ∙ 2 ∙ 5 ∙ 7 .
Množenjem podvučenih brojeva (u bilo kojem od proširenja) dobijamo:
gcd(105, 140) = 5 ∙ 7 = 35.
Naravno, moguće je da postoji više od dva podvučena faktora:
168 = 2 ∙ 2 ∙ 2 ∙ 3 ∙ 7;
396 = 2 ∙ 2 ∙ 3 ∙ 3 ∙ 11.
Odavde je to jasno
gcd(168, 396) = 2 ∙ 2 ∙ 3 = 12.
Posebno treba istaći situaciju kada uopšte nema zajedničkih faktora i nema šta da se istakne, na primer:
42 = 2 ∙ 3 ∙ 7;
U ovom slučaju,
gcd(42, 55) = 1.
Pozivaju se dva prirodna broja za koja je gcd jednak jedan coprime. Ako od takvih brojeva napravite razlomak, npr.
onda je takav razlomak nesvodivo.
Općenito govoreći, pravilo za smanjenje razlomaka može se zapisati na sljedeći način:
|
a/ gcd( a, b) |
|||
|
b/ gcd( a, b) |
Ovdje se pretpostavlja da a I b su prirodni brojevi, a svi razlomci su pozitivni. Ako sada dodijelimo znak minus objema stranama ove jednakosti, dobićemo odgovarajuće pravilo za negativne razlomke.
Sabiranje i oduzimanje razlomaka. Najmanji zajednički višekratnik
Pretpostavimo da želite izračunati zbir dva razlomka:
Već znamo kako se imenioci rastavljaju na proste faktore:
105 = 3 ∙ 5 ∙ 7 ;
140 = 2 ∙ 2 ∙ 5 ∙ 7 .
Iz ovog proširenja odmah slijedi da je, da bi se razlomci doveli u zajednički nazivnik, dovoljno pomnožiti brojilac i imenilac prvog razlomka sa 2 ∙ 2 (proizvod nenaglašenih prostih faktora drugog nazivnika), i brojilac i imenilac drugog razlomka za 3 („proizvod“ nepodvučeni prosti faktori prvog imenioca). Kao rezultat toga, nazivnici oba razlomka će postati jednaki broju koji se može predstaviti na sljedeći način:
2 ∙ 2 ∙ 3 ∙ 5 ∙ 7 = 105 ∙ 2 ∙ 2 = 140 ∙ 3 = 420.
Lako je vidjeti da su oba izvorna nazivnika (i 105 i 140) djelitelji broja 420, a broj 420 je, zauzvrat, višekratnik oba nazivnika - a ne samo višekratnik, on je najmanji zajednički višekratnik (NOC) brojevi 105 i 140. Ovo se piše ovako:
LCM(105, 140) = 420.
Ako pažljivije pogledamo proširenje brojeva 105 i 140, vidimo to
105 ∙ 140 = LCM(105, 140) ∙ GCD(105, 140).
Slično, za proizvoljne prirodne brojeve b I d:
b ∙ d= LCM( b, d) ∙ GCD( b, d).
Sada završimo zbrajanje naših razlomaka:
|
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 |
|
Bilješka. Da biste riješili neke probleme, morate znati koliki je kvadrat broja. Broj kvadrata a nazvao broj a pomnoženo samim sobom, tj a∙a. (Kao što vidite, jednaka je površini kvadrata sa stranicom a). |
Jedan od zadataka koji stvara problem savremenim školarcima, koji su navikli da koriste kalkulatore ugrađene u gadžete na mestu i van mesta, je pronalaženje najvećeg zajedničkog djelitelja (GCD) dva ili više brojeva.
Nemoguće je riješiti bilo koji matematički problem ako se ne zna šta se zapravo postavlja. Da biste to učinili, morate znati šta znači ovaj ili onaj izraz. koristi u matematici.
Trebam znati:
- Ako se određeni broj može koristiti za brojanje raznih objekata, na primjer, devet stupova, šesnaest kuća, onda je to prirodno. Najmanji od njih će biti jedan.
- Kada je prirodan broj djeljiv drugim prirodnim brojem, kaže se da je manji broj djelitelj većeg.
- Ako su dva ili više različitih brojeva djeljivi određenim brojem bez ostatka, onda kažu da će im potonji biti zajednički djelitelj (OD).
- Najveći od OD naziva se najveći zajednički djelitelj (GCD).
- U tom slučaju, kada broj ima samo dva prirodna djelitelja (sam i jedan), naziva se prostim. Najmanji među njima je dvojka, osim toga, to je jedini paran broj u njihovoj seriji.
- Ako dva broja imaju maksimalni zajednički djelitelj jedan, tada će biti međusobno prosti.
- Broj sa više od dva djelitelja naziva se složeni broj.
- Proces kada se pronađu svi prosti faktori, koji će, kada se pomnože jedan s drugim, dati početnu vrijednost u proizvodu u matematici, naziva se dekompozicija na proste faktore. Štaviše, isti faktori u ekspanziji mogu se pojaviti više puta.
U matematici su prihvaćene sljedeće oznake:
- Delitelji D (45) = (1; 3; 5; 9; 45).
- OD (8;18) = (1;2).
- GCD (8;18) = 2.
Različiti načini za pronalaženje GCD
Pitanje na koje je najlakše odgovoriti kako pronaći NOD kada je manji broj djelilac većeg. To će biti najveći zajednički djelitelj u ovom slučaju.
Na primjer, GCD (15;45) = 15, GCD (48;24) = 24.
Ali takvi slučajevi u matematici su vrlo rijetki, stoga se za pronalaženje GCD koriste složenije tehnike, iako se još uvijek preporučuje da se ova opcija provjeri prije početka rada.
Metoda dekompozicije na osnovne faktore
Ako trebate pronaći GCD dva ili više različitih brojeva, dovoljno je svaki od njih razložiti na jednostavne činioce, a zatim izvršiti proces množenja onih od njih koji se nalaze u svakom od brojeva.
Primjer 1
Razmislite kako pronaći GCD 36 i 90:
- 36 = 1*2*2*3*3;
- 90 = 1*2*3*3*5;
GCD (36;90) = 1*2*3*3 = 18.
Sada da vidimo kako da pronađemo isto u slučaju tri broja, uzmimo na primjer 54; 162; 42.
Već znamo kako razložiti 36, pozabavimo se ostatkom:
- 162 = 1*2*3*3*3*3;
- 42 = 1*2*3*7;
Dakle, GCD (36;162;42) = 1*2*3 = 6.
Treba napomenuti da je apsolutno opciono upisati jedinicu u proširenje.
Razmotrite način kako je lako rastaviti na faktore, za to ćemo na lijevoj strani napisati broj koji nam je potreban, a na desnoj strani pisati jednostavne djelitelje.
Kolone se mogu odvojiti ili znakom podjele ili jednostavnom vertikalnom crtom.
- 36 / 2 nastavićemo proces podjele;
- 18 / 2 dalje;
- 9/3 i ponovo;
- 3/3 je sada sasvim elementarno;
- 1 - rezultat je spreman.
Željenih 36 = 2 * 2 * 3 * 3.
Euklidski način
Ova opcija je poznata čovječanstvu još od vremena drevne grčke civilizacije, mnogo je jednostavnija, a pripisuje se velikom matematičaru Euklidu, iako su se ranije koristili vrlo slični algoritmi. Ova metoda je korištenje sljedećeg algoritma, veći broj sa ostatkom dijelimo manjim. Zatim naš djelitelj podijelimo s ostatkom i nastavimo tako djelovati u krugu dok se dijeljenje ne završi. Posljednja vrijednost će se pokazati kao željeni najveći zajednički djelitelj.
Dajemo primjer korištenja ovog algoritma:
Pokušajmo saznati koji GCD za 816 i 252:
- 816 / 252 = 3, a ostatak je 60. Sada dijelimo 252 sa 60;
- 252 / 60 = 4 ostatak će ovoga puta biti 12. Nastavimo naš kružni proces, podijelimo šezdeset sa dvanaest;
- 60 / 12 = 5. Pošto ovaj put nismo dobili nikakav ostatak, rezultat je spreman, dvanaest će biti vrijednost koju tražimo.
Dakle, na kraju našeg procesa imamo NOD (816;252) = 12.
Radnje ako je potrebno odrediti GCD ako je navedeno više od dvije vrijednosti
Već smo shvatili šta učiniti u slučaju kada postoje dva različita broja, sada ćemo naučiti kako postupiti ako ih ima. 3 ili više.
Uz svu prividnu složenost, ovaj zadatak nam neće stvarati probleme. Sada biramo bilo koja dva broja i određujemo vrijednost koju tražimo za njih. Sljedeći korak je pronalaženje GCD za dobiveni rezultat i treću od datih vrijednosti. Onda opet postupamo po principu koji nam je već poznat za četvrtu petu i tako dalje.
Zaključak
Dakle, uz naizgled veliku složenost zadatka koji je na početku postavljen pred nas, u stvari, sve je jednostavno, glavna stvar je da se proces dijeljenja može izvesti bez greške i pridržavajte se bilo kojeg od dva gore opisana algoritma.
Iako su obje metode sasvim prihvatljive, u srednjoj školi prva metoda se mnogo češće koristi.. To je zbog činjenice da će pri proučavanju sljedeće obrazovne teme - definicije najvećeg zajedničkog višekratnika (LCM) biti potrebna dekompozicija na osnovne faktore. Ali ipak, vrijedi još jednom napomenuti da se upotreba Euklidovog algoritma ni na koji način ne može smatrati pogrešnom.
Video
Uz pomoć videa možete naučiti kako pronaći najveći zajednički djelitelj.
Niste dobili odgovor na svoje pitanje? Predložite temu autorima.
Pronalaženje najvećeg zajedničkog djelitelja tri ili više brojeva može se svesti na uzastopno pronalaženje gcd dva broja. To smo spomenuli kada smo proučavali svojstva GCD. Tamo smo formulirali i dokazali teoremu: najveći zajednički djelitelj nekoliko brojeva a 1 , a 2 , …, a k jednak je broju d k, koji se nalazi u sekvencijalnom proračunu GCD(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.
Pogledajmo kako izgleda proces pronalaženja GCD nekoliko brojeva razmatrajući rješenje primjera.
Primjer.
Pronađite najveći zajednički djelitelj četiri broja 78 , 294 , 570 I 36 .
Rješenje.
U ovom primjeru a 1 =78, a2=294, a 3 \u003d 570, a4=36.
Prvo, koristeći Euklid algoritam, određujemo najveći zajednički djelitelj d2 prva dva broja 78 I 294 . Prilikom dijeljenja dobijamo jednakosti 294=78 3+60; 78=60 1+18;60=18 3+6 I 18=6 3. dakle, d 2 \u003d GCD (78, 294) \u003d 6.
Sada izračunajmo d 3 = GCD (d 2, a 3) \u003d GCD (6, 570). Koristimo ponovo Euklidov algoritam: 570=6 95, dakle, d 3 = GCD (6, 570) \u003d 6.
Ostaje izračunati d 4 \u003d GCD (d 3, a 4) \u003d GCD (6, 36). Jer 36 podijeljena 6 , To d 4 \u003d GCD (6, 36) \u003d 6.
Dakle, najveći zajednički djelitelj četiri data broja je d4=6, to je, gcd(78, 294, 570, 36)=6.
odgovor:
gcd(78, 294, 570, 36)=6.
Dekomponovanje brojeva na proste faktore takođe vam omogućava da izračunate GCD tri ili više brojeva. U ovom slučaju, najveći zajednički djelitelj se nalazi kao proizvod svih zajedničkih prostih faktora datih brojeva.
Primjer.
Izračunajte GCD brojeva iz prethodnog primjera koristeći njihove osnovne faktorizacije.
Rješenje.
Hajde da dekomponujemo brojeve 78 , 294 , 570 I 36 u osnovne faktore, dobijamo 78=2 3 13,294=2 3 7 7, 570=2 3 5 19, 36=2 2 3 3. Zajednički prosti faktori za sva data četiri broja su brojevi 2 I 3 . dakle, GCD(78, 294, 570, 36)=2 3=6.
odgovor:
gcd(78, 294, 570, 36)=6.
Vrh stranice
Pronalaženje gcd negativnih brojeva
Ako su jedan, nekoliko ili svi brojevi čiji se najveći djelitelj nalazi negativni brojevi, tada je njihov gcd jednak najvećem zajedničkom djelitelju modula ovih brojeva. To je zato što su suprotni brojevi a I -a imaju iste djelitelje, o čemu smo raspravljali kada smo proučavali svojstva djeljivosti.
Primjer.
Pronađite gcd negativnih cijelih brojeva −231 I −140 .
Rješenje.
Apsolutna vrijednost broja −231 jednaki 231 , i modul broja −140 jednaki 140 , And gcd(−231, −140)=gcd(231, 140). Euklidov algoritam nam daje sljedeće jednakosti: 231=140 1+91; 140=91 1+49; 91=49 1+42; 49=42 1+7 I 42=7 6. dakle, gcd(231, 140)=7. Zatim željeni najveći zajednički djelitelj negativnih brojeva −231 I −140 jednaki 7 .
odgovor:
GCD(−231,−140)=7.
Primjer.
Odrediti gcd tri broja −585 , 81 I −189 .
Rješenje.
Prilikom pronalaženja najvećeg zajedničkog djelitelja, negativni brojevi se mogu zamijeniti njihovim apsolutnim vrijednostima, tj. gcd(−585, 81, −189)=gcd(585, 81, 189). Proširenja brojeva 585 , 81 I 189 u proste faktore su, respektivno, oblika 585=3 3 5 13, 81=3 3 3 3 I 189=3 3 3 7. Uobičajeni prosti faktori ova tri broja su 3 I 3 . Onda GCD(585, 81, 189)=3 3=9, dakle, gcd(−585, 81, −189)=9.
odgovor:
gcd(−585, 81, −189)=9.
35. Korijeni polinoma. Bezoutova teorema. (33 i više)
36. Višestruki korijeni, kriterij višestrukosti korijena.
Sada iu daljem tekstu, pretpostavićemo da je barem jedan od ovih brojeva različit od nule. Ako su svi dati brojevi jednaki nuli, onda je njihov zajednički djelitelj bilo koji cijeli broj, a kako cijelih brojeva ima beskonačno mnogo, ne možemo govoriti o najvećem od njih. Stoga se ne može govoriti o najvećem zajedničkom djelitelju brojeva, od kojih je svaki jednak nuli.
Sada možemo dati pronalaženje najvećeg zajedničkog djelitelja dva broja.
Definicija.
Najveći zajednički djelitelj od dva cijela broja je najveći cijeli broj koji dijeli dva data cijela broja.
Skraćenica GCD se često koristi za skraćenje najvećeg zajedničkog djelitelja - Greatest Common Divisor. Također, najveći zajednički djelitelj dva broja a i b često se označava kao gcd(a, b) .
Hajde da donesemo Primjer najvećeg zajedničkog djelitelja (gcd). dva cela broja. Najveći zajednički djelitelj 6 i −15 je 3. Hajde da to potkrijepimo. Zapišimo sve djelitelje broja šest: ±6, ±3, ±1, a djelitelji broja −15 su brojevi ±15, ±5, ±3 i ±1. Sada možete pronaći sve zajedničke djelitelje brojeva 6 i −15, to su brojevi −3, −1, 1 i 3. Pošto −3<−1<1<3 , то 3 – это наибольший общий делитель чисел 6 и −15 . То есть, НОД(6, −15)=3 .
Definicija najvećeg zajedničkog djelitelja tri ili više cijelih brojeva slična je definiciji gcd dva broja.
Definicija.
Najveći zajednički djelitelj tri ili više cijelih brojeva je najveći cijeli broj koji istovremeno dijeli sve date brojeve.
Najveći zajednički djelitelj n cijelih brojeva a 1 , a 2 , …, a n označit ćemo kao gcd(a 1 , a 2 , …, a n) . Ako se pronađe vrijednost b najvećeg zajedničkog djelitelja ovih brojeva, onda možemo pisati GCD(a 1 , a 2 , …, a n)=b.
Kao primjer, s obzirom na gcd od četiri cijela broja −8, 52, 16 i −12, on je jednak 4, odnosno gcd(−8, 52, 16, −12)=4. To se može provjeriti zapisivanjem svih djelitelja datih brojeva, odabirom zajedničkih djelitelja od njih i određivanjem najvećeg zajedničkog djelitelja.
Imajte na umu da najveći zajednički djelitelj cijelih brojeva može biti jednak jednom od ovih brojeva. Ova tvrdnja je tačna ako su svi dati brojevi djeljivi sa jednim od njih (dokaz je dat u sljedećem pasusu ovog člana). Na primjer, gcd(15, 60, −45)=15 . To je tačno jer 15 dijeli 15, 60 i −45, a ne postoji zajednički djelitelj 15, 60 i −45 koji je veći od 15.
Od posebnog interesa su takozvani relativno prosti brojevi, - takvi cijeli brojevi, čiji je najveći zajednički djelitelj jednak jedan.
Najveća svojstva zajedničkog djelitelja, Euklidov algoritam
Najveći zajednički djelitelj ima niz karakterističnih rezultata, drugim riječima, brojna svojstva. Sada ćemo navesti glavne svojstva najvećeg zajedničkog djelitelja (gcd), formulisaćemo ih u obliku teorema i odmah dati dokaze.
Formulisaćemo sva svojstva najvećeg zajedničkog djelitelja za pozitivne cijele brojeve, dok ćemo uzeti u obzir samo pozitivne djelitelje ovih brojeva.
Najveći zajednički djelitelj a i b jednak je najvećem zajedničkom djelitelju b i a, to jest, gcd(a, b)=gcd(a, b) .
Ovo svojstvo GCD direktno slijedi iz definicije najvećeg zajedničkog djelitelja.
Ako je a djeljivo sa b, tada je skup zajedničkih djelitelja a i b isti kao skup djelitelja b, posebno gcd(a, b)=b.
Dokaz.
Svaki zajednički djelitelj brojeva a i b je djelitelj svakog od ovih brojeva, uključujući i broj b. S druge strane, pošto je a višekratnik broja b, onda je svaki djelitelj broja b također i djelitelj broja a zbog činjenice da djeljivost ima svojstvo tranzitivnosti, stoga je svaki djelitelj broja b a zajednički djelitelj brojeva a i b. Ovo dokazuje da ako je a djeljivo sa b, tada se skup djelitelja brojeva a i b poklapa sa skupom djelitelja jednog broja b. A pošto je najveći djelitelj broja b sam broj b, tada je i najveći zajednički djelitelj brojeva a i b jednak b, odnosno gcd(a, b)=b.
Konkretno, ako su brojevi a i b jednaki, onda gcd(a, b)=gcd(a, a)=gcd(b, b)=a=b. Na primjer, gcd(132, 132)=132.
Dokazano svojstvo najvećeg djelitelja nam omogućava da pronađemo gcd dva broja kada je jedan od njih djeljiv s drugim. U ovom slučaju, GCD je jednak jednom od ovih brojeva, s kojim je drugi broj djeljiv. Na primjer, gcd(8, 24)=8 budući da je 24 višestruko od osam.
Ako je a=b q+c, gdje su a, b, c i q cijeli brojevi, tada se skup zajedničkih djelitelja brojeva a i b poklapa sa skupom zajedničkih djelitelja brojeva b i c, posebno gcd( a, b)=gcd (b, c) .
Hajde da opravdamo ovo svojstvo GCD.
Kako vrijedi jednakost a=b·q+c, onda svaki zajednički djelitelj brojeva a i b također dijeli c (ovo slijedi iz svojstava djeljivosti). Iz istog razloga, svaki zajednički djelitelj b i c dijeli a . Dakle, skup zajedničkih djelitelja brojeva a i b je isti kao skup zajedničkih djelitelja brojeva b i c. Konkretno, najveći od ovih zajedničkih djelitelja također se mora podudarati, odnosno, sljedeća jednakost mora biti važeća gcd(a, b)=gcd(b, c) .
Sada formuliramo i dokazujemo teoremu, koja je Euklidov algoritam. Euklidov algoritam vam omogućava da pronađete GCD dva broja (pogledajte pronalaženje GCD pomoću Euklidovog algoritma). Štaviše, Euklidov algoritam će nam omogućiti da dokažemo sljedeća svojstva najvećeg zajedničkog djelitelja.
Prije davanja iskaza teoreme, preporučujemo osvježavanje pamćenja teoreme iz odjeljka teorije, koji kaže da se dividenda a može predstaviti kao b q + r, gdje je b djelitelj, q je neki cijeli broj koji se naziva parcijalni količnik, i r je cijeli broj koji zadovoljava uslov, naziva se ostatak.
Dakle, neka je za dva različita od nule pozitivna cijela broja a i b tačan niz jednakosti 
završava kada je r k+1 =0 (što je neizbježno, budući da je b>r 1 >r 2 >r 3 , … niz opadajućih cijelih brojeva, a ovaj niz ne može sadržavati više od konačnog broja pozitivnih brojeva), tada r k – je najveći zajednički djelitelj a i b , odnosno r k =gcd(a, b) .
Dokaz.
Dokažimo prvo da je r k zajednički djelitelj brojeva a i b , nakon čega ćemo pokazati da r k nije samo djelitelj, već najveći zajednički djelitelj brojeva a i b .
Kretaćemo se duž zapisanih jednakosti odozdo prema gore. Iz posljednje jednakosti možemo reći da je r k−1 djeljivo sa r k . Imajući u vidu ovu činjenicu, kao i prethodno svojstvo GCD, pretposljednja jednakost r k−2 =r k−1 q k +r k nam omogućava da tvrdimo da je r k−2 deljivo sa r k , jer je r k−1 deljivo sa r k i r k je deljivo od r k . Analogno, iz treće jednakosti odozdo zaključujemo da je r k−3 djeljivo sa r k . I tako dalje. Iz druge jednakosti dobijamo da je b djeljivo sa r k , a iz prve jednakosti dobijamo da je a djeljivo sa r k . Prema tome, r k je zajednički djelitelj a i b.
Ostaje dokazati da je r k =gcd(a, b) . Jer, dovoljno je pokazati da svaki zajednički djelitelj brojeva a i b (označavamo ga sa r 0 ) dijeli r k .
Kretaćemo se duž početnih jednakosti od vrha do dna. Na osnovu prethodnog svojstva, iz prve jednakosti slijedi da je r 1 djeljiv sa r 0 . Tada iz druge jednakosti dobijamo da je r 2 deljivo sa r 0 . I tako dalje. Iz posljednje jednakosti dobijamo da je r k djeljiv sa r 0 . Dakle, r k =gcd(a, b) .
Iz razmatranog svojstva najvećeg zajedničkog djelitelja proizlazi da se skup zajedničkih djelitelja brojeva a i b poklapa sa skupom djelitelja najvećeg zajedničkog djelitelja ovih brojeva. Ovaj zaključak iz Euklidovog algoritma nam omogućava da pronađemo sve zajedničke djelitelje dvaju brojeva kao djelitelje gcd ovih brojeva.
Neka su a i b cijeli brojevi koji nisu istovremeno jednaki nuli, tada postoje takvi cijeli brojevi u 0 i v 0 , tada je tačna jednakost gcd(a, b)=a u 0 +b v 0. Posljednja jednakost je linearni prikaz najvećeg zajedničkog djelitelja brojeva a i b, ova jednakost se zove Bezoutov omjer, a brojevi u 0 i v 0 su Bezoutovi koeficijenti.
Dokaz.
Prema Euklidovom algoritmu možemo napisati sljedeće jednakosti
Iz prve jednakosti imamo r 1 =a−b q 1 , i, označavajući 1=s 1 i −q 1 =t 1 , ova jednakost ima oblik r 1 =s 1 a+t 1 b , a brojevi s 1 i t 1 su cijeli brojevi. Tada iz druge jednakosti dobijamo 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. Označavajući −s 1 q 2 =s 2 i 1−t 1 q 2 =t 2 , posljednja jednakost se može napisati kao r 2 =s 2 a+t 2 b , a s 2 i t 2 su cijeli brojevi (jer suma , razlika i proizvod cijelih brojeva je cijeli broj). Slično, iz treće jednakosti dobijamo r 3 =s 3 ·a+t 3 ·b, iz četvrte r 4 =s 4 ·a+t 4 ·b, i tako dalje. Konačno, r k =s k ·a+t k ·b , gdje su s k i t k cijeli brojevi. Pošto je r k =gcd(a, b) , i označava s k =u 0 i t k =v 0 , dobijamo linearnu reprezentaciju gcd traženog oblika: gcd(a, b)=a u 0 +b v 0 .
Ako je m bilo koji prirodan broj, onda gcd(m a, m b)=m gcd(a, b).
Obrazloženje za ovo svojstvo najvećeg zajedničkog djelitelja je sljedeće. Ako pomnožimo sa m obje strane svake od jednakosti Euklidovog algoritma, dobićemo da je gcd(m a, m b)=m r k , a r k je gcd(a, b) . dakle, gcd(m a, m b)=m gcd(a, b).
Ovo svojstvo najvećeg zajedničkog djelitelja je osnova za metodu pronalaženja GCD pomoću faktorizacije prostih slojeva.
Neka je p bilo koji zajednički djelitelj brojeva a i b , tada gcd(a:p, b:p)=gcd(a, b):p, posebno, ako je p=gcd(a, b) imamo gcd(a:gcd(a, b), b:gcd(a, b))=1, to jest, brojevi a:gcd(a, b) i b:gcd(a, b) su međusobno prosti.
Pošto su a=p (a:p) i b=p (b:p) , a zbog prethodnog svojstva, možemo napisati lanac jednakosti oblika gcd(a, b)=gcd(p (a:p), p (b:p))= p·gcd(a:p, b:p) , odakle slijedi jednakost koju treba dokazati.
Upravo dokazano svojstvo najvećeg zajedničkog djelitelja leži u osnovi.
Recimo sada svojstvo GCD, koje svodi problem pronalaženja najvećeg zajedničkog djelitelja tri ili više brojeva na sukcesivno pronalaženje GCD dva broja.
Najveći zajednički djelitelj brojeva a 1 , a 2 , ..., a k je jednak broju d k , koji se nalazi u sekvencijalnom izračunavanju GCD(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 .
Dokaz je zasnovan na posledicama iz Euklidovog algoritma. Zajednički djelitelji brojeva a 1 i a 2 su isti kao i djelitelji brojeva d 2 . Tada se zajednički djelitelji brojeva a 1, a 2 i a 3 poklapaju sa zajedničkim djeliteljima brojeva d 2 i a 3, pa se poklapaju sa djeliteljima d 3 . Zajednički djelitelji brojeva a 1, a 2, a 3 i a 4 isti su kao zajednički djelitelji brojeva d 3 i a 4, dakle isti kao i djelitelji brojeva d 4. I tako dalje. Konačno, zajednički djelitelji brojeva a 1 , a 2 , …, a k se poklapaju sa djeliteljima d k . A pošto je najveći djelitelj broja d k sam broj d k, onda GCD(a 1 , a 2 , …, a k)=d k.
Ovim je završen pregled glavnih svojstava najvećeg zajedničkog djelitelja.
Bibliografija.
- Vilenkin N.Ya. itd. Matematika. 6. razred: udžbenik za obrazovne ustanove.
- Vinogradov I.M. Osnove teorije brojeva.
- Mikhelovich Sh.Kh. Teorija brojeva.
- Kulikov L.Ya. i dr. Zbirka zadataka iz algebre i teorije brojeva: Udžbenik za studente fiz.-mat. specijalnosti pedagoških instituta.
GCD je najveći zajednički djelitelj.
Da biste pronašli najveći zajednički djelitelj nekoliko brojeva:
- odrediti faktore zajedničke za oba broja;
- pronaći proizvod zajedničkih faktora.
Primjer pronalaženja GCD-a:
Pronađite GCD brojeva 315 i 245.
315 = 5 * 3 * 3 * 7;
245 = 5 * 7 * 7.
2. Napišite faktore zajedničke za oba broja:
3. Pronađite proizvod zajedničkih faktora:
gcd(315; 245) = 5 * 7 = 35.
Odgovor: GCD(315; 245) = 35.
Pronalaženje NOC-a
LCM je najmanji umnožak.
Da biste pronašli najmanji zajednički višekratnik nekoliko brojeva:
- rastaviti brojeve na proste faktore;
- napišite faktore uključene u proširenje jednog od brojeva;
- dodajte im faktore koji nedostaju iz proširenja drugog broja;
- naći proizvod rezultujućih faktora.
Primjer pronalaženja NOC-a:
Pronađite LCM brojeva 236 i 328:
1. Razlažemo brojeve na proste faktore:
236 = 2 * 2 * 59;
328 = 2 * 2 * 2 * 41.
2. Zapišite faktore uključene u proširenje jednog od brojeva i dodajte im faktore koji nedostaju iz proširenja drugog broja:
2; 2; 59; 2; 41.
3. Pronađite proizvod rezultujućih faktora:
LCM(236; 328) = 2 * 2 * 59 * 2 * 41 = 19352.
Odgovor: LCM(236; 328) = 19352.
Da biste pronašli GCD (najveći zajednički djelitelj) dva broja, trebate:
2. Naći (podvući) sve zajedničke proste faktore u dobijenim proširenjima.
3. Pronađite proizvod zajedničkih prostih faktora.
Da biste pronašli LCM (najmanji zajednički višekratnik) dva broja, trebate:
1. Rastavite ove brojeve na proste faktore.
2. Proširivanje jednog od njih dopuniti onim faktorima proširenja drugog broja, kojih nema u proširenju prvog.
3. Izračunati proizvod dobijenih faktora.