Najmanje uobičajeni višestruki online kalkulator kolona. Najmanji zajednički višestruki (LCM) – definicija, primjeri i svojstva

Najmanji zajednički višekratnik dva broja direktno je povezan sa najvećim zajedničkim djeliteljem tih brojeva. Ovo veza između GCD i NOC određena je sljedećom teoremom.

Teorema.

Najmanji zajednički višekratnik dva pozitivna cijela broja a i b jednak je umnošku a i b podijeljenom sa najvećim zajedničkim djeliteljem a i b, tj. LCM(a, b)=a b:GCD(a, b).

Dokaz.

Neka M je neki višekratnik brojeva a i b. To jest, M je deljivo sa a, a prema definiciji deljivosti, postoji neki ceo broj k takav da je jednakost M=a·k tačna. Ali M je takođe deljiv sa b, tada je a·k deljiv sa b.

Označimo gcd(a, b) kao d. Tada možemo napisati jednakosti a=a 1 ·d i b=b 1 ·d, a a 1 =a:d i b 1 =b:d će biti relativno prosti brojevi. Prema tome, uslov dobijen u prethodnom paragrafu da je a · k deljivo sa b može se preformulisati na sledeći način: a 1 · d · k je podeljeno sa b 1 · d , a ovo je, zbog svojstava deljivosti, ekvivalentno uslovu da je a 1 · k djeljiv sa b 1 .

Takođe morate da zapišete dve važne posledice iz razmatrane teoreme.

Zajednički višekratnici dva broja isti su kao i višekratnici njihovog najmanjeg zajedničkog višekratnika.

Ovo je zaista slučaj, budući da je svaki zajednički višekratnik M brojeva a i b određen jednakošću M=LMK(a, b)·t za neku cjelobrojnu vrijednost t.

Najmanji zajednički višekratnik međusobno prostih pozitivnih brojeva a i b jednak je njihovom proizvodu.

Obrazloženje ove činjenice je sasvim očigledno. Pošto su a i b relativno prosti, onda je gcd(a, b)=1, dakle, GCD(a, b)=a b: GCD(a, b)=a b:1=a b.

Najmanji zajednički višekratnik tri ili više brojeva

Pronalaženje najmanjeg zajedničkog višekratnika tri ili više brojeva može se svesti na sekvencijalno pronalaženje LCM dva broja. Kako se to radi prikazano je u sljedećoj teoremi: a 1 , a 2 , ..., a k se poklapaju sa zajedničkim višekratnicima brojeva m k-1 i a k ​​, dakle, poklapaju se sa zajedničkim višekratnicima broja m k . A pošto je najmanji pozitivni višekratnik broja m k sam broj m k, onda je najmanji zajednički višekratnik brojeva a 1, a 2, ..., a k m k.

Bibliografija.

• Vilenkin N.Ya. i dr. Matematika. 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.

drugi broj: b=

Hiljadu separator Bez razmaka "´

rezultat:

Najveći zajednički djelitelj gcd( a,b)=6

Najmanji zajednički višekratnik LCM( a,b)=468

Naziva se najveći prirodni broj koji se bez ostatka može podijeliti brojevima a i b najveći zajednički djelitelj(GCD) ovih brojeva. Označava se sa 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 prirodni 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 uzajamno prime, 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 se shvatiti kao cijeli broj.

Neka a 1 ≥ a 2 i neka

Gdje m 1 , a 3 su neki cijeli brojevi, a 3 <a 2 (ostatak od podjele a 1 per a 2 bi trebalo biti manje a 2).

Pretvarajmo se to λ deli a 1 i a 2 onda λ deli m 1 a 2 i λ deli a 1 −m 1 a 2 =a 3 (Navod 2 iz članka „Djeljivost brojeva. Test 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 je također djeljiv sa λ . Stoga 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 zadatka nalaženja zajedničkog djelitelja brojeva a 1 i a 2 sveden na jednostavniji problem nalaženja zajedničkog djelitelja brojeva a 2 i a 3 .

Ako a 3 ≠0, onda možemo podijeliti a 2 per a 3. Onda

,

Gdje m 1 i a 4 su neki cijeli brojevi, ( a 4 ostatak od podjele a 2 per a 3 (a 4 <a 3)). Sličnim rasuđivanjem dolazimo do zaključka da su zajednički djelitelji brojeva a 3 i a 4 se poklapa sa zajedničkim djeliteljima 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, ... su 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 brojeva a n i a n+1 je broj a n+1 , jer a n i a n+1 su djeljivi sa a n+1 (zapamtite to a n+2 =0). Dakle a n+1 je također djelitelj brojeva a 1 i a 2 .

Imajte na umu da je broj a n+1 je najveći djelitelj brojeva a n i a n+1 , od najvećeg djelitelja a n+1 je samo po sebi a n+1 . Ako a n+1 se može predstaviti kao proizvod cijelih brojeva, tada su ovi brojevi također zajednički djelitelji brojeva a 1 i a 2. Broj a n+1 se poziva najveći zajednički djelitelj brojevi a 1 i a 2 .

Brojevi a 1 i a 2 mogu biti pozitivni ili 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 nula brojeva je nedefiniran.

Gornji algoritam se zove Euklidski 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, bez zajedničkog djelitelja.

Teorema 1. Ako a 1 i a 2 međusobno 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 Euklidski 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. To jest a n+1 =1.

Pomnožimo sve ove jednakosti sa λ , Onda

.

Neka je zajednički djelitelj a 1 λ I a 2 da δ . Onda δ je uključen kao množilac u a 1 λ , m 1 a 2 λ i u a 1 λ -m 1 a 2 λ =a 3 λ (vidi "Djeljivost brojeva", izjava 2). Dalje δ je uključen kao množilac u a 2 λ I m 2 a 3 λ , i stoga je faktor u a 2 λ -m 2 a 3 λ =a 4 λ .

Rezonujući na ovaj način, u to smo uvjereni δ je uključen kao množilac 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, dakle δ je uključen kao množilac u λ . Stoga 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 relativno jednostavno, 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. Od uslova odobrenja ak I b imaju zajednički djelitelj b. Na osnovu teoreme 1, b mora biti zajednički djelitelj b I k. Dakle 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 nizu prost u odnosu svakog broja u drugom nizu. Zatim proizvod

Morate pronaći brojeve koji su djeljivi sa svakim od ovih brojeva.

Ako je broj djeljiv sa a 1, tada ima oblik sa 1 gdje s neki broj. Ako q je najveći zajednički djelitelj brojeva a 1 i a 2, onda

Gdje s 1 je neki cijeli broj. Onda

je najmanji zajednički višekratnici brojeva a 1 i a 2 .

a 1 i a 2 su relativno prosti, tada najmanji zajednički višekratnik brojeva a 1 i a 2:

Moramo pronaći 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 nazad. Neka je najmanji zajednički višekratnik brojeva ε I a 3 da ε 1 . Zatim, višestruki brojevi a 1 , a 2 , a 3 , a 4 mora biti višekratnik brojeva ε 1 i a 4 . Neka je najmanji zajednički višekratnik brojeva ε 1 i a 4 da ε 2. Tako smo saznali da su svi višekratnici brojeva a 1 , a 2 , a 3 ,...,a m se poklapaju sa višekratnicima određenog broja ε n, koji se naziva najmanji zajednički višekratnik datih brojeva.

U posebnom slučaju kada su brojevi a 1 , a 2 , a 3 ,...,a m su relativno prosti, tada najmanji zajednički višekratnik brojeva a 1 , a 2, kao što je gore prikazano, ima oblik (3). Sledeće, pošto a 3 prost u odnosu na brojeve a 1 , a 2 onda a 3 prost broj a 1 · a 2 (Korolar 1). Označava najmanji zajednički višekratnik brojeva a 1 ,a 2 ,a 3 je broj a 1 · a 2 · a 3. Rezonujuć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 1 · 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 1 · a 2 · a 3 ··· a m.

Tema „Više brojeva“ se izučava u 5. razredu srednje škole. Njegov cilj je poboljšati pismene i usmene matematičke računske vještine. U ovoj lekciji se uvode novi pojmovi - „višebrojni brojevi“ i „djelitelji“, tehnika pronalaženja djelitelja i višekratnika prirodnog broja, te sposobnost pronalaženja LCM na različite načine.

Ova tema je veoma važna. Znanje o tome može se primijeniti pri rješavanju primjera s razlomcima. Da biste to učinili, morate pronaći zajednički nazivnik izračunavanjem najmanjeg zajedničkog višekratnika (LCM).

Višekratnik A je cijeli broj koji je djeljiv sa A bez ostatka.

Svaki prirodan broj ima beskonačan broj višekratnika. Sama se smatra najmanjom. Višekratnik ne može biti manji od samog broja.

Morate dokazati da je broj 125 višestruki od 5. Da biste to učinili, trebate podijeliti prvi broj sa drugim. Ako je 125 djeljivo sa 5 bez ostatka, onda je odgovor potvrdan.

Ova metoda je primjenjiva za male brojeve.

Postoje posebni slučajevi kada se izračunava LOC.

1. Ako trebate pronaći zajednički višekratnik 2 broja (na primjer, 80 i 20), gdje je jedan od njih (80) djeljiv s drugim (20), tada je ovaj broj (80) najmanji višekratnik ovih dva broja.

LCM(80, 20) = 80.

2. Ako dva nemaju zajednički djelitelj, onda možemo reći da je njihov LCM proizvod ova dva broja.

LCM(6, 7) = 42.

Pogledajmo posljednji primjer. 6 i 7 u odnosu na 42 su djelitelji. Oni dijele višekratnik broja bez ostatka.

U ovom primjeru, 6 i 7 su upareni faktori. Njihov proizvod je jednak najvišem broju (42).

Broj se naziva prostim ako je djeljiv samo sa sobom ili sa 1 (3:1=3; 3:3=1). Ostalo se naziva kompozitnim.

Drugi primjer uključuje određivanje da li je 9 djelitelj broja 42.

42:9=4 (ostatak 6)

Odgovor: 9 nije djelitelj broja 42 jer odgovor ima ostatak.

Delitelj se razlikuje od višekratnika po tome što je djelitelj broj kojim se dijele prirodni brojevi, a sam višekratnik je djeljiv ovim brojem.

Najveći zajednički djelitelj brojeva a I b, pomnoženo njihovim najmanjim višekratnikom, dat će proizvod samih brojeva a I b.

Naime: gcd (a, b) x gcd (a, b) = a x b.

Uobičajeni višekratnici za složenije brojeve nalaze se na sljedeći način.

Na primjer, pronađite LCM za 168, 180, 3024.

Ove brojeve rastavljamo u jednostavne faktore i zapisujemo ih kao proizvod potencija:

168=2³x3¹x7¹

2⁴h3³h5¹h7¹=15120

LCM(168, 180, 3024) = 15120.

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

Moramo pronaći svaki faktor svakog od dva broja za koji nalazimo najmanji zajednički višekratnik, a zatim pomnožiti jedan s drugim faktore koji se poklapaju u prvom i drugom broju. Rezultat proizvoda će biti traženi višestruki.

Na primjer, imamo brojeve 3 i 5 i moramo pronaći LCM (najmanji zajednički višekratnik). Nas treba umnožiti i tri i pet za sve brojeve počevši od 1 2 3 ... i tako sve dok ne vidimo isti broj na oba mjesta.

Pomnožite tri i dobijete: 3, 6, 9, 12, 15

Pomnožite sa pet i dobijete: 5, 10, 15

Metoda faktorizacije prostih brojeva je najklasičnija metoda za pronalaženje najmanjeg zajedničkog višekratnika (LCM) nekoliko brojeva. Ova metoda je jasno i jednostavno prikazana u sljedećem videu:

Sabiranje, množenje, dijeljenje, svođenje na zajednički nazivnik i druge aritmetičke operacije su vrlo uzbudljive aktivnosti; posebno su fascinantni primjeri koji zauzimaju cijeli list papira.

Dakle, pronađite zajednički višekratnik dva broja, koji će biti najmanji broj sa kojim su dva broja podijeljena. Napominjem da u budućnosti nije potrebno pribjegavati formulama da biste pronašli ono što tražite, ako možete računati u glavi (a to se može istrenirati), onda vam u glavi iskaču sami brojevi i tada razlomci pucaju kao orasi.

Za početak, naučimo da možete pomnožiti dva broja jedan s drugim, a zatim smanjiti ovu brojku i podijeliti naizmjenično sa ova dva broja, tako da ćemo pronaći najmanji višekratnik.

Na primjer, dva broja 15 i 6. Pomnožite i dobijete 90. Ovo je očito veći broj. Štaviše, 15 je deljivo sa 3, a 6 je deljivo sa 3, što znači da takođe delimo 90 sa 3. Dobijamo 30. Pokušavamo da 30 podelimo 15 jednako je 2. A 30 podelimo 6 je jednako 5. Pošto je 2 granica, pretvara se da je najmanji višekratnik za brojeve 15, a 6 će biti 30.

Sa većim brojevima to će biti malo teže. ali ako znate koji brojevi daju nulti ostatak pri dijeljenju ili množenju, onda, u principu, nema velikih poteškoća.

• Kako pronaći NOC

  Evo videa koji će vam dati dva načina da pronađete najmanji zajednički višekratnik (LCM). Nakon što uvježbate korištenje prve od predloženih metoda, možete bolje razumjeti koji je najmanji zajednički višekratnik.

Predstavljam još jedan način za pronalaženje najmanjeg zajedničkog višekratnika. Pogledajmo to sa jasnim primjerom.

Morate pronaći LCM od tri broja odjednom: 16, 20 i 28.

• Svaki broj predstavljamo kao proizvod njegovih prostih faktora:
• Zapisujemo snage svih primarnih faktora:

16 = 224 = 2^24^1

20 = 225 = 2^25^1

28 = 227 = 2^27^1

• Odaberemo sve proste djelitelje (množitelje) s najvećim potencijama, pomnožimo ih i pronađemo LCM:

LCM = 2^24^15^17^1 = 4457 = 560.

LCM(16, 20, 28) = 560.

Tako je rezultat izračuna bio broj 560. To je najmanji zajednički višekratnik, odnosno djeljiv je sa svakim od tri broja bez ostatka.

Najmanji zajednički višekratnik je broj koji se može podijeliti na nekoliko datih brojeva bez ostavljanja ostatka. Da biste izračunali takvu cifru, morate uzeti svaki broj i razložiti ga na jednostavne faktore. Oni brojevi koji se podudaraju se uklanjaju. Ostavlja sve jednog po jednog, pomnožite ih redom i dobijete željeni - najmanji zajednički višekratnik.

NOC, ili najmanji zajednički višekratnik, je najmanji prirodan broj od dva ili više brojeva koji je djeljiv sa svakim od datih brojeva bez ostatka.

Evo primjera kako pronaći najmanji zajednički višekratnik 30 i 42.

• Prvi korak je rastavljanje ovih brojeva u proste faktore.

Za 30 je 2 x 3 x 5.

Za 42, ovo je 2 x 3 x 7. Pošto su 2 i 3 u proširenju broja 30, precrtavamo ih.

• Zapisujemo faktore koji su uključeni u proširenje broja 30. To je 2 x 3 x 5.
• Sada ih trebamo pomnožiti sa faktorom koji nedostaje, koji imamo kada proširimo 42, a to je 7. Dobijamo 2 x 3 x 5 x 7.
• Nalazimo koliko je jednako 2 x 3 x 5 x 7 i dobijamo 210.

Kao rezultat, nalazimo da je LCM brojeva 30 i 42 210.

Da pronađemo najmanji zajednički višekratnik, morate izvršiti nekoliko jednostavnih koraka u nizu. Pogledajmo ovo koristeći dva broja kao primjer: 8 i 12

1. Oba broja činimo u proste faktore: 8=2*2*2 i 12=3*2*2
2. Smanjujemo iste faktore jednog od brojeva. U našem slučaju, 2 * 2 se poklapaju, smanjimo ih za broj 12, tada će za 12 ostati jedan faktor: 3.
3. Pronađite proizvod svih preostalih faktora: 2*2*2*3=24

Provjeravajući, uvjeravamo se da je 24 djeljivo i sa 8 i sa 12, a ovo je najmanji prirodan broj koji je djeljiv sa svakim od ovih brojeva. Tu smo pronađen najmanji zajednički višekratnik.

Pokušat ću objasniti koristeći kao primjer brojeve 6 i 8. Najmanji zajednički višekratnik je broj koji se može podijeliti ovim brojevima (u našem slučaju 6 i 8) i neće biti ostatka.

Dakle, prvo počinjemo da množimo 6 sa 1, 2, 3, itd. i 8 sa 1, 2, 3, itd.

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 nam omogućava 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) . Pogledajmo primjere pronalaženja LCM-a pomoću date formule.

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 LCM(68, 34) jednako?

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 nađemo 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. To jest, 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.