Najveći zajednički djelitelj (GCD): definicija, primjeri i svojstva. Pronalaženje GCD-a korištenjem Euklidovog algoritma i korištenjem prostih faktora
Najveći zajednički djelitelj
Definicija 2
Ako je prirodni broj a djeljiv prirodnim brojem $b$, tada se $b$ naziva djelitelj od $a$, a broj $a$ se naziva višekratnik od $b$.
Neka su $a$ i $b$ prirodni brojevi. Broj $c$ se naziva zajedničkim djeliteljem i za $a$ i za $b$.
Skup zajedničkih djelitelja brojeva $a$ i $b$ je konačan, jer nijedan od ovih djelitelja ne može biti veći od $a$. To znači da među ovim djeliteljima postoji najveći, koji se naziva najveći zajednički djelitelj brojeva $a$ i $b$, a za označavanje se koristi notacija:
$gcd \ (a;b) \ ili \ D \ (a;b)$
Da biste pronašli najveći zajednički djelitelj dva broja:
- Pronađite proizvod brojeva pronađenih u koraku 2. Rezultirajući broj će biti željeni najveći zajednički djelitelj.
Primjer 1
Pronađite gcd brojeva $121$ i $132.$
$242=2\cdot 11\cdot 11$
$132=2\cdot 2\cdot 3\cdot 11$
Odaberite brojeve koji su uključeni u proširenje ovih brojeva
$242=2\cdot 11\cdot 11$
$132=2\cdot 2\cdot 3\cdot 11$
Pronađite proizvod brojeva pronađenih u koraku 2. Rezultirajući broj će biti željeni najveći zajednički djelitelj.
$gcd=2\cdot 11=22$
Primjer 2
Pronađite GCD monoma $63$ i $81$.
Pronaći ćemo prema predstavljenom algoritmu. Za ovo:
Razložimo brojeve na proste faktore
$63=3\cdot 3\cdot 7$
$81=3\cdot 3\cdot 3\cdot 3$
Odabiremo brojeve koji su uključeni u proširenje ovih brojeva
$63=3\cdot 3\cdot 7$
$81=3\cdot 3\cdot 3\cdot 3$
Nađimo proizvod brojeva pronađenih u koraku 2. Rezultirajući broj će biti željeni najveći zajednički djelitelj.
$gcd=3\cdot 3=9$
GCD dva broja možete pronaći na drugi način, koristeći skup djelitelja brojeva.
Primjer 3
Pronađite gcd brojeva $48$ i $60$.
Odluka:
Pronađite skup djelitelja od $48$: $\left\((\rm 1,2,3.4.6,8,12,16,24,48)\right\)$
Sada pronađimo skup djelitelja od $60$:$\ \left\((\rm 1,2,3,4,5,6,10,12,15,20,30,60)\desno\)$
Nađimo presjek ovih skupova: $\left\((\rm 1,2,3,4,6,12)\right\)$ - ovaj skup će odrediti skup zajedničkih djelitelja brojeva $48$ i $60 $. Najveći element u ovom setu će biti broj $12$. Dakle, najveći zajednički djelitelj $48$ i $60$ je $12$.
Definicija NOC-a
Definicija 3
zajednički umnožak prirodnih brojeva$a$ i $b$ su prirodni broj koji je višekratnik i $a$ i $b$.
Uobičajeni višekratnici brojeva su brojevi koji su djeljivi sa originalom bez ostatka. Na primjer, za brojeve $25$ i $50$, zajednički višekratnici će biti brojevi $50,100,150,200$, itd.
Najmanji zajednički višekratnik će se zvati najmanji zajednički umnožak i označen sa LCM$(a;b)$ ili K$(a;b).$
Da biste pronašli LCM dva broja, trebate:
- Rastaviti brojeve na proste faktore
- Napišite faktore koji su dio prvog broja i dodajte im faktore koji su dio drugog i ne idu u prvi
Primjer 4
Pronađite LCM brojeva $99$ i $77$.
Pronaći ćemo prema predstavljenom algoritmu. Za ovo
Rastaviti brojeve na proste faktore
$99=3\cdot 3\cdot 11$
Zapišite faktore uključene u prvi
dodajte im faktore koji su dio drugog i ne idu u prvi
Pronađite proizvod brojeva pronađenih u koraku 2. Rezultirajući broj će biti željeni najmanji zajednički višekratnik
$LCC=3\cdot 3\cdot 11\cdot 7=693$
Sastavljanje lista djelitelja brojeva često oduzima mnogo vremena. Postoji način da se pronađe GCD koji se zove Euklidov algoritam.
Izjave na kojima se zasniva Euklidov algoritam:
Ako su $a$ i $b$ prirodni brojevi, a $a\vdots b$, onda je $D(a;b)=b$
Ako su $a$ i $b$ prirodni brojevi takvi da je $b
Koristeći $D(a;b)= D(a-b;b)$, možemo sukcesivno smanjivati brojeve koji se razmatraju dok ne dođemo do para brojeva tako da je jedan od njih djeljiv drugim. Tada će manji od ovih brojeva biti željeni najveći zajednički djelitelj za brojeve $a$ i $b$.
Svojstva GCD i LCM
- Svaki zajednički višekratnik $a$ i $b$ je djeljiv sa K$(a;b)$
- Ako je $a\vdots b$, onda je K$(a;b)=a$
Ako je K$(a;b)=k$ i $m$-prirodni broj, onda je K$(am;bm)=km$
Ako je $d$ zajednički djelitelj za $a$ i $b$, tada je K($\frac(a)(d);\frac(b)(d)$)=$\ \frac(k)(d ) $
Ako je $a\vdots c$ i $b\vdots c$, onda je $\frac(ab)(c)$ zajednički višekratnik $a$ i $b$
Za bilo koje prirodne brojeve $a$ i $b$ jednakost
$D(a;b)\cdot K(a;b)=ab$
Svaki zajednički djelitelj $a$ i $b$ je djelitelj $D(a;b)$
Ali mnogi prirodni brojevi su jednako djeljivi s drugim prirodnim brojevima.
na primjer:
Broj 12 je djeljiv sa 1, sa 2, sa 3, sa 4, sa 6, sa 12;
Broj 36 je djeljiv sa 1, sa 2, sa 3, sa 4, sa 6, sa 12, sa 18, sa 36.
Brojevi kojima je broj djeljiv (za 12 je 1, 2, 3, 4, 6 i 12) nazivaju se djelitelji brojeva. Delitelj prirodnog broja a je prirodan broj koji dijeli dati broj a bez traga. Prirodni broj koji ima više od dva faktora naziva se kompozitni. Imajte na umu da brojevi 12 i 36 imaju zajedničke djelitelje. Ovo su brojevi: 1, 2, 3, 4, 6, 12. Najveći djelitelj ovih brojeva je 12.
Zajednički djelitelj dva data broja a i b je broj kojim su oba data broja djeljiva bez ostatka a i b. Zajednički djelitelj više brojeva (GCD) je broj koji služi kao djelitelj za svaki od njih.
Ukratko, najveći zajednički djelitelj brojeva a i b su napisane ovako:
Primjer: gcd (12; 36) = 12.
Delitelji brojeva u zapisu rješenja označavaju veliko slovo"D".
primjer:
gcd (7; 9) = 1
Brojevi 7 i 9 imaju samo jedan zajednički djelitelj - broj 1. Takvi brojevi se nazivaju coprimechi slam.
Koprosti brojevi su prirodni brojevi koji imaju samo jedan zajednički djelitelj - broj 1. Njihov gcd je 1.
Najveći zajednički djelitelj (GCD), svojstva.
- Glavno svojstvo: najveći zajednički djelitelj m i n je djeljiv sa bilo kojim zajedničkim djeliteljem ovih brojeva. Primjer: za brojeve 12 i 18 najveći zajednički djelitelj je 6; djeljiv je sa svim zajedničkim djeliteljima ovih brojeva: 1, 2, 3, 6.
- Korol 1: skup zajedničkih djelitelja m i n poklapa se sa skupom djelitelja gcd( m, n).
- Korol 2: skup zajedničkih višekratnika m i n poklapa se sa skupom više LCM-ova ( m, n).
To posebno znači da je da bi se razlomak sveo na nesvodljiv oblik potrebno podijeliti njegov brojnik i imenilac s njihovim gcd.
- Najveći zajednički djelitelj brojeva m i n može se definirati kao najmanji pozitivni element skupa svih njihovih linearnih kombinacija:
i stoga predstavljaju linearnu kombinaciju brojeva m i n:
Ovaj omjer se zove Bezoutov omjer, i koeficijenti u i v — bezout koeficijenti. Bézout koeficijenti su efikasno izračunati proširenim Euklidovim algoritmom. Ova izjava je generalizovana na skupove prirodnih brojeva - njeno značenje je da je podgrupa grupe koju generiše skup ciklična i da je generisana jednim elementom: gcd ( a 1 , a 2 , … , a n).
Izračunavanje najvećeg zajedničkog djelitelja (gcd).
Efikasni načini za izračunavanje gcd dva broja su Euklidov algoritam i binarnialgoritam. Osim toga, GCD vrijednost ( m,n) može se lako izračunati ako je poznata kanonska ekspanzija brojeva m i n za primarne faktore:
gdje su različiti prosti brojevi i i su nenegativni cijeli brojevi (mogu biti nula ako odgovarajući prosti brojevi nisu u proširenju). Zatim gcd ( m,n) i LCM ( m,n) izraženi su formulama:
Ako ima više od dva broja: , njihov GCD se nalazi prema sljedećem algoritmu:
- ovo je željeni GCD.
Takođe, u cilju pronalaženja najveći zajednički djelitelj, možete razložiti svaki od datih brojeva na proste faktore. Zatim posebno napišite samo one faktore koji su uključeni u sve date brojeve. Zatim množimo brojeve zapisane među sobom - rezultat množenja je najveći zajednički djelitelj .
Analizirajmo izračun najvećeg zajedničkog djelitelja korak po korak:
1. Rastaviti djelitelje brojeva na proste faktore:
Proračuni se jednostavno pišu pomoću vertikalne trake. Lijevo od reda prvo zapišite dividendu, desno - djelitelj. Dalje u lijevom stupcu zapisujemo vrijednosti privatnog. Objasnimo odmah na primjeru. Razložimo brojeve 28 i 64 u proste faktore.
2. Podvlačimo iste proste faktore u oba broja:
28 = 2 . 2 . 7
64 = 2 . 2 . 2 . 2 . 2 . 2
3. Pronalazimo proizvod identičnih prostih faktora i zapisujemo odgovor:
GCD (28; 64) = 2. 2 = 4
Odgovor: GCD (28; 64) = 4
Lokaciju GCD-a možete urediti na dva načina: u stupcu (kao što je učinjeno gore) ili "u liniji".
Prvi način za pisanje GCD:
Pronađite GCD 48 i 36.
GCD (48; 36) = 2 . 2. 3 = 12
Drugi način za pisanje GCD:
Sada napišimo rješenje GCD pretraživanja u liniji. Pronađite GCD 10 i 15.
D(10) = (1, 2, 5, 10)
D(15) = (1, 3, 5, 15)
D(10, 15) = (1, 5)
Ovaj članak je o pronalaženje najvećeg zajedničkog djelitelja (gcd) dva i više brojevi. Prvo, razmotrite Euklidov algoritam, koji vam omogućava da pronađete GCD dva broja. Nakon toga ćemo se zadržati na metodi koja nam omogućava da izračunamo GCD brojeva kao proizvod njihovih zajedničkih prostih faktora. Zatim ćemo se pozabaviti pronalaženjem najvećeg zajedničkog djelitelja tri ili više brojeva, a također ćemo dati primjere izračunavanja GCD negativnih brojeva.
Navigacija po stranici.
Euklidov algoritam za pronalaženje GCD
Imajte na umu da da smo se od samog početka okrenuli tabeli prostih brojeva, saznali bismo da su brojevi 661 i 113 prosti, iz čega bismo odmah mogli reći da je njihov najveći zajednički djelitelj 1.
odgovor:
gcd(661, 113)=1.
Pronalaženje GCD-a faktoringom brojeva u proste faktore
Razmotrite drugi način da pronađete GCD. Najveći zajednički djelitelj se može naći rastavljanjem brojeva u proste faktore. Formulirajmo pravilo: gcd dva pozitivna cijela broja a i b jednak je proizvodu svih uobičajenih prostih faktora u faktorizaciji a i b u proste faktore.
Dajemo primjer da objasnimo pravilo za pronalaženje GCD. Upoznajmo proširenja brojeva 220 i 600 u proste faktore, oni imaju oblik 220=2 2 5 11 i 600=2 2 2 3 5 5 . Uobičajeni prosti faktori uključeni u proširenje brojeva 220 i 600 su 2, 2 i 5. Stoga gcd(220, 600)=2 2 5=20 .
Dakle, ako brojeve a i b razložimo na proste činioce i nađemo proizvod svih njihovih zajedničkih faktora, tada ćemo pronaći najveći zajednički djelitelj brojeva a i b.
Razmotrimo primjer pronalaženja GCD-a prema najavljenom pravilu.
Primjer.
Pronađite najveći zajednički djelitelj brojeva 72 i 96.
Odluka.
Razložimo brojeve 72 i 96 na faktore: 
To jest, 72=2 2 2 3 3 i 96=2 2 2 2 2 3 . Uobičajeni prosti faktori su 2, 2, 2 i 3. Dakle, gcd(72, 96)=2 2 2 3=24 .
odgovor:
gcd(72, 96)=24 .
U zaključku ovog odjeljka napominjemo da valjanost gornjeg pravila za pronalaženje gcd proizlazi iz svojstva najvećeg zajedničkog djelitelja, koje glasi da GCD(m a 1, m b 1)=m GCD(a 1, b 1), gdje je m bilo koji pozitivan cijeli broj.
Pronalaženje GCD od tri ili više brojeva
Pronalaženje najvećeg zajedničkog djelitelja tri ili više brojeva može se svesti na sukcesivno 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 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.
Odluka.
U ovom primjeru a 1 =78, a 2 =294, a 3 =570, a 4 =36.
Prvo, koristeći Euklid algoritam, određujemo najveći zajednički djelitelj d 2 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 =GCD(78, 294)=6 .
Sada izračunajmo d 3 \u003d GCD (d 2, a 3) = GCD (6, 570). Ponovo primjenjujemo Euklidov algoritam: 570=6·95 , dakle, d 3 =GCD(6, 570)=6 .
Ostaje izračunati d 4 \u003d GCD (d 3, a 4) \u003d GCD (6, 36). Budući da je 36 djeljivo sa 6, onda je d 4 = GCD (6, 36) = 6.
Dakle, najveći zajednički djelitelj četiri data broja je d 4 =6, odnosno 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.
Odluka.
Brojeve 78 , 294 , 570 i 36 rastavljamo na proste faktore, dobijamo 78=2 3 13 , 294=2 3 7 7 , 570=2 3 5 19 , 36=2 2 3 . Zajednički prosti faktori za sva data četiri broja su brojevi 2 i 3. dakle, GCD(78, 294, 570, 36)=2 3=6.
Hajde da rešimo problem. Imamo dvije vrste kolačića. Neki su čokoladni, a neki obični. Čokolada ima 48 komada, a jednostavnih 36. Od ovih kolačića potrebno je napraviti što veći broj poklona i svi se moraju 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 djeliteljima one zajedničke koje imaju i prvi i drugi broj.
Uobičajeni djelitelji će biti: 1, 2, 3, 4, 6, 12.
Najveći zajednički djelitelj svih je 12. Ovaj broj se zove najveći zajednički djelitelj 36 i 48.
Na osnovu 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 kojim su dva broja a i b djeljiva 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 koprosti 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 ispisati sve djelitelje ovih brojeva.
Možete i drugačije. Prvo, razdijelite oba broja u proste faktore.
- 48 = 2*2*2*2*3,
- 36 = 2*2*3*3.
Sada, iz faktora koji su uključeni u proširenje prvog broja, brišemo 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.
Ostaju faktori 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 i tako dalje. brojevi.
Opća shema za pronalaženje najvećeg zajedničkog djelitelja
- 1. Rastaviti 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.