Izračun čvora. Najveći zajednički djelitelj i najmanji zajednički višekratnik

Idemo riješiti problem. Imamo dvije vrste kolačića. Neki su čokoladni, a drugi obični. Čokoladnih ima 48, a običnih 36. Od ovih kolačića morate napraviti najveći mogući broj darova i sve ih morate iskoristiti.

Najprije zapišimo sve djelitelje svakog od ova dva broja, jer oba ova broja moraju biti djeljiva s brojem darova.

Dobivamo

• 48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48.
• 36: 1, 2, 3, 4, 6, 9, 12, 18, 36.

Pronađimo među zajedničkim djeliteljima koje imaju i prvi i drugi broj.

Zajednički faktori će biti: 1, 2, 3, 4, 6, 12.

Najveći zajednički faktor od svih je broj 12. Taj se broj naziva najvećim zajedničkim faktorom brojeva 36 i 48.

Na temelju dobivenih rezultata možemo zaključiti da se od svih kolačića može napraviti 12 darova. Jedan takav poklon sadržavat će 4 čokoladna kolačića i 3 obična kolačića.

Pronalaženje najvećeg zajedničkog djelitelja

• Najveći prirodni broj koji bez ostatka dijeli dva broja a i b zove se najveći zajednički djelitelj tih brojeva.

Ponekad se za skraćenje unosa koristi kratica GCD.

Neki parovi brojeva imaju jedan kao najveći zajednički djelitelj. Takvi se brojevi nazivaju međusobno prosti brojevi. Na primjer, brojevi 24 i 35 imaju GCD =1.

Kako pronaći najveći zajednički djelitelj

Da bismo pronašli najveći zajednički djelitelj, nije potrebno zapisati sve djelitelje zadanih brojeva.

Možete to učiniti drugačije. Prvo rastavite oba broja na proste faktore.

• 48 = 2*2*2*2*3,
• 36 = 2*2*3*3.

Sada ćemo od faktora koji ulaze u proširenje prvog broja prekrižiti sve one koji nisu uključeni u proširenje drugog broja. U našem slučaju to su dvije dvojke.

• 48 = 2*2*2*2*3 ,
• 36 = 2*2*3 *3.

Preostali faktori su 2, 2 i 3. Njihov umnožak je 12. Taj će broj biti najveći zajednički djelitelj brojeva 48 i 36.

Ovo se pravilo može proširiti na slučaj tri, četiri itd. brojevima.

Opća shema za pronalaženje najvećeg zajedničkog djelitelja

• 1. Podijelite brojeve na proste faktore.
• 2. Od faktora uključenih u proširenje jednog od ovih brojeva prekriži one koji nisu uključeni u proširenje drugih brojeva.
• 3. Izračunajte umnožak preostalih faktora.

Najveći zajednički djelitelj i najmanji zajednički višekratnik ključni su aritmetički koncepti koji olakšavaju rad s razlomcima. LCM i najčešće se koriste za pronalaženje zajedničkog nazivnika nekoliko razlomaka.

Osnovni koncepti

Djelitelj cijelog broja X je drugi cijeli broj Y kojim se X dijeli bez ostatka. Na primjer, djelitelj broja 4 je 2, a 36 je 4, 6, 9. Višekratnik cijelog broja X je broj Y koji je djeljiv s X bez ostatka. Na primjer, 3 je višekratnik broja 15, a 6 je višekratnik broja 12.

Za svaki par brojeva možemo pronaći njihove zajedničke djelitelje i višekratnike. Na primjer, za 6 i 9, zajednički višekratnik je 18, a zajednički djelitelj je 3. Očito, parovi mogu imati nekoliko djelitelja i višekratnika, tako da izračuni koriste najveći djelitelj GCD i najmanji višekratnik LCM.

Najmanji djelitelj je besmislen, jer je za svaki broj uvijek jedan. Najveći višekratnik je također besmislen, jer niz višekratnika ide u beskonačnost.

Pronalaženje gcd-a

Postoje mnoge metode za pronalaženje najvećeg zajedničkog djelitelja, od kojih su najpoznatije:

• sekvencijalno traženje djelitelja, odabir zajedničkih za par i traženje najvećeg od njih;
• rastavljanje brojeva na nedjeljive faktore;
• Euklidov algoritam;
• binarni algoritam.

Danas u obrazovnim ustanovama najpopularnije metode su dekompozicija na proste faktore i Euklidov algoritam. Potonji se pak koristi pri rješavanju Diofantovih jednadžbi: traženje GCD-a potrebno je za provjeru mogućnosti razlučivanja u jednadžbi u cijelim brojevima.

Pronalaženje NOO-a

Najmanji zajednički višekratnik također se određuje sekvencijalnim pretraživanjem ili dekompozicijom na nedjeljive faktore. Osim toga, lako je pronaći LCM ako je najveći djelitelj već određen. Za brojeve X i Y, LCM i GCD povezani su sljedećim odnosom:

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

Na primjer, ako je GCM(15,18) = 3, tada je LCM(15,18) = 15 × 18 / 3 = 90. Najočitiji primjer korištenja LCM je pronaći zajednički nazivnik, koji je najmanji zajednički višekratnik zadani razlomci.

Koprosti brojevi

Ako par brojeva nema zajedničkih djelitelja, onda se takav par naziva međusobno prostim. Gcd za takve parove uvijek je jednaka jedinici, a na temelju veze između djelitelja i višekratnika, gcd za međusobno proste parove jednaka je njihovom umnošku. Na primjer, brojevi 25 i 28 su relativno prosti, jer nemaju zajedničkih djelitelja, a LCM(25, 28) = 700, što odgovara njihovom umnošku. Bilo koja dva nedjeljiva broja uvijek će biti relativno prosti.

Zajednički djelitelj i višestruki kalkulator

Pomoću našeg kalkulatora možete izračunati GCD i LCM za proizvoljan broj brojeva koje možete izabrati. Zadaci o izračunu zajedničkih djelitelja i višekratnika nalaze se u aritmetici 5. i 6. razreda, ali GCD i LCM ključni su pojmovi u matematici i koriste se u teoriji brojeva, planimetriji i komunikativnoj algebri.

Primjeri iz stvarnog života

Zajednički nazivnik razlomaka

Najmanji zajednički višekratnik koristi se pri pronalaženju zajedničkog nazivnika nekoliko razlomaka. Recimo da u aritmetičkom problemu trebate zbrojiti 5 razlomaka:

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

Za zbrajanje razlomaka, izraz se mora svesti na zajednički nazivnik, što se svodi na problem pronalaženja LCM-a. Da biste to učinili, odaberite 5 brojeva u kalkulatoru i unesite vrijednosti nazivnika u odgovarajuće ćelije. Program će izračunati LCM (8, 9, 12, 15, 18) = 360. Sada trebate izračunati dodatne faktore za svaki razlomak, koji su definirani kao omjer LCM-a i nazivnika. Tako bi dodatni množitelji izgledali ovako:

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

Nakon toga pomnožimo sve razlomke s odgovarajućim dodatnim faktorom i dobijemo:

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

Lako možemo zbrojiti takve razlomke i dobiti rezultat kao 159/360. Smanjujemo razlomak za 3 i vidimo konačni odgovor - 53/120.

Rješavanje linearnih Diofantovih jednadžbi

Linearne Diofantove jednadžbe su izrazi oblika ax + by = d. Ako je omjer d / gcd(a, b) cijeli broj, onda je jednadžba rješiva ​​u cijelim brojevima. Provjerimo nekoliko jednadžbi da vidimo imaju li cjelobrojno rješenje. Prvo provjerimo jednadžbu 150x + 8y = 37. Pomoću kalkulatora nalazimo GCD (150,8) = 2. Podijelimo 37/2 = 18,5. Broj nije cijeli broj, stoga jednadžba nema cjelobrojne korijene.

Provjerimo jednadžbu 1320x + 1760y = 10120. Pomoću kalkulatora pronađite GCD(1320, 1760) = 440. Podijelite 10120/440 = 23. Kao rezultat, dobivamo cijeli broj, stoga je Diofantova jednadžba rješiva ​​u cjelobrojnim koeficijentima .

Zaključak

GCD i LCM igraju veliku ulogu u teoriji brojeva, a sami koncepti naširoko se koriste u raznim područjima matematike. Koristite naš kalkulator za izračun najvećih djelitelja i najmanjih višekratnika bilo kojeg broja brojeva.

Materijal prikazan u nastavku logičan je nastavak teorije iz članka pod naslovom LCM - najmanji zajednički višekratnik, definicija, primjeri, veza između LCM i GCD. Ovdje ćemo razgovarati o pronalaženje najmanjeg zajedničkog višekratnika (LCM), a posebnu pozornost posvetit ćemo rješavanju primjera. Prvo ćemo pokazati kako se LCM dva broja izračunava pomoću GCD ovih brojeva. Zatim ćemo pogledati pronalaženje najmanjeg zajedničkog višekratnika rastavljanjem brojeva na proste faktore. Nakon ovoga ćemo se usredotočiti na pronalaženje LCM-a tri ili više brojeva, a također ćemo obratiti pozornost na izračunavanje LCM-a negativnih brojeva.

Navigacija po stranici.

Izračunavanje najmanjeg zajedničkog višekratnika (LCM) putem GCD-a

Jedan način da se pronađe najmanji zajednički višekratnik temelji se na odnosu između LCM i GCD. Postojeća veza između LCM i GCD omogućuje nam izračunavanje najmanjeg zajedničkog višekratnika dva prirodna cijela broja preko poznatog najvećeg zajedničkog djelitelja. Odgovarajuća formula je LCM(a, b)=a b:NOT(a, b) . Pogledajmo primjere pronalaženja LCM-a pomoću dane formule.

Primjer.

Odredi najmanji zajednički višekratnik dvaju brojeva 126 i 70.

Riješenje.

U ovom primjeru a=126 , b=70 . Poslužimo se vezom između LCM i GCD izraženom formulom LCM(a, b)=a b:NOT(a, b). Odnosno, prvo moramo pronaći najveći zajednički djelitelj brojeva 70 i 126, nakon čega pomoću zapisane formule možemo izračunati LCM tih brojeva.

Nađimo GCD(126, 70) koristeći Euklidov algoritam: 126=70·1+56, 70=56·1+14, 56=14·4, dakle, GCD(126, 70)=14.

Sada nalazimo traženi najmanji zajednički višekratnik: NOD(126, 70)=126·70:NOD(126, 70)= 126·70:14=630.

Odgovor:

LCM(126, 70)=630.

Primjer.

Čemu je jednako LCM(68, 34)?

Riješenje.

Jer 68 je djeljiv sa 34, tada je GCD(68, 34)=34. Sada izračunavamo najmanji zajednički višekratnik: NOD(68, 34)=68·34:NOD(68, 34)= 68·34:34=68.

Odgovor:

LCM(68, 34)=68.

Imajte na umu da prethodni primjer odgovara sljedećem pravilu za pronalaženje LCM-a za pozitivne cijele brojeve a i b: ako je broj a djeljiv s b, tada je najmanji zajednički višekratnik ovih brojeva a.

Pronalaženje LCM rastavljanjem brojeva na proste faktore

Drugi način pronalaska najmanjeg zajedničkog višekratnika temelji se na rastavljanju brojeva na proste faktore. Ako sastavite umnožak od svih prostih faktora zadanih brojeva, a zatim iz tog umnoška isključite sve zajedničke proste faktore prisutne u dekompoziciji danih brojeva, tada će rezultirajući umnožak biti jednak najmanjem zajedničkom višekratniku danih brojeva .

Navedeno pravilo za određivanje LCM slijedi iz jednakosti LCM(a, b)=a b:NOT(a, b). Doista, umnožak brojeva a i b jednak je umnošku svih faktora uključenih u proširenje brojeva a i b. Zauzvrat, GCD(a, b) jednak je umnošku svih prostih faktora koji su istovremeno prisutni u proširenjima brojeva a i b (kao što je opisano u odjeljku o pronalaženju GCD-a korištenjem ekspanzije brojeva u proste faktore).

Navedimo primjer. Recimo da je 75=3·5·5 i 210=2·3·5·7. Sastavimo umnožak svih faktora ovih proširenja: 2·3·3·5·5·5·7 . Sada iz ovog umnoška isključujemo sve faktore prisutne i u proširenju broja 75 i u proširenju broja 210 (ovi faktori su 3 i 5), tada će umnožak imati oblik 2·3·5·5·7 . Vrijednost ovog umnoška jednaka je najmanjem zajedničkom višekratniku brojeva 75 i 210, tj. NOC(75, 210)= 2·3·5·5·7=1,050.

Primjer.

Rastavite brojeve 441 i 700 na proste faktore i pronađite najmanji zajednički višekratnik tih brojeva.

Riješenje.

Rastavimo brojeve 441 i 700 na proste faktore:

Dobivamo 441=3·3·7·7 i 700=2·2·5·5·7.

Kreirajmo sada umnožak svih faktora uključenih u proširenje ovih brojeva: 2·2·3·3·5·5·7·7·7. Isključimo iz ovog umnoška sve faktore koji su istovremeno prisutni u oba proširenja (postoji samo jedan takav faktor - to je broj 7): 2·2·3·3·5·5·7·7. Tako, LCM(441, 700)=2·2·3·3·5·5·7·7=44 100.

Odgovor:

NOC(441, 700)= 44 100 .

Pravilo za pronalaženje LCM-a korištenjem faktorizacije brojeva na proste faktore može se formulirati malo drugačije. Ako se faktorima iz proširenja broja a dodaju faktori koji nedostaju iz proširenja broja b, tada će vrijednost dobivenog umnoška biti jednaka najmanjem zajedničkom višekratniku brojeva a i b.

Na primjer, uzmimo iste brojeve 75 i 210, njihova dekompozicija na proste faktore je sljedeća: 75=3·5·5 i 210=2·3·5·7. Faktorima 3, 5 i 5 iz proširenja broja 75 pribrojimo nedostajuće faktore 2 i 7 iz proširenja broja 210, dobijemo umnožak 2·3·5·5·7 čija je vrijednost jednako LCM(75, 210).

Primjer.

Pronađite najmanji zajednički višekratnik brojeva 84 i 648.

Riješenje.

Prvo dobivamo rastave brojeva 84 i 648 na proste faktore. Izgledaju kao 84=2·2·3·7 i 648=2·2·2·3·3·3·3. Faktorima 2, 2, 3 i 7 iz proširenja broja 84 pribrojimo faktore koji nedostaju 2, 3, 3 i 3 iz proširenja broja 648, dobijemo umnožak 2 2 2 3 3 3 3 7, što je jednako 4 536 . Dakle, željeni najmanji zajednički višekratnik brojeva 84 i 648 je 4,536.

Odgovor:

LCM(84, 648)=4,536.

Pronalaženje LCM tri ili više brojeva

Najmanji zajednički višekratnik tri ili više brojeva može se pronaći uzastopnim pronalaženjem LCM dvaju brojeva. Prisjetimo se odgovarajućeg teorema, koji daje način da se pronađe LCM tri ili više brojeva.

Teorema.

Neka su zadani pozitivni cijeli brojevi a 1 , a 2 , …, a k, najmanji zajednički višekratnik m k ovih brojeva nalazi se sekvencijalnim izračunavanjem m 2 = LCM(a 1 , a 2) , m 3 = LCM(m 2 , a 3) , … , m k = LCM(m k−1 , a k) .

Razmotrimo primjenu ovog teorema na primjeru pronalaženja najmanjeg zajedničkog višekratnika četiriju brojeva.

Primjer.

Pronađite LCM četiri broja 140, 9, 54 i 250.

Riješenje.

U ovom primjeru, a 1 =140, a 2 =9, a 3 =54, a 4 =250.

Prvo nalazimo m 2 = LOC(a 1 , a 2) = LOC(140, 9). Da bismo to učinili, koristeći Euklidov algoritam, odredimo GCD(140, 9), imamo 140=9·15+5, 9=5·1+4, 5=4·1+1, 4=1·4, prema tome, GCD(140, 9)=1 , odakle NOD(140, 9)=140 9:NOT(140, 9)= 140·9:1=1,260. Odnosno, m 2 =1 260.

Sada nalazimo m 3 = LOC (m 2 , a 3) = LOC (1 260, 54). Izračunajmo ga preko GCD(1 260, 54), koji također određujemo pomoću Euklidovog algoritma: 1 260=54·23+18, 54=18·3. Tada je gcd(1,260, 54)=18, iz čega je gcd(1,260, 54)= 1,260·54:gcd(1,260, 54)= 1,260·54:18=3,780. Odnosno, m 3 =3 780.

Ostaje samo pronaći m 4 = LOC (m 3, a 4) = LOC (3 780, 250). Da bismo to učinili, nalazimo GCD(3,780, 250) koristeći Euklidov algoritam: 3,780=250·15+30, 250=30·8+10, 30=10·3. Prema tome, GCM(3,780, 250)=10, odakle je GCM(3,780, 250)= 3 780 250: GCD(3 780, 250)= 3.780·250:10=94.500. To jest, m 4 =94,500.

Dakle, najmanji zajednički višekratnik originalna četiri broja je 94 500.

Odgovor:

LCM(140, 9, 54, 250)=94,500.

U mnogim je slučajevima prikladno pronaći najmanji zajednički višekratnik tri ili više brojeva korištenjem prostih faktora danih brojeva. U tom slučaju morate se pridržavati sljedećeg pravila. Najmanji zajednički višekratnik više brojeva jednak je umnošku koji se sastavlja na sljedeći način: faktori koji nedostaju iz proširenja drugog broja pribrajaju se svim faktorima iz proširenja prvog broja, faktori koji nedostaju iz proširenja treći se broj dodaje dobivenim faktorima, i tako dalje.

Pogledajmo primjer pronalaženja najmanjeg zajedničkog višekratnika korištenjem proste faktorizacije.

Primjer.

Odredi najmanji zajednički višekratnik pet brojeva 84, 6, 48, 7, 143.

Riješenje.

Prvo, dobivamo dekompozicije ovih brojeva na proste faktore: 84=2·2·3·7, 6=2·3, 48=2·2·2·2·3, 7 (7 je prost broj, poklapa se s njegovim rastavljanjem na proste faktore) i 143=11·13.

Da biste pronašli LCM ovih brojeva, faktorima prvog broja 84 (to su 2, 2, 3 i 7), trebate dodati faktore koji nedostaju iz proširenja drugog broja 6. Rastavljanje broja 6 ne sadrži faktore koji nedostaju, jer su i 2 i 3 već prisutni u rastavljanju prvog broja 84. Dalje, faktorima 2, 2, 3 i 7 dodamo faktore 2 i 2 koji nedostaju iz proširenja trećeg broja 48, dobivamo skup faktora 2, 2, 2, 2, 3 i 7. Neće biti potrebno dodavati množitelje ovom skupu u sljedećem koraku, budući da je 7 već sadržano u njemu. Na kraju faktorima 2, 2, 2, 2, 3 i 7 pribrajamo faktore 11 i 13 koji nedostaju iz proširenja broja 143. Dobivamo umnožak 2·2·2·2·3·7·11·13, što je jednako 48,048.

Da biste razumjeli kako izračunati LCM, prvo morate odrediti značenje pojma "višestruko".

Višekratnik A je prirodan broj koji je djeljiv s A bez ostatka, dakle, brojevi koji su višekratnici broja 5 mogu se smatrati 15, 20, 25 i tako dalje.

Može postojati ograničen broj djelitelja određenog broja, ali postoji beskonačan broj višekratnika.

Zajednički višekratnik prirodnih brojeva je broj koji je s njima djeljiv bez ostatka.

Kako pronaći najmanji zajednički višekratnik brojeva

Najmanji zajednički višekratnik (NZM) brojeva (dva, tri ili više) je najmanji prirodni broj koji je djeljiv sa svim tim brojevima.

Da biste pronašli LOC, možete koristiti nekoliko metoda.

Za male brojeve zgodno je zapisati sve višekratnike tih brojeva na crtu dok ne pronađete nešto zajedničko među njima. Višekratnici se označavaju velikim slovom K.

Na primjer, višekratnici broja 4 mogu se napisati ovako:

K (4) = (8,12, 16, 20, 24, ...)

K (6) = (12, 18, 24, ...)

Dakle, možete vidjeti da je najmanji zajednički višekratnik brojeva 4 i 6 broj 24. Ovaj zapis se radi na sljedeći način:

LCM(4, 6) = 24

Ako su brojevi veliki, pronađite zajednički višekratnik tri ili više brojeva, tada je bolje koristiti drugu metodu izračuna LCM.

Da biste dovršili zadatak, morate zadane brojeve rastaviti na proste faktore.

Najprije na crtu treba zapisati razlaganje najvećeg broja, a ispod njega - ostatak.

Dekompozicija svakog broja može sadržavati različit broj faktora.

Na primjer, rastavimo brojeve 50 i 20 na proste faktore.

U proširenju manjeg broja treba istaknuti faktore koji nedostaju u proširenju prvog najvećeg broja, a zatim mu ih dodati. U prikazanom primjeru nedostaje dvojka.

Sada možete izračunati najmanji zajednički višekratnik brojeva 20 i 50.

LCM(20, 50) = 2 * 5 * 5 * 2 = 100

Dakle, umnožak prostih faktora većeg broja i faktora drugog broja koji nisu bili uključeni u proširenje većeg broja bit će najmanji zajednički višekratnik.

Da biste pronašli LCM tri ili više brojeva, trebali biste ih sve rastaviti na proste faktore, kao u prethodnom slučaju.

Kao primjer, možete pronaći najmanji zajednički višekratnik brojeva 16, 24, 36.

36 = 2 * 2 * 3 * 3

24 = 2 * 2 * 2 * 3

16 = 2 * 2 * 2 * 2

Dakle, samo dvije dvojke iz proširenja šesnaest nisu ušle u faktoriziranje većeg broja (jedan je u proširenju dvadeset četiri).

Dakle, potrebno ih je dodati proširenju većeg broja.

LCM(12, 16, 36) = 2 * 2 * 3 * 3 * 2 * 2 = 9

Postoje posebni slučajevi određivanja najmanjeg zajedničkog višekratnika. Dakle, ako se jedan od brojeva može podijeliti bez ostatka s drugim, tada će veći od tih brojeva biti najmanji zajednički višekratnik.

Na primjer, LCM od dvanaest i dvadeset četiri je dvadeset četiri.

Ako je potrebno pronaći najmanji zajednički višekratnik međusobno prostih brojeva koji nemaju identične djelitelje, tada će njihov LCM biti jednak njihovom umnošku.

Na primjer, LCM (10, 11) = 110.

Sada iu onome što slijedi pretpostavit ćemo da je barem jedan od ovih brojeva različit od nule. Ako su svi zadani brojevi jednaki nuli, onda je njihov zajednički djelitelj bilo koji cijeli broj, a kako cijelih brojeva ima beskonačno mnogo, ne može se 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 određivanje najvećeg zajedničkog djelitelja dva broja.

Definicija.

Najveći zajednički djelitelj dva cijela broja je najveći cijeli broj koji dijeli dva zadana cijela broja.

Za ukratko pisanje najvećeg zajedničkog djelitelja često se koristi skraćenica GCD - Greatest Common Divisor. Također, najveći zajednički djelitelj dvaju brojeva a i b često se označava kao GCD(a, b) .

Dajmo primjer najvećeg zajedničkog djelitelja (GCD) dva cijela broja. Najveći zajednički djelitelj brojeva 6 i −15 je 3. Opravdajmo ovo. 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. Od −3<−1<1<3 , то 3 – это наибольший общий делитель чисел 6 и −15 . То есть, НОД(6, −15)=3 .

Određivanje najvećeg zajedničkog djelitelja triju ili više cijelih brojeva slično je određivanju gcd dvaju brojeva.

Definicija.

Najveći zajednički djelitelj tri ili više cijelih brojeva je najveći cijeli broj koji istodobno dijeli sve zadane 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, tada možemo pisati GCD(a 1 , a 2 , …, a n)=b.

Kao primjer navedimo gcd četiri cijela broja −8, 52, 16 i −12, on je jednak 4, odnosno gcd(−8, 52, 16, −12)=4. To se može provjeriti tako da se zapišu svi djelitelji zadanih brojeva, među njima izaberu zajednički i odredi najveći zajednički djelitelj.

Imajte na umu da najveći zajednički djelitelj cijelih brojeva može biti jednak jednom od ovih brojeva. Ova je tvrdnja točna ako su svi zadani brojevi djeljivi s jednim od njih (dokaz je dan u sljedećem odlomku ovog članka). Na primjer, GCD(15, 60, −45)=15. To je istina, jer 15 dijeli i broj 15, i broj 60, i broj −45, a ne postoji zajednički djelitelj brojeva 15, 60 i −45 koji je veći od 15.

Posebno su zanimljivi takozvani relativno prosti brojevi - oni cijeli brojevi čiji je najveći zajednički djelitelj jednak jedan.

Svojstva najvećeg zajedničkog djelitelja, Euklidov algoritam

Najveći zajednički djelitelj ima niz karakterističnih rezultata, drugim riječima, niz svojstava. Sada ćemo navesti glavne svojstva najvećeg zajedničkog djelitelja (NOD), mi ćemo ih formulirati u obliku teorema i odmah dati dokaze.

Formulirati ćemo sva svojstva najvećeg zajedničkog djelitelja za prirodne brojeve, a razmatrat ćemo samo pozitivne djelitelje tih brojeva.

Najveći zajednički djelitelj brojeva a i b jednak je najvećem zajedničkom djelitelju brojeva b i a , odnosno gcd(a, b) = gcd(a, b) .

Ovo svojstvo GCD izravno slijedi iz definicije najvećeg zajedničkog djelitelja.

Ako je a djeljiv s b, tada se skup zajedničkih djelitelja brojeva a i b podudara sa skupom djelitelja broja b, konkretno, gcd(a, b)=b.

Dokaz.

Svaki zajednički djelitelj brojeva a i b je djelitelj svakog od tih brojeva, uključujući i broj b. S druge strane, budući da je a višekratnik b, svaki djelitelj broja b je djelitelj broja a zbog činjenice da djeljivost ima svojstvo tranzitivnosti, dakle, svaki djelitelj broja b je zajednički djelitelj brojeva a i b. Time je dokazano da ako je a djeljiv s b, tada se skup djelitelja brojeva a i b podudara sa skupom djelitelja jednog broja b. A kako je najveći djelitelj broja b sam broj b, onda 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, tada gcd(a, b)=gcd(a, a)=gcd(b, b)=a=b. Na primjer, GCD(132, 132)=132.

Dokazano svojstvo najvećeg djelitelja omogućuje nam da pronađemo NNO dva broja kada se jedan od njih podijeli s drugim. U ovom slučaju GCD je jednak jednom od ovih brojeva, koji je podijeljen drugim brojem. Na primjer, GCD(8, 24)=8, budući da je 24 višekratnik broja 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 podudara sa skupom zajedničkih djelitelja brojeva b i c, posebno gcd (a, b)=gcd (b, c) .

Opravdajmo ovo svojstvo GCD.

Kako vrijedi jednakost a=b·q+c, onda svaki zajednički djelitelj brojeva a i b dijeli i c (to proizlazi iz svojstava djeljivosti). Iz istog razloga svaki zajednički djelitelj b i c dijeli a. Dakle, skup zajedničkih djelitelja brojeva a i b podudara se sa skupom zajedničkih djelitelja brojeva b i c. Konkretno, najveći od ovih zajedničkih djelitelja također se mora podudarati, odnosno mora biti istinita sljedeća jednakost NOD(a, b) = NOD(b, c).

Sada ćemo formulirati i dokazati teorem, koji je Euklidski algoritam. Euklidov algoritam omogućuje pronalaženje GCD dvaju brojeva (pogledajte nalaženje GCD pomoću Euklidovog algoritma). Štoviše, Euklidov algoritam će nam omogućiti da dokažemo sljedeća svojstva najvećeg zajedničkog djelitelja.

Prije davanja formulacije teorema, preporučamo da osvježite svoje sjećanje na teorem iz teorijskog dijela, koji kaže da se dividenda a može predstaviti kao b q + r, gdje je b djelitelj, q neki cijeli broj koji se naziva nepotpuni kvocijent, a r je cijeli broj koji zadovoljava uvjet koji se naziva ostatak.

Dakle, neka je niz jednakosti istinit za dva pozitivna cijela broja a i b različita od nule

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 taj niz ne može sadržavati više od konačnog broja pozitivnih brojeva), tada je r k – to je najveći zajednički djelitelj brojeva a i b, odnosno r k = gcd(a, b) .

Dokaz.

Dokažimo najprije 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.

Po napisanim jednakostima kretat ćemo se odozdo prema gore. Iz posljednje jednakosti možemo reći da je r k−1 djeljivo s r k . Uzimajući u obzir ovu činjenicu, kao i prethodno svojstvo GCD-a, pretposljednja jednakost r k−2 =r k−1 ·q k +r k dopušta nam da tvrdimo da je r k−2 djeljivo s r k, budući da je r k−1 djeljivo s r k a r k je djeljiv s r k. Analogno, iz treće jednakosti odozdo zaključujemo da je r k−3 djeljivo s r k . I tako dalje. Iz druge jednakosti dobivamo da je b djeljiv s r k , a iz prve jednakosti dobivamo da je a djeljiv s r k . Dakle, r k je zajednički djelitelj brojeva a i b.

Ostaje dokazati da je r k = NOT(a, b) . Jer dovoljno je pokazati da svaki zajednički djelitelj brojeva a i b (označimo ga r 0 ) dijeli r k .

Kretat ćemo se duž izvornih jednakosti odozgo prema dolje. Zbog prethodnog svojstva iz prve jednakosti proizlazi da je r 1 djeljiv s r 0. Tada iz druge jednakosti dobivamo da je r 2 djeljiv s r 0 . I tako dalje. Iz posljednje jednakosti dobivamo da je r k djeljiv s 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 podudara sa skupom djelitelja najvećeg zajedničkog djelitelja tih brojeva. Ovaj korolar iz Euklidovog algoritma dopušta nam da pronađemo sve zajedničke djelitelje dvaju brojeva kao djelitelje gcd tih brojeva.

Neka su a i b cijeli brojevi koji nisu istodobno jednaki nuli, tada postoje cijeli brojevi u 0 i v 0, tada vrijedi 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 se jednakost naziva Bezoutova relacija, a brojevi u 0 i v 0 nazivaju se Bezoutovi koeficijenti.

Dokaz.

Pomoću Euklidovog algoritma možemo napisati sljedeće jednakosti



Iz prve jednakosti imamo r 1 =a−b·q 1, a označavajući 1=s 1 i −q 1 =t 1, ova jednakost ima oblik r 1 =s 1 ·a+t 1 ·b, i brojevi s 1 i t 1 su cijeli brojevi. Tada iz druge jednakosti dobivamo 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, zadnja se jednakost može napisati kao r 2 =s 2 ·a+t 2 ·b, a s 2 i t 2 su cijeli brojevi (budući da je zbroj, razlika i umnožak cijelih brojeva cijeli broj). Slično, iz treće jednakosti dobivamo r 3 =s 3 ·a+t 3 ·b, iz četvrte jednakosti 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. Budući da je r k =NOT(a, b) , a označavajući s k =u 0 i t k =v 0 , dobivamo linearni prikaz NOT-a traženog oblika: NOT(a, b)=a·u 0 +b·v 0 .

Ako je m bilo koji prirodan broj, tada NOT(m a, m b)=m NOT(a, b).

Obrazloženje ovog svojstva najvećeg zajedničkog djelitelja je sljedeće. Ako pomnožimo s m obje strane svake od jednakosti Euklidskog algoritma, dobivamo da je GCD(m·a, m·b)=m·r k , a r k je GCD(a, b) . Stoga, NOT(m a, m b)=m NOT(a, b).

Metoda pronalaženja GCD korištenjem proste faktorizacije temelji se na ovom svojstvu najvećeg zajedničkog djelitelja.

Neka je p bilo koji zajednički djelitelj brojeva a i b gcd(a:p, b:p)=gcd(a, b):p, posebno, ako je p=NOT(a, b) imamo gcd(a:gcd(a, b), b:gcd(a, b))=1, odnosno brojevi a:NOT(a, b) i b:NOT(a, b) su relativno prosti.

Kako je a=p·(a:p) i b=p·(b:p) , a zbog prethodnog svojstva, možemo napisati lanac jednakosti oblika GCD(a, b)=NOT(p (a:p), p (b:p))= p·NOT(a:p, b:p) , iz čega slijedi jednakost koja se dokazuje.

Svojstvo najvećeg zajedničkog djelitelja koje smo upravo dokazali je baza .

Razgovarajmo sada o svojstvu GCD, koje smanjuje problem pronalaženja najvećeg zajedničkog djelitelja tri ili više brojeva na uzastopno pronalaženje GCD dvaju brojeva.

Najveći zajednički djelitelj brojeva a 1 , a 2 , …, a k jednak je broju d k koji se nalazi sekvencijalnim izračunavanjem NOT(a 1 , a 2)=d 2 , NOT(d 2 , a 3)= d 3 , NOT(d 3 , a 4)=d 4 , …, NOT(d k-1 , a k)=d k .

Dokaz se temelji na korolariji Euklidovog algoritma. Zajednički djelitelji brojeva a 1 i a 2 podudaraju se s djeliteljima broja d 2. Tada se zajednički djelitelji brojeva a 1, a 2 i a 3 podudaraju sa zajedničkim djeliteljima brojeva d 2 i a 3, dakle, podudaraju se s djeliteljima od d 3. Zajednički djelitelji brojeva a 1, a 2, a 3 i a 4 podudaraju se sa zajedničkim djeliteljima brojeva d 3 i a 4, dakle, podudaraju se s djeliteljima brojeva d 4. I tako dalje. Konačno, zajednički djelitelji brojeva a 1, a 2, ..., a k podudaraju se s djeliteljima d k. A kako je najveći djelitelj broja d k sam broj d k, onda GCD(a 1 , a 2 , …, a k)=d k.

Ovime završavamo pregled osnovnih svojstava najvećeg zajedničkog djelitelja.

Bibliografija.

• Vilenkin N.Ya. i drugi. 6. razred: udžbenik za općeobrazovne ustanove.
• Vinogradov I.M. Osnove teorije brojeva.
• Mikhelovich Sh.H. Teorija brojeva.
• Kulikov L.Ya. i dr. Zbirka zadataka iz algebre i teorije brojeva: Udžbenik za studente fizike i matematike. specijalnosti pedagoških zavoda.