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

Hajde da rešimo 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 potrebno je napraviti maksimalan broj poklona i sve ih iskoristiti.

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

Dobijamo,

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

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

Uobičajeni faktori će biti: 1, 2, 3, 4, 6, 12.

Najveći zajednički faktor od svih je broj 12. Ovaj broj se zove najveći zajednički faktor brojeva 36 i 48.

Na osnovu dobijenih rezultata možemo zaključiti da se od svih kolačića može napraviti 12 poklona. Jedan takav poklon će sadržavati 4 čokoladna kolačića i 3 obična kolačića.

Pronalaženje najvećeg zajedničkog djelitelja

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

Ponekad se skraćenica GCD koristi za skraćenje unosa.

Neki parovi brojeva imaju jedan kao najveći zajednički djelitelj. Takvi brojevi se 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 datih brojeva.

Možete to učiniti drugačije. Prvo, razdijelite oba broja u proste faktore.

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

Sada ćemo od faktora koji su uključeni u proširenje prvog broja precrtati 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 proizvod je 12. Ovaj broj će biti najveći zajednički djelitelj brojeva 48 i 36.

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

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 precrtajte one koji nisu uključeni u proširenje drugih brojeva.
• 3. Izračunajte proizvod preostalih faktora.

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

Osnovni koncepti

Delitelj cijelog broja X je drugi cijeli broj Y kojim je X podijeljen 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 sa X bez ostatka. Na primjer, 3 je višekratnik od 15, a 6 je višekratnik od 12.

Za bilo koji par brojeva možemo pronaći njihove zajedničke djelitelje i višekratnike. Na primjer, za 6 i 9, zajednički djelitelj je 18, a zajednički djelitelj je 3. Očigledno, parovi mogu imati nekoliko djelitelja i višekratnika, tako da se u proračunima koriste najveći djelitelj GCD i najmanji višestruki LCM.

Najmanji djelitelj je besmislen, jer je za bilo koji broj uvijek jedan. Najveći umnožak je takođe besmislen, jer niz višekratnika ide u beskonačnost.

Finding gcd

Postoji mnogo metoda 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;
• dekompozicija brojeva na nedjeljive faktore;
• Euklidski algoritam;
• binarni algoritam.

Danas u obrazovnim ustanovama najpopularnije metode su dekompozicija na osnovne faktore i Euklidski algoritam. Potonji se, pak, koristi pri rješavanju Diofantovih jednadžbi: traženje GCD-a je potrebno da bi se provjerila mogućnost rezolucije u cijelim brojevima.

Pronalaženje NOC-a

Najmanji zajednički višekratnik se također 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čigledniji primjer korištenja LCM je pronalaženje zajedničkog nazivnika, koji je najmanji zajednički višekratnik dati razlomci.

Koprosti brojevi

Ako par brojeva nema zajedničkih djelitelja, onda se takav par naziva koprostim. Gcd za takve parove je uvijek jednak jedan, a na osnovu veze između djelitelja i višekratnika, gcd za koprime parove jednak je njihovom proizvodu. Na primjer, brojevi 25 i 28 su relativno prosti, jer nemaju zajedničkih djelitelja, a LCM(25, 28) = 700, što odgovara njihovom proizvodu. Bilo koja dva nedjeljiva broja uvijek će biti relativno prosti.

Zajednički djelitelj i višestruki kalkulator

Koristeći naš kalkulator možete izračunati GCD i LCM za proizvoljan broj brojeva koje možete izabrati. Zadaci za izračunavanje zajedničkih djelitelja i višekratnika nalaze se u aritmetici 5. i 6. razreda, ali GCD i LCM su ključni 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 se koristi kada se pronađe zajednički nazivnik višestrukih razlomaka. Recimo da u aritmetičkom zadatku trebate zbrojiti 5 razlomaka:

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

Za dodavanje razlomaka, izraz se mora svesti na zajednički nazivnik, što se svodi na problem pronalaženja LCM. 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 morate izračunati dodatne faktore za svaki razlomak, koji su definisani kao omjer LCM-a i nazivnika. Dakle, dodatni množitelji bi izgledali ovako:

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

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

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

Lako možemo sabrati takve razlomke i dobiti rezultat kao 159/360. Smanjujemo razlomak za 3 i vidimo konačan 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 jednačina da vidimo da li imaju cjelobrojno rješenje. Prvo, provjerimo jednačinu 150x + 8y = 37. Koristeći kalkulator, nalazimo GCD (150,8) = 2. Podijelimo 37/2 = 18,5. Broj nije cijeli broj, stoga jednadžba nema cjelobrojne korijene.

Provjerimo jednačinu 1320x + 1760y = 10120. Koristite kalkulator da nađete GCD(1320, 1760) = 440. Podijelite 10120/440 = 23. Kao rezultat, dobijamo cijeli broj, pa je Diofantov koeficijent tako u jednadžbi .

Zaključak

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

Materijal predstavljen u nastavku je logičan 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 pažnju ćemo posvetiti 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 u proste faktore. Nakon toga ćemo se fokusirati na pronalaženje LCM od tri ili više brojeva, a također ćemo obratiti pažnju na izračunavanje LCM negativnih brojeva.

Navigacija po stranici.

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

Jedan od načina da se pronađe najmanji zajednički višekratnik je zasnovan na odnosu između LCM i GCD. Postojeća veza između LCM i GCD omogućava nam da izračunamo najmanji zajednički višekratnik dva pozitivna cijela broja kroz poznati najveći zajednički djelitelj. Odgovarajuća formula je LCM(a, b)=a b:GCD(a, b) . Razmotrimo primjere pronalaženja LCM-a koristeći datu formulu.

Primjer.

Pronađite najmanji zajednički višekratnik dva broja 126 i 70.

Rješenje.

U ovom primjeru a=126, b=70. Koristimo vezu između LCM i GCD, izraženu formulom LCM(a, b)=a b:GCD(a, b). Odnosno, prvo moramo pronaći najveći zajednički djelitelj brojeva 70 i 126, nakon čega možemo izračunati LCM ovih brojeva koristeći napisanu formulu.

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: GCD(126, 70)=126·70:GCD(126, 70)= 126·70:14=630.

odgovor:

LCM(126, 70)=630 .

Primjer.

Čemu je jednako LCM(68, 34)?

Rješenje.

Jer 68 je djeljivo sa 34, tada je GCD(68, 34)=34. Sada izračunavamo najmanji zajednički višekratnik: GCD(68, 34)=68·34:GCD(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 sa b, tada je najmanji zajednički višekratnik ovih brojeva a.

Pronalaženje LCM-a rastavljanjem brojeva u proste faktore

Drugi način za pronalaženje najmanjeg zajedničkog višekratnika je baziran na faktoringu brojeva u proste faktore. Ako sastavite proizvod od svih prostih faktora datih brojeva, a zatim iz ovog proizvoda isključite sve uobičajene proste faktore prisutne u dekompozicijama datih brojeva, tada će rezultirajući proizvod biti jednak najmanjem zajedničkom višekratniku datih brojeva .

Navedeno pravilo za pronalaženje LCM proizlazi iz jednakosti LCM(a, b)=a b:GCD(a, b). Zaista, proizvod brojeva a i b jednak je proizvodu svih faktora uključenih u proširenje brojeva a i b. Zauzvrat, GCD(a, b) je jednak proizvodu svih prostih faktora koji su istovremeno prisutni u proširenjima brojeva a i b (kao što je opisano u odjeljku o pronalaženju GCD pomoću proširenja brojeva u proste faktore).

Dajemo primjer. Javite nam da je 75=3·5·5 i 210=2·3·5·7. Sastavimo proizvod od svih faktora ovih proširenja: 2·3·3·5·5·5·7 . Sada iz ovog proizvoda isključujemo sve faktore prisutne u proširenju broja 75 i proširenju broja 210 (ovi faktori su 3 i 5), tada će proizvod dobiti oblik 2·3·5·5·7 . Vrijednost ovog proizvoda jednaka je najmanjem zajedničkom višekratniku 75 i 210, tj. NOC(75, 210)= 2·3·5·5·7=1,050.

Primjer.

Faktorite brojeve 441 i 700 u proste faktore i pronađite najmanji zajednički višekratnik ovih brojeva.

Rješenje.

Razložimo brojeve 441 i 700 u proste faktore:

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

Sada napravimo proizvod od svih faktora koji su uključeni u proširenje ovih brojeva: 2·2·3·3·5·5·7·7·7. Izuzmimo iz ovog proizvoda 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. dakle, LCM(441, 700)=2·2·3·3·5·5·7·7=44 100.

odgovor:

NOC(441, 700)= 44 100 .

Pravilo za pronalaženje LCM koristeći faktorizaciju brojeva u proste faktore može se formulisati malo drugačije. Ako se faktori koji nedostaju iz proširenja broja b dodaju faktorima iz proširenja broja a, tada će vrijednost rezultirajućeg proizvoda biti jednaka najmanjem zajedničkom višekratniku brojeva a i b.

Na primjer, uzmimo iste brojeve 75 i 210, njihove dekompozicije na proste faktore su sljedeće: 75=3·5·5 i 210=2·3·5·7. Faktorima 3, 5 i 5 iz proširenja broja 75 dodamo faktore koji nedostaju 2 i 7 iz proširenja broja 210, dobijemo proizvod 2·3·5·5·7, čija je vrijednost jednako LCM(75, 210).

Primjer.

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

Rješenje.

Prvo dobijamo dekompozicije 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 dodamo faktore koji nedostaju 2, 3, 3 i 3 iz proširenja broja 648, dobijemo proizvod 2 2 2 3 3 3 3 7, što je jednako 4 536 . Dakle, željeni najmanji zajednički višekratnik od 84 i 648 je 4,536.

odgovor:

LCM(84, 648)=4,536 .

Pronalaženje LCM od tri ili više brojeva

Najmanji zajednički višekratnik tri ili više brojeva može se naći uzastopnim pronalaženjem LCM dva broja. Podsjetimo se odgovarajuće teoreme, koja daje način da se pronađe LCM od tri ili više brojeva.

Teorema.

Neka su dati 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 ove teoreme na primjeru pronalaženja najmanjeg zajedničkog višekratnika četiri broja.

Primjer.

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

Rješenje.

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

Prvo ćemo naći m 2 = LOC(a 1, a 2) = LOC(140, 9). Da bismo to uradili, koristeći Euklidov algoritam, odredimo GCD(140, 9), imamo 140=9·15+5, 9=5·1+4, 5=4·1+1, 4=1·4, dakle, GCD(140, 9)=1, odakle GCD(140, 9)=140 9:GCD(140, 9)= 140·9:1=1,260. Odnosno, m 2 =1 260.

Sada pronalazimo m 3 = LOC (m 2 , a 3) = LOC (1 260, 54). Izračunajmo ga kroz GCD(1 260, 54), koji takođe određujemo pomoću Euklidovog algoritma: 1 260=54·23+18, 54=18·3. Tada je gcd(1,260, 54)=18, od č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 uradili, nalazimo GCD(3,780, 250) koristeći Euklidov algoritam: 3,780=250·15+30, 250=30·8+10, 30=10·3. Dakle, 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 od originalna četiri broja je 94.500.

odgovor:

LCM(140, 9, 54, 250)=94.500.

U mnogim slučajevima, zgodno je pronaći najmanji zajednički umnožak tri ili više brojeva korištenjem prostih faktorizacija datih brojeva. U tom slučaju morate se pridržavati sljedećeg pravila. Najmanji zajednički umnožak nekoliko brojeva jednak je umnošku koji je sastavljen na sljedeći način: faktori koji nedostaju iz proširenja drugog broja dodaju se svim faktorima iz proširenja prvog broja, faktori koji nedostaju iz proširenja broja treći broj se dodaje rezultujućim faktorima, i tako dalje.

Pogledajmo primjer pronalaženja najmanjeg zajedničkog višekratnika pomoću faktorizacije.

Primjer.

Pronađite najmanji zajednički višekratnik od pet brojeva 84, 6, 48, 7, 143.

Rješenje.

Prvo, dobijamo 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 sa njegovom dekompozicijom 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), morate dodati faktore koji nedostaju iz proširenja drugog broja 6. Dekompozicija broja 6 ne sadrži faktore koji nedostaju, jer su i 2 i 3 već prisutni u dekompoziciji prvog broja 84. Zatim, faktorima 2, 2, 3 i 7 dodajemo faktore koji nedostaju 2 i 2 iz proširenja trećeg broja 48, dobijamo skup faktora 2, 2, 2, 2, 3 i 7. Neće biti potrebe za dodavanjem množitelja ovom skupu u sljedećem koraku, pošto je 7 već sadržano u njemu. Konačno, faktorima 2, 2, 2, 2, 3 i 7 dodajemo faktore 11 i 13 koji nedostaju iz proširenja broja 143. Dobijamo proizvod 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 sa A bez ostatka. Dakle, brojevi koji su višekratnici broja 5 mogu se smatrati 15, 20, 25 itd.

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 djeljiv s njima bez ostatka.

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

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

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

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

Na primjer, višekratnici od 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. Ova notacija 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čunavanja LCM-a.

Da biste izvršili zadatak, potrebno je da date brojeve rastavite u proste faktore.

Prvo trebate zapisati dekompoziciju najvećeg broja na liniji, a ispod njega - ostatak.

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

Na primjer, razložimo brojeve 50 i 20 u 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 20 i 50.

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

Tako će proizvod prostih faktora većeg broja i faktora drugog broja koji nisu uključeni u proširenje većeg broja biti najmanji zajednički višekratnik.

Da biste pronašli LCM od tri ili više brojeva, trebali biste ih sve rastaviti u 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 uključene u faktorizaciju većeg broja (jedan je u proširenju dvadeset četiri).

Stoga ih je potrebno 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 ovih 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 koprostih brojeva koji nemaju identične djelitelje, tada će njihov LCM biti jednak njihovom proizvodu.

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

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. Dakle, ne možemo 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 data cijela broja.

Da bi se ukratko zapisao najveći zajednički djelitelj, često se koristi skraćenica GCD - 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 damo primjer najvećeg zajedničkog djelitelja (GCD) dva cela broja. Najveći zajednički djelitelj brojeva 6 i −15 je 3. Hajde da opravdamo 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. Pošto −3<−1<1<3 , то 3 – это наибольший общий делитель чисел 6 и −15 . То есть, НОД(6, −15)=3 .

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

Definicija.

Najveći zajednički djelitelj tri ili više cijelih brojeva je najveći cijeli broj koji dijeli sve date brojeve u isto vrijeme.

Najveći zajednički djelitelj n cijelih brojeva a 1 , a 2 , …, a n ćemo označiti 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, dajmo 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 tako što ćete zapisati sve djelitelje datih brojeva, od njih izabrati zajedničke i odrediti 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 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 i broj 15, i broj 60, i broj −45, a ne postoji zajednički djelitelj brojeva 15, 60 i −45 koji prelazi 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, Euklidski 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, a razmatrat ćemo samo pozitivne djelitelje ovih 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 direktno slijedi iz definicije najvećeg zajedničkog djelitelja.

Ako je a djeljivo sa b, tada se skup zajedničkih djelitelja brojeva a i b poklapa sa skupom djelitelja broja 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 djelitelj broja a zbog činjenice da djeljivost ima svojstvo tranzitivnosti, stoga je svaki djelitelj broja b 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, 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, 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 se jedan od njih podijeli s drugim. U ovom slučaju, GCD je jednak jednom od ovih brojeva, koji je podijeljen s drugim brojem. 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 poklapa se sa skupom zajedničkih djelitelja brojeva b i c. Konkretno, najveći od ovih zajedničkih djelitelja također se mora podudarati, odnosno, sljedeća jednakost GCD(a, b) = GCD(b, c) mora biti tačna.

Sada ćemo formulisati i dokazati teoremu, koja je Euklidski algoritam. Euklid 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 formulacije teoreme, preporučujemo da osvježite svoje pamćenje 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 nepotpuni količnik, i r je cijeli broj koji zadovoljava uslov, naziva se ostatak.

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

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), onda je r k – ovo je najveći zajednički djelitelj brojeva 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 djeljiv sa r k . Uzimajući u obzir ovu činjenicu, kao i prethodno svojstvo GCD, pretposljednja jednakost r k−2 =r k−1 ·q k +r k nam omogućava da kažemo da je r k−2 deljivo sa r k, pošto je r k−1 deljivo sa r k i r k je djeljiv sa r k. Analogno, iz treće jednakosti odozdo zaključujemo da je r k−3 deljivo 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 brojeva a i b.

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

Kretaćemo se po originalnim jednakostima od vrha do dna. Zbog 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 omogućava nam da pronađemo sve zajedničke djelitelje dva broja kao djelitelje gcd ovih brojeva.

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

Dokaz.

Koristeći Euklidski algoritam 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, i 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 (pošto je zbir, razlika i proizvod cijelih brojeva cijeli broj). Slično, iz treće jednakosti dobijamo 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. 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).

Metoda pronalaženja GCD pomoću faktorizacije osnovnih faktora zasniva 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=GCD(a, b) imamo gcd(a:gcd(a, b), b:gcd(a, b))=1, odnosno brojevi a:GCD(a, b) i b:GCD(a, b) su relativno prosti.

Pošto 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) , iz čega slijedi jednakost koja se dokazuje.

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

Sada razgovarajmo o svojstvu GCD, koje svodi problem pronalaženja najvećeg zajedničkog djelitelja tri ili više brojeva na sekvencijalno pronalaženje GCD dva broja.

Najveći zajednički djelitelj brojeva a 1 , a 2 , …, a k jednak je broju d k , koji se nalazi sekvencijalnim izračunavanjem 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 Euklidovog algoritma. Zajednički djelitelji brojeva a 1 i a 2 poklapaju se sa djeliteljima 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, dakle, poklapaju se sa djeliteljima d 3. Zajednički djelitelji brojeva a 1, a 2, a 3 i a 4 poklapaju se sa zajedničkim djeliteljima brojeva d 3 i a 4, dakle, poklapaju se sa djeliteljima d 4. I tako dalje. Konačno, zajednički djelitelji brojeva a 1, a 2, ..., a k poklapaju se 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.

Ovo završava naš pregled osnovnih svojstava najvećeg zajedničkog djelitelja.

Bibliografija.

• Vilenkin N.Ya. i drugi. 6. razred: udžbenik za opšteobrazovne 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 instituta.