Pronalaženje zajedničkog višekratnika dva broja. Načini pronalaženja najmanjeg zajedničkog višekratnika, nok is i sva objašnjenja
drugi broj: b=
Razdjelnik cifara Nema razmaka " ´
rezultat:
najveći zajednički djelitelj GCD( a,b)=6
Najmanji zajednički višekratnik LCM( a,b)=468
Greatest prirodni broj, kojim su brojevi a i b djeljivi bez ostatka, naziva se najveći zajednički djelitelj(gcd) ovih brojeva. Označava se gcd(a,b), (a,b), gcd(a,b) ili hcf(a,b).
Najmanji zajednički višekratnik(LCM) od dva cijela broja a i b je najmanji prirodan broj koji je djeljiv sa a i b bez ostatka. Označava se LCM(a,b) ili lcm(a,b).
Pozivaju se cijeli brojevi a i b coprime ako nemaju zajedničke djelitelje osim +1 i −1.
Najveći zajednički djelitelj
Neka su data dva pozitivna broja a 1 i a 2 1). Potrebno je pronaći zajednički djelitelj ovih brojeva, tj. pronađite takav broj λ , koji dijeli brojeve a 1 i a 2 u isto vreme. Hajde da opišemo algoritam.
1) U ovom članku, riječ broj će značiti cijeli broj.
Neka a 1 ≥ a 2 i neka
gdje m 1 , a 3 su neki cijeli brojevi, a 3 <a 2 (ostatak iz divizije a 1 on a 2 bi trebalo biti manje a 2).
Pretvarajmo se to λ deli a 1 i a 2, dakle λ deli m 1 a 2 i λ deli a 1 −m 1 a 2 =a 3 (Tvrdnja 2 članka "Djeljivost brojeva. Znak djeljivosti"). Iz toga slijedi da je svaki zajednički djelitelj a 1 i a 2 je zajednički djelitelj a 2 i a 3 . I obrnuto je tačno ako λ zajednički djelitelj a 2 i a 3 , onda m 1 a 2 i a 1 =m 1 a 2 +a 3 se također dijele na λ . Otuda zajednički djelitelj a 2 i a 3 je također zajednički djelitelj a 1 i a 2. Jer a 3 <a 2 ≤a 1 , onda možemo reći da je rješenje problema nalaženja zajedničkog djelitelja brojeva a 1 i a 2 sveden na jednostavniji problem pronalaženja zajedničkog djelitelja brojeva a 2 i a 3 .
Ako a a 3 ≠0, onda možemo podijeliti a 2 on a 3 . Onda
,
gdje m 1 i a 4 su neki cijeli brojevi, ( a 4 ostatak podjele a 2 on a 3 (a 4 <a 3)). Sličnim razmišljanjem dolazimo do zaključka da su zajednički djelitelji brojeva a 3 i a 4 je isto što i zajednički djelitelj brojeva a 2 i a 3 , kao i sa zajedničkim djeliteljima a 1 i a 2. Jer a 1 , a 2 , a 3 , a 4 , ... brojevi koji se stalno smanjuju, a budući da postoji konačan broj cijelih brojeva između a 2 i 0, zatim u nekom koraku n, ostatak divizije a n uključeno a n+1 će biti jednako nuli ( a n+2=0).
.
Svaki zajednički djelitelj λ brojevi a 1 i a 2 je također djelitelj brojeva a 2 i a 3 , a 3 i a 4 , .... a n i a n+1 . Vrijedi i obrnuto, zajednički djelitelji brojeva a n i a n+1 su također djelitelji brojeva a n−1 i a n , .... , a 2 i a 3 , a 1 i a 2. Ali zajednički djelitelj a n i a n+1 je broj a n+1 , jer a n i a n+1 su djeljivi sa a n+1 (podsjetite se toga a n+2=0). Shodno tome a n+1 je također djelitelj brojeva a 1 i a 2 .
Imajte na umu da broj a n+1 je najveći djelitelj broja a n i a n+1 , od najvećeg djelitelja a n+1 je sam po sebi a n+1 . Ako a a n + 1 se može predstaviti kao proizvod cijelih brojeva, tada su ovi brojevi također uobičajeni djelitelji brojeva a 1 i a 2. Broj a n+1 se pozivaju najveći zajednički djelitelj brojevi a 1 i a 2 .
Brojevi a 1 i a 2 mogu biti i pozitivni i negativni brojevi. Ako je jedan od brojeva jednak nuli, tada će najveći zajednički djelitelj ovih brojeva biti jednak apsolutnoj vrijednosti drugog broja. Najveći zajednički djelitelj brojeva nula nije definiran.
Gornji algoritam se zove Euklidov algoritam pronaći najveći zajednički djelitelj dva cijela broja.
Primjer pronalaženja najvećeg zajedničkog djelitelja dva broja
Pronađite najveći zajednički djelitelj dva broja 630 i 434.
- Korak 1. Podijelite broj 630 sa 434. Ostatak je 196.
- Korak 2. Podijelite broj 434 sa 196. Ostatak je 42.
- Korak 3. Podijelite broj 196 sa 42. Ostatak je 28.
- Korak 4. Podijelite broj 42 sa 28. Ostatak je 14.
- Korak 5. Podijelite broj 28 sa 14. Ostatak je 0.
U koraku 5, ostatak dijeljenja je 0. Stoga je najveći zajednički djelitelj brojeva 630 i 434 14. Imajte na umu da su brojevi 2 i 7 također djelitelji brojeva 630 i 434.
Koprosti brojevi
Definicija 1. Neka je najveći zajednički djelitelj brojeva a 1 i a 2 je jednako jedan. Tada se ovi brojevi pozivaju koprosti brojevi koji nemaju zajednički djelitelj.
Teorema 1. Ako a a 1 i a 2 relativno prosta broja, i λ neki broj, zatim bilo koji zajednički djelitelj brojeva λa 1 i a 2 je također zajednički djelitelj brojeva λ i a 2 .
Dokaz. Razmotrimo Euklidov algoritam za pronalaženje najvećeg zajedničkog djelitelja brojeva a 1 i a 2 (vidi gore).
.
Iz uslova teoreme slijedi da je najveći zajednički djelitelj brojeva a 1 i a 2 , i stoga a n i a n+1 je 1. tj. a n+1=1.
Pomnožimo sve ove jednakosti sa λ , onda
.
Neka je zajednički djelitelj a 1 λ i a 2 je δ . Onda δ ulazi kao faktor u a 1 λ , m 1 a 2 λ i u a 1 λ -m 1 a 2 λ =a 3 λ (Vidi "Djeljivost brojeva", izjava 2). Dalje δ ulazi kao faktor u a 2 λ i m 2 a 3 λ , pa stoga ulazi kao faktor u a 2 λ -m 2 a 3 λ =a 4 λ .
Ovakvim rasuđivanjem u to smo uvjereni δ ulazi kao faktor u a n−1 λ i m n−1 a n λ , a samim tim i u a n−1 λ −m n−1 a n λ =a n+1 λ . Jer a n+1 =1, onda δ ulazi kao faktor u λ . Otuda broj δ je zajednički djelitelj brojeva λ i a 2 .
Razmotrimo posebne slučajeve teoreme 1.
Posljedica 1. Neka a i c prosti brojevi su relativno b. Zatim njihov proizvod ac je prost broj u odnosu na b.
Zaista. Iz teoreme 1 ac i b imaju iste zajedničke djelitelje kao c i b. Ali brojevi c i b coprime, tj. imaju jedan zajednički djelitelj 1. Tada ac i b također imaju jedan zajednički djelitelj 1. Dakle ac i b obostrano jednostavno.
Posljedica 2. Neka a i b koprosti brojevi i neka b deli ak. Onda b deli i k.
Zaista. Iz uslova tvrdnje ak i b imaju zajednički djelitelj b. Na osnovu teoreme 1, b mora biti zajednički djelitelj b i k. Shodno tome b deli k.
Korolar 1 se može generalizovati.
Posljedica 3. 1. Neka brojevi a 1 , a 2 , a 3 , ..., a m su prosti u odnosu na broj b. Onda a 1 a 2 , a 1 a 2 · a 3 , ..., a 1 a 2 a 3 ··· a m , proizvod ovih brojeva je prost u odnosu na broj b.
2. Neka imamo dva reda brojeva
tako da je svaki broj u prvom redu prost u odnosu na svaki broj u drugom redu. Zatim proizvod
Potrebno je pronaći takve brojeve koji su djeljivi sa svakim od ovih brojeva.
Ako je broj djeljiv sa a 1 , onda izgleda sa 1, gdje s neki broj. Ako a q je najveći zajednički djelitelj brojeva a 1 i a 2, dakle
gdje s 1 je neki cijeli broj. Onda
je najmanji zajednički umnožak brojeva a 1 i a 2 .
a 1 i a 2 zajedno prost, zatim najmanji zajednički višekratnik brojeva a 1 i a 2:
Pronađite najmanji zajednički višekratnik ovih brojeva.
Iz navedenog slijedi da je bilo koji višekratnik brojeva a 1 , a 2 , a 3 mora biti višekratnik brojeva ε i a 3 i obrnuto. Neka je najmanji zajednički višekratnik brojeva ε i a 3 je ε jedan . Nadalje, višestruki brojevi a 1 , a 2 , a 3 , a 4 mora biti višekratnik brojeva ε 1 i ačetiri . Neka je najmanji zajednički višekratnik brojeva ε 1 i a 4 je ε 2. Tako smo saznali da su svi višekratnici brojeva a 1 , a 2 , a 3 ,...,a m se poklapaju sa višekratnicima nekog određenog broja ε n , koji se naziva najmanji zajednički višekratnik datih brojeva.
U konkretnom slučaju kada su brojevi a 1 , a 2 , a 3 ,...,a m koprost, tada najmanji zajednički višekratnik brojeva a 1 , a 2 kao što je gore prikazano ima oblik (3). Dalje, pošto a 3 prosti u odnosu na brojeve a 1 , a 2, dakle a 3 je prost relativni broj a jedan · a 2 (Korolar 1). Dakle, najmanji zajednički višekratnik brojeva a 1 ,a 2 ,a 3 je broj a jedan · a 2 · a 3 . Argumentirajući na sličan način, dolazimo do sljedećih tvrdnji.
Izjava 1. Najmanji zajednički višekratnik međusobno prostih brojeva a 1 , a 2 , a 3 ,...,a m je jednako njihovom proizvodu a jedan · a 2 · a 3 ··· a m .
Izjava 2. Bilo koji broj koji je djeljiv sa svakim koprostim brojevima a 1 , a 2 , a 3 ,...,a m je također djeljiv njihovim umnoškom a jedan · a 2 · a 3 ··· a m .
Definicija. Naziva se najveći prirodni broj kojim su brojevi a i b djeljivi bez ostatka najveći zajednički djelitelj (gcd) ovi brojevi.
Nađimo najveći zajednički djelitelj brojeva 24 i 35.
Delitelji 24 će biti brojevi 1, 2, 3, 4, 6, 8, 12, 24, a djelitelji 35 će biti brojevi 1, 5, 7, 35.
Vidimo da brojevi 24 i 35 imaju samo jedan zajednički djelitelj - broj 1. Takvi brojevi se nazivaju coprime.
Definicija. Prirodni brojevi se nazivaju coprime ako je njihov najveći zajednički djelitelj (gcd) 1.
Najveći zajednički djelitelj (GCD) može se naći bez ispisivanja svih djelitelja datih brojeva.
Rastavljajući na faktore brojeve 48 i 36, dobijamo:
48 = 2 * 2 * 2 * 2 * 3, 36 = 2 * 2 * 3 * 3.
Iz faktora uključenih u proširenje prvog od ovih brojeva brišemo one koji nisu uključeni u proširenje drugog broja (tj. dvije dvojke).
Ostaju faktori 2 * 2 * 3. Njihov proizvod je 12. Ovaj broj je najveći zajednički djelitelj brojeva 48 i 36. Pronađen je i najveći zajednički djelitelj tri ili više brojeva.
Naći najveći zajednički djelitelj
2) iz faktora uključenih u proširenje jednog od ovih brojeva precrtati one koji nisu uključeni u proširenje drugih brojeva;
3) naći proizvod preostalih faktora.
Ako su svi dati brojevi djeljivi sa jednim od njih, onda je i ovaj broj najveći zajednički djelitelj date brojeve.
Na primjer, najveći zajednički djelitelj 15, 45, 75 i 180 je 15, jer dijeli sve ostale brojeve: 45, 75 i 180.
Najmanji zajednički višekratnik (LCM)
Definicija. Najmanji zajednički višekratnik (LCM) prirodni brojevi a i b su najmanji prirodni broj koji je višekratnik i a i b. Najmanji zajednički višekratnik (LCM) brojeva 75 i 60 može se pronaći bez pisanja višekratnika ovih brojeva u nizu. Da bismo to učinili, razlažemo 75 i 60 na jednostavne faktore: 75 = 3 * 5 * 5 i 60 = 2 * 2 * 3 * 5.
Zapisujemo faktore uključene u proširenje prvog od ovih brojeva i dodajemo im faktore koji nedostaju 2 i 2 iz proširenja drugog broja (tj. kombinujemo faktore).
Dobijamo pet faktora 2 * 2 * 3 * 5 * 5, čiji je proizvod 300. Ovaj broj je najmanji zajednički višekratnik brojeva 75 i 60.
Također pronađite najmanji zajednički višekratnik tri ili više brojeva.
To pronađite najmanji zajednički višekratnik nekoliko prirodnih brojeva, potrebno je:
1) razložiti ih na proste faktore;
2) ispisati faktore uključene u proširenje jednog od brojeva;
3) dodati im faktore koji nedostaju iz proširenja preostalih brojeva;
4) naći proizvod rezultujućih faktora.
Imajte na umu da ako je jedan od ovih brojeva djeljiv sa svim ostalim brojevima, onda je ovaj broj najmanji zajednički višekratnik ovih brojeva.
Na primjer, najmanji zajednički višekratnik od 12, 15, 20 i 60 bi bio 60, jer je djeljiv sa svim datim brojevima.
Pitagora (VI vek pne) i njegovi učenici proučavali su pitanje deljivosti brojeva. Broj jednak zbroju svih njegovih djelitelja (bez samog broja), nazvali su savršenim brojem. Na primjer, brojevi 6 (6 = 1 + 2 + 3), 28 (28 = 1 + 2 + 4 + 7 + 14) su savršeni. Sljedeći savršeni brojevi su 496, 8128, 33 550 336. Pitagorejci su poznavali samo prva tri savršena broja. Četvrti - 8128 - postao je poznat u 1. vijeku. n. e. Peti - 33 550 336 - pronađen je u 15. vijeku. Do 1983. već je bilo poznato 27 savršenih brojeva. Ali do sada naučnici ne znaju da li postoje neparni savršeni brojevi, da li postoji najveći savršeni broj.
Interes starih matematičara za proste brojeve je zbog činjenice da je bilo koji broj ili prost ili se može predstaviti kao proizvod prostih brojeva, odnosno prosti brojevi su poput cigli od kojih su izgrađeni ostali prirodni brojevi.
Vjerovatno ste primijetili da se prosti brojevi u nizu prirodnih brojeva javljaju neravnomjerno - u nekim dijelovima niza ih ima više, u drugim - manje. Ali što se dalje krećemo duž niza brojeva, prosti brojevi su rjeđi. Postavlja se pitanje: postoji li posljednji (najveći) prost broj? Drevni grčki matematičar Euklid (3. vek pre nove ere), u svojoj knjizi „Počeci“, koja je dve hiljade godina bila glavni udžbenik matematike, dokazao je da postoji beskonačno mnogo prostih brojeva, odnosno da iza svakog prostog broja postoji paran broj. veći prost broj.
Za pronalaženje prostih brojeva, drugi grčki matematičar iz istog vremena, Eratosten, smislio je takvu metodu. Zapisao je sve brojeve od 1 do nekog broja, a zatim precrtao jedinicu, koja nije ni prost ni složeni broj, zatim kroz jedan precrtao sve brojeve nakon 2 (brojeve koji su višestruki od 2, tj. 4, 6, 8, itd.). Prvi preostali broj nakon 2 bio je 3. Zatim, nakon dva, svi brojevi iza 3 su precrtani (brojevi koji su višestruki od 3, tj. 6, 9, 12, itd.). na kraju su ostali neprecrtani samo prosti brojevi.
Uobičajeni višestruki
Jednostavno rečeno, svaki cijeli broj koji je djeljiv sa svakim od datih brojeva jeste zajednički višestruki dati cijeli brojevi.
Možete pronaći zajednički višekratnik dva ili više cijelih brojeva.
Primjer 1
Izračunajte zajednički višekratnik dva broja: $2$ i $5$.
Rješenje.
Po definiciji, zajednički višekratnik $2$ i $5$ je $10$, jer to je višekratnik od $2$ i $5$:
Uobičajeni višekratnici brojeva $2$ i $5$ takođe će biti brojevi $–10, 20, –20, 30, –30$, itd., jer svi su djeljivi sa $2$ i $5$.
Napomena 1
Nula je zajednički višekratnik bilo kojeg broja cijelih brojeva koji nisu nula.
Prema svojstvima djeljivosti, ako je određeni broj zajednički višekratnik više brojeva, tada će i broj suprotan po predznaku biti zajednički višekratnik datih brojeva. To se može vidjeti iz razmatranog primjera.
Za date cijele brojeve uvijek možete pronaći njihov zajednički višekratnik.
Primjer 2
Izračunajte zajednički višekratnik $111$ i $55$.
Rješenje.
Pomnožite date brojeve: $111\div 55=6105$. Lako je provjeriti da je broj $6105$ djeljiv brojem $111$ i brojem $55$:
$6105\div 111=55$;
$6105\div 55=111$.
Dakle, $6105$ je zajednički višekratnik $111$ i $55$.
Odgovori: zajednički višekratnik od 111$ i 55$ je 6105$.
Ali, kao što smo već vidjeli iz prethodnog primjera, ovaj zajednički višekratnik nije jedan. Drugi uobičajeni višekratnici bi bili $-6105, 12210, -12210, 61050, -61050 $, i tako dalje. Dakle, došli smo do sljedećeg zaključka:
Napomena 2
Svaki skup cijelih brojeva ima beskonačan broj zajedničkih višekratnika.
U praksi su ograničeni na pronalaženje zajedničkih višekratnika samo pozitivnih cijelih (prirodnih) brojeva, jer skupovi višekratnika datog broja i njegove suprotnosti se poklapaju.
Pronalaženje najmanjeg zajedničkog višekratnika
Najčešće, od svih višekratnika datog broja, koristi se najmanji zajednički višekratnik (LCM).
Definicija 2
Najmanji pozitivni zajednički višekratnik datih cijelih brojeva je najmanji zajednički višekratnik ovi brojevi.
Primjer 3
Izračunajte LCM brojeva $4$ i $7$.
Rješenje.
Jer ovi brojevi nemaju zajedničke djelitelje, tada je $LCM(4,7)=28$.
Odgovori: $LCM(4,7)=28$.
Pronalaženje NOC-a kroz NOD
Jer postoji veza između LCM-a i GCD-a, uz njegovu pomoć moguće je izračunati LCM od dva pozitivna cijela broja:
Napomena 3
Primjer 4
Izračunajte LCM brojeva $232$ i $84$.
Rješenje.
Koristimo formulu za pronalaženje LCM-a kroz GCD:
$LCD (a,b)=\frac(a\cdot b)(gcd (a,b))$
Nađimo gcd brojeva $232$ i $84$ pomoću Euklidovog algoritma:
$232=84\cdot 2+64$,
$84=64\cdot 1+20$,
$64=20\cdot 3+4$,
One. $gcd (232, 84)=4$.
Nađimo $LCM (232, 84)$:
$LCC(232,84)=\frac(232\cdot 84)(4)=58\cdot 84=4872$
Odgovori: $NOK(232.84)=4872$.
Primjer 5
Izračunajte $LCM (23, 46)$.
Rješenje.
Jer $46$ je jednako djeljivo sa $23$, tada je $gcd(23, 46)=23$. Pronađimo NOC:
$LCC(23,46)=\frac(23\cdot 46)(23)=46$
Odgovori: $NOK(23,46)=46$.
Dakle, može se formulisati pravilo:
Napomena 4
Materijal predstavljen u nastavku je logičan nastavak teorije iz članka pod naslovom LCM - najmanji zajednički višekratnik, definicija, primjeri, odnos između LCM i GCD. Ovdje ćemo razgovarati o pronalaženje najmanjeg zajedničkog višekratnika (LCM), a posebnu pažnju posvetite rješavanju primjera. Hajde da prvo pokažemo kako se LCM dva broja izračunava u terminima GCD ovih brojeva. Zatim, razmotrite 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) kroz gcd
Jedan od načina da se pronađe najmanji zajednički višekratnik je zasnovan na odnosu između LCM i GCD. Postojeći odnos između LCM i GCD vam omogućava da izračunate najmanji zajednički višekratnik dva pozitivna cijela broja kroz poznati najveći zajednički djelitelj. Odgovarajuća formula ima oblik LCM(a, b)=a b: GCD(a, b) . Razmotrimo primjere pronalaženja LCM-a prema gornjoj formuli.
Primjer.
Pronađite najmanji zajednički višekratnik dva broja 126 i 70.
Rješenje.
U ovom primjeru a=126, b=70. Koristimo odnos između LCM i GCD izražen 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 prema napisanoj formuli.
Pronađite 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: LCM(126, 70)=126 70: GCM(126, 70)= 126 70:14=630 .
odgovor:
LCM(126, 70)=630 .
Primjer.
Šta je LCM(68, 34) ?
Rješenje.
Jer 68 je jednako djeljivo sa 34, tada je gcd(68, 34)=34. Sada izračunavamo najmanji zajednički višekratnik: LCM(68, 34)=68 34: LCM(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 razlaganjem brojeva u proste faktore
Drugi način za pronalaženje najmanjeg zajedničkog višekratnika je baziran na faktoringu brojeva u proste faktore. Ako napravimo proizvod svih prostih faktora ovih brojeva, nakon čega iz ovog proizvoda isključimo sve zajedničke proste faktore koji su prisutni u proširenjima ovih brojeva, onda će rezultirajući proizvod biti jednak najmanjem zajedničkom višekratniku ovih brojeva.
Najavljeno 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širenja 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 (što je opisano u odjeljku o pronalaženju gcd pomoću dekompozicije brojeva na proste faktore ).
Uzmimo primjer. Neka znamo da je 75=3 5 5 i 210=2 3 5 7 . Sastavite proizvod svih faktora ovih proširenja: 2 3 3 5 5 5 7 . Sada iz ovog proizvoda izuzimamo sve faktore koji su prisutni i u proširenju broja 75 i u proširenju broja 210 (takvi 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 brojeva 75 i 210, tj. LCM(75, 210)= 2 3 5 5 7=1 050.
Primjer.
Nakon faktoringa brojeva 441 i 700 u proste faktore, pronađite najmanji zajednički višekratnik ovih brojeva.
Rješenje.
Razložimo brojeve 441 i 700 na proste faktore:
Dobijamo 441=3 3 7 7 i 700=2 2 5 5 7 .
Sada napravimo proizvod svih faktora koji su uključeni u proširenja 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 . Na ovaj način, LCM(441, 700)=2 2 3 3 5 5 7 7=44 100.
odgovor:
LCM(441, 700)= 44 100 .
Pravilo za pronalaženje LCM pomoću dekompozicije brojeva na proste faktore može se formulisati malo drugačije. Ako faktorima koji nedostaju iz proširenja broja b dodamo faktore 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 sve iste brojeve 75 i 210, njihova proširenja u proste faktore su sljedeća: 75=3 5 5 i 210=2 3 5 7 . Faktorima 3, 5 i 5 iz dekompozicije broja 75 dodamo faktore koji nedostaju 2 i 7 iz dekompozicije broja 210, dobijemo proizvod 2 3 5 5 7 , čija je vrijednost LCM(75 , 210) .
Primjer.
Pronađite najmanji zajednički višekratnik brojeva 84 i 648.
Rješenje.
Prvo dobijamo dekompoziciju 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 dekompozicije broja 84 dodamo faktore koji nedostaju 2, 3, 3 i 3 iz dekompozicije broja 648, dobijemo proizvod 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 od tri ili više brojeva
Najmanji zajednički višekratnik tri ili više brojeva može se naći sukcesivnim pronalaženjem LCM dva broja. Prisjetite 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 u sekvencijalnom proračunu 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 nađemo m 2 = LCM (a 1, a 2) \u003d LCM (140, 9). Da bismo to učinili, koristeći Euklidov algoritam, određujemo 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 LCM(140, 9)=140 9: LCM(140, 9)= 140 9:1=1 260 . Odnosno, m 2 =1 260 .
Sada pronalazimo m 3 = LCM (m 2, a 3) = LCM (1 260, 54). Izračunajmo ga kroz gcd(1 260, 54) , što je također određeno Euklidovim algoritmom: 1 260=54 23+18 , 54=18 3 . Tada je gcd(1 260, 54)=18, odakle je LCM(1 260, 54)= 1 260 54:gcd(1 260, 54)= 1 260 54:18=3 780 . To jest, m 3 = 3 780.
Ostalo da se pronađe m 4 = LCM (m 3, a 4) = LCM (3 780, 250). Da bismo to učinili, nalazimo GCD(3 780, 250) koristeći Euklid algoritam: 3 780=250 15+30 , 250=30 8+10 , 30=10 3 . Prema tome, gcd(3 780, 250)=10 , odakle je gcd(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, najmanji zajednički umnožak tri ili više brojeva prikladno se nalazi korištenjem prostih faktorizacija datih brojeva. U ovom slučaju treba 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 dobijenim faktorima i tako dalje.
Razmotrimo primjer pronalaženja najmanjeg zajedničkog višekratnika koristeći dekompoziciju brojeva na proste faktore.
Primjer.
Pronađite najmanji zajednički višekratnik pet brojeva 84 , 6 , 48 , 7 , 143 .
Rješenje.
Prvo dobijamo proširenja ovih brojeva u proste faktore: 84=2 2 3 7 , 6=2 3 , 48=2 2 2 2 3 , 7 prosti faktori) 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. Proširivanje broja 6 ne sadrži faktore koji nedostaju, jer su i 2 i 3 već prisutni u proširenju prvog broja 84 . Pored faktora 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. Nema potrebe dodavati faktore 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 , koji je jednak 48 048 .
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$.
Rješenje:
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$ je prirodan 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 višekratnik i označavati ga 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$, tada 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)$