Iskanje skupnega večkratnika dveh števil. Načini iskanja najmanjšega skupnega večkratnika, nok is in vse razlage
Druga številka: b=
Ločilo številk Brez ločila presledkov " ´
rezultat:
največji skupni delilnik GCD( a,b)=6
Najmanjši skupni večkratnik LCM( a,b)=468
Največji naravno število, s katerim sta števili a in b deljivi brez ostanka, imenujemo največji skupni delitelj(gcd) teh številk. Označeno z gcd(a,b), (a,b), gcd(a,b) ali hcf(a,b).
Najmanjši skupni večkratnik(LCM) dveh celih števil a in b je najmanjše naravno število, ki je deljivo z a in b brez ostanka. Označeno z LCM(a,b) ali lcm(a,b).
Celi števili a in b se imenujeta coprimeče nimata skupnih deliteljev, razen +1 in −1.
Največji skupni delitelj
Naj sta podani dve pozitivni števili a 1 in a 2 1). Najti je treba skupni delitelj teh števil, tj. najti tako številko λ , ki deli števila a 1 in a 2 hkrati. Opišimo algoritem.
1) V tem članku bo beseda številka pomenila celo število.
Pustiti a 1 ≥ a 2 in pustite
kje m 1 , a 3 je nekaj celih števil, a 3 <a 2 (ostanek od delitve a 1 na a 2 mora biti manj a 2).
Pretvarjajmo se, da λ deli a 1 in a 2, torej λ deli m 1 a 2 in λ deli a 1 −m 1 a 2 =a 3 (2. trditev članka »Deljivost števil. Znak deljivosti«). Iz tega sledi, da vsak skupni delitelj a 1 in a 2 je skupni delitelj a 2 in a 3. Tudi obratno velja, če λ skupni delilnik a 2 in a 3, torej m 1 a 2 in a 1 =m 1 a 2 +a 3 se delijo tudi na λ . Od tod skupni delilnik a 2 in a 3 je tudi skupni delitelj a 1 in a 2. Ker a 3 <a 2 ≤a 1 , potem lahko rečemo, da je rešitev problema iskanja skupnega delitelja števil a 1 in a 2 zmanjšana na preprostejši problem iskanja skupnega delitelja števil a 2 in a 3 .
Če a 3 ≠0, potem lahko delimo a 2 naprej a 3. Potem
,
kje m 1 in a 4 je nekaj celih števil, ( a 4 ostanek deljenja a 2 naprej a 3 (a 4 <a 3)). S podobnim razmišljanjem pridemo do zaključka, da so skupni delitelji števil a 3 in a 4 je enak navadnim deliteljem števil a 2 in a 3 , in tudi s skupnimi delilniki a 1 in a 2. Ker a 1 , a 2 , a 3 , a 4 , ... števila, ki nenehno padajo, in ker je med njimi končno število celih števil a 2 in 0, nato na nekem koraku n, ostanek delitve a n naprej a n+1 bo enako nič ( a n+2=0).
.
Vsak skupni delitelj λ številke a 1 in a 2 je tudi delitelj števil a 2 in a 3 , a 3 in a 4 , .... a n in a n+1 . Velja tudi obratno, skupni delitelji števil a n in a n+1 so tudi delitelji števil a n−1 in a n, ...., a 2 in a 3 , a 1 in a 2. Ampak skupni delilec a n in a n+1 je število a n+1, ker a n in a n+1 so deljivi s a n+1 (spomni se tega a n+2=0). Posledično a n+1 je tudi delitelj števil a 1 in a 2 .
Upoštevajte, da je številka a n+1 je največji delitelj števila a n in a n+1 , saj je največji delitelj a n+1 je sam a n+1 . Če a n + 1 lahko predstavimo kot zmnožek celih števil, potem so ta števila tudi pogosti delitelji števil a 1 in a 2. številka a n+1 se imenujejo največji skupni deliteljštevilke a 1 in a 2 .
Številke a 1 in a 2 so lahko pozitivna in negativna števila. Če je eno od števil enako nič, potem bo največji skupni delitelj teh števil enak absolutni vrednosti drugega števila. Največji skupni delitelj števil nič ni definiran.
Pokliče se zgornji algoritem Evklidov algoritem najti največji skupni delitelj dveh celih števil.
Primer iskanja največjega skupnega delitelja dveh števil
Poiščite največji skupni delitelj dveh števil 630 in 434.
- Korak 1. Število 630 delite s 434. Ostanek je 196.
- Korak 2. Število 434 delite s 196. Ostanek je 42.
- Korak 3. Število 196 razdelite na 42. Ostanek je 28.
- Korak 4. Število 42 delite z 28. Ostanek je 14.
- Korak 5. Število 28 delite s 14. Ostanek je 0.
Pri koraku 5 je preostanek deljenja 0. Zato je največji skupni delitelj števil 630 in 434 14. Upoštevajte, da sta števili 2 in 7 tudi delitelja števil 630 in 434.
Kopraštevila
Opredelitev 1. Naj bo največji skupni delitelj števil a 1 in a 2 je enako ena. Nato se pokličejo te številke soprosta števila ki nimajo skupnega delitelja.
Izrek 1. Če a 1 in a 2 relativno praštevili in λ neko število, nato poljuben skupni delitelj števil λa 1 in a 2 je tudi skupni delitelj števil λ in a 2 .
Dokaz. Razmislite o Evklidovem algoritmu za iskanje največjega skupnega delitelja števil a 1 in a 2 (glej zgoraj).
.
Iz pogojev izreka sledi, da je največji skupni delitelj števil a 1 in a 2 in zato a n in a n+1 je 1. tj. a n+1=1.
Pomnožimo vse te enakosti z λ , potem
.
Naj skupni delilec a 1 λ in a 2 je δ . Potem δ vstopi kot dejavnik v a 1 λ , m 1 a 2 λ in v a 1 λ -m 1 a 2 λ =a 3 λ (Glej »Deljivost števil«, trditev 2). Nadalje δ vstopi kot dejavnik v a 2 λ in m 2 a 3 λ , in tako vstopi kot dejavnik a 2 λ -m 2 a 3 λ =a 4 λ .
S takšnim razmišljanjem smo prepričani, da δ vstopi kot dejavnik v a n−1 λ in m n−1 a n λ , torej v a n−1 λ −m n−1 a n λ =a n+1 λ . Ker a n+1 =1, torej δ vstopi kot dejavnik v λ . Zato število δ je skupni delitelj števil λ in a 2 .
Razmislite o posebnih primerih izreka 1.
Posledica 1. Pustiti a in c praštevila so relativna b. Nato njihov izdelek ac je praštevilo glede na b.
res. Iz izreka 1 ac in b imajo enake skupne delitelje kot c in b. Ampak številke c in b coprime, tj. imajo en sam skupni delitelj 1. Potem ac in b imajo tudi en sam skupni delitelj 1. Zato ac in b medsebojno preprosta.
Posledica 2. Pustiti a in b soprosta števila in pustimo b deli ak. Potem b deli in k.
res. Iz trditvenega pogoja ak in b imajo skupni delitelj b. Na podlagi izreka 1, b mora biti skupni delitelj b in k. Posledično b deli k.
Posledico 1 lahko posplošimo.
Posledica 3. 1. Naj številke a 1 , a 2 , a 3 , ..., a m so praštevila glede na število b. Potem a 1 a 2 , a 1 a 2 · a 3 , ..., a 1 a 2 a 3 ··· a m , je produkt teh števil praštevil glede na število b.
2. Naj imamo dve vrstici številk
tako, da je vsako število v prvi vrstici praštevilo glede na vsako število v drugi vrstici. Nato izdelek
Najti je treba takšna števila, ki so deljiva z vsakim od teh števil.
Če je število deljivo z a 1, potem izgleda sa 1, kjer s neko število. Če q je največji skupni delitelj števil a 1 in a 2, torej
kje s 1 je neko celo število. Potem
je najmanjši skupni večkratnik števil a 1 in a 2 .
a 1 in a 2 enako praštevila, potem najmanjši skupni večkratnik števil a 1 in a 2:
Poiščite najmanjši skupni večkratnik teh števil.
Iz zgoraj navedenega sledi, da vsak večkratnik števil a 1 , a 2 , a 3 mora biti večkratnik številk ε in a 3 in obratno. Najmanjši skupni večkratnik števil ε in a 3 je ε ena. Nadalje, večkratnik številk a 1 , a 2 , a 3 , a 4 mora biti večkratnik številk ε 1 in aštiri . Najmanjši skupni večkratnik števil ε 1 in a 4 je ε 2. Tako smo ugotovili, da so vsi večkratniki števil a 1 , a 2 , a 3 ,...,a m sovpada z večkratniki določenega števila ε n, ki se imenuje najmanjši skupni večkratnik danih števil.
V posebnem primeru, ko so številke a 1 , a 2 , a 3 ,...,a m skupno praštevilo, potem najmanjši skupni večkratnik števil a 1 , a 2, kot je prikazano zgoraj, ima obliko (3). Nadalje, saj a 3 praštevilo glede na števila a 1 , a 2, torej a 3 je praštevilo relativno a ena · a 2 (posledica 1). Torej najmanjši skupni večkratnik števil a 1 ,a 2 ,a 3 je številka a ena · a 2 · a 3. S podobnim argumentiranjem pridemo do naslednjih trditev.
Izjava 1. Najmanjši skupni večkratnik soprostih števil a 1 , a 2 , a 3 ,...,a m je enak njihovemu produktu a ena · a 2 · a 3 ··· a m .
Izjava 2. Vsako število, ki je deljivo z vsakim od soprostih števil a 1 , a 2 , a 3 ,...,a m je tudi deljiv z njihovim produktom a ena · a 2 · a 3 ··· a m .
Opredelitev. Največje naravno število, s katerim sta števili a in b deljivi brez ostanka, se imenuje največji skupni delitelj (gcd) te številke.
Poiščimo največji skupni delitelj števil 24 in 35.
Delitelji števila 24 bodo števila 1, 2, 3, 4, 6, 8, 12, 24, delitelji števila 35 pa bodo števila 1, 5, 7, 35.
Vidimo, da imata števili 24 in 35 le en skupni delitelj - število 1. Takšni števili se imenujeta coprime.
Opredelitev. Naravna števila imenujemo coprimeče je njihov največji skupni delitelj (gcd) 1.
Največji skupni delitelj (GCD) lahko najdete, ne da bi izpisali vse delitelje danih števil.
Če števili 48 in 36 faktoriziramo, dobimo:
48 = 2 * 2 * 2 * 2 * 3, 36 = 2 * 2 * 3 * 3.
Iz faktorjev, vključenih v razširitev prvega od teh števil, izbrišemo tiste, ki niso vključeni v razširitev drugega števila (tj. dve dvojki).
Ostanejo faktorji 2 * 2 * 3. Njihov produkt je 12. To število je največji skupni delitelj števil 48 in 36. Najden je tudi največji skupni delitelj treh ali več števil.
Najti največji skupni delitelj
2) izmed dejavnikov, vključenih v razširitev enega od teh števil, prečrtajte tiste, ki niso vključeni v razširitev drugih številk;
3) poiščite produkt preostalih faktorjev.
Če so vsa dana števila deljiva z enim od njih, potem je to število deljivo največji skupni delitelj podane številke.
Na primer, največji skupni delitelj 15, 45, 75 in 180 je 15, saj deli vsa druga števila: 45, 75 in 180.
Najmanjši skupni večkratnik (LCM)
Opredelitev. Najmanjši skupni večkratnik (LCM) naravni števili a in b sta najmanjše naravno število, ki je večkratnik obeh a in b. Najmanjši skupni večkratnik (LCM) števil 75 in 60 je mogoče najti, ne da bi zaporedoma izpisali večkratnike teh števil. Da bi to naredili, razgradimo 75 in 60 na preproste faktorje: 75 \u003d 3 * 5 * 5 in 60 \u003d 2 * 2 * 3 * 5.
Izpišemo faktorje, vključene v razširitev prvega od teh števil, in jim dodamo manjkajoča faktorja 2 in 2 iz razširitve drugega števila (to pomeni, da faktorje združimo).
Dobimo pet faktorjev 2 * 2 * 3 * 5 * 5, katerih produkt je 300. To število je najmanjši skupni večkratnik števil 75 in 60.
Poiščite tudi najmanjši skupni večkratnik treh ali več števil.
Za poiščite najmanjši skupni večkratnik več naravnih števil, potrebujete:
1) jih razstavite na prafaktorje;
2) izpišite faktorje, vključene v razširitev enega od števil;
3) dodajte jim manjkajoče faktorje iz razširitev preostalih števil;
4) poiščite produkt nastalih faktorjev.
Upoštevajte, da če je eno od teh števil deljivo z vsemi drugimi števili, potem je to število najmanjši skupni večkratnik teh števil.
Na primer, najmanjši skupni večkratnik 12, 15, 20 in 60 bi bil 60, ker je deljiv z vsemi danimi števili.
Pitagora (VI. stol. pr. n. št.) in njegovi učenci so preučevali vprašanje deljivosti števil. Število, ki je enako vsoti vseh svojih deliteljev (brez samega števila), so imenovali popolno število. Na primer, številke 6 (6 = 1 + 2 + 3), 28 (28 = 1 + 2 + 4 + 7 + 14) so popolne. Naslednja popolna števila so 496, 8128, 33 550 336. Pitagorejci so poznali le prva tri popolna števila. Četrti - 8128 - je postal znan v 1. stoletju. n. e. Petega - 33 550 336 - so našli v 15. stoletju. Do leta 1983 je bilo znanih že 27 popolnih števil. Toda do zdaj znanstveniki ne vedo, ali obstajajo liha popolna števila, ali obstaja največje popolno število.
Zanimanje starodavnih matematikov za praštevila je posledica dejstva, da je vsako število praštevilo ali pa ga je mogoče predstaviti kot produkt praštevil, to pomeni, da so praštevila kot opeke, iz katerih so zgrajena ostala naravna števila.
Verjetno ste opazili, da se praštevila v nizu naravnih števil pojavljajo neenakomerno - v nekaterih delih niza jih je več, v drugih - manj. Toda dlje kot se premikamo po številski vrsti, redkejša so praštevila. Postavlja se vprašanje: ali obstaja zadnje (največje) praštevilo? Starogrški matematik Evklid (3. stoletje pr. n. št.) je v svoji knjigi Začetki, ki je bila dva tisoč let glavni učbenik matematike, dokazal, da je praštevil neskončno veliko, to je, da za vsakim praštevilom stoji sodo večje praštevilo.
Za iskanje praštevil si je tako metodo omislil drug grški matematik iz istega časa, Eratosten. Zapisal je vsa števila od 1 do nekega števila, nato pa prečrtal enoto, ki ni niti praštevilo niti sestavljeno število, nato pa prečrtal skozi ena vsa števila za 2 (števila, ki so večkratniki 2, tj. 4, 6, 8 itd.). Prva preostala številka po 2 je bila 3. Nato so bile po dve prečrtane vse številke po 3 (števila, ki so večkratniki 3, tj. 6, 9, 12 itd.). na koncu so ostala neprečrtana samo praštevila.
Skupni večkratniki
Preprosto povedano, vsako celo število, ki je deljivo z vsakim od danih števil, je skupni večkratnik podana cela števila.
Najdete lahko skupni večkratnik dveh ali več celih števil.
Primer 1
Izračunajte skupni večkratnik dveh števil: $2$ in $5$.
rešitev.
Po definiciji je skupni večkratnik $2$ in $5$ 10$, ker je večkratnik $2$ in $5$:
Skupni večkratniki števil $2$ in $5$ bodo tudi števila $–10, 20, –20, 30, –30$ itd., ker vsi so deljivi z $2$ in $5$.
Opomba 1
Nič je skupni večkratnik poljubnega števila celih števil, ki niso nič.
V skladu z lastnostmi deljivosti velja, da če je določeno število skupni večkratnik več števil, potem bo tudi predznačno nasprotno število skupni večkratnik danih števil. To je razvidno iz obravnavanega primera.
Za dana cela števila lahko vedno najdete njihov skupni večkratnik.
Primer 2
Izračunajte skupni večkratnik $111$ in $55$.
rešitev.
Pomnožite podana števila: $111\div 55=6105$. Preprosto preverimo, da je število $6105$ deljivo s številom $111$ in s številom $55$:
$6105\div 111=55$;
6105 $\div 55=111 $.
Tako je $6105$ skupni večkratnik $111$ in $55$.
Odgovori: skupni večkratnik $111$ in $55$ je $6105$.
Toda, kot smo že videli iz prejšnjega primera, ta skupni večkratnik ni ena. Drugi pogosti večkratniki bi bili $-6105, 12210, -12210, 61050, -61050$ itd. Tako smo prišli do naslednje ugotovitve:
Opomba 2
Vsaka množica celih števil ima neskončno število skupnih večkratnikov.
V praksi so omejeni na iskanje skupnih mnogokratnikov le pozitivnih celih (naravnih) števil, ker množici večkratnikov danega števila in njegovega nasprotja sovpadata.
Iskanje najmanjšega skupnega večkratnika
Najpogosteje se od vseh večkratnikov danega števila uporabi najmanjši skupni večkratnik (LCM).
Definicija 2
Najmanjši pozitivni skupni večkratnik danih celih števil je najmanjši skupni večkratnik te številke.
Primer 3
Izračunajte LCM števil $4$ in $7$.
rešitev.
Ker ta števila nimajo skupnih deliteljev, potem $LCM(4,7)=28$.
Odgovori: $LCM(4,7)=28$.
Iskanje NOC prek NOD
Ker obstaja povezava med LCM in GCD, z njeno pomočjo je mogoče izračunati LCM dveh pozitivnih celih števil:
Opomba 3
Primer 4
Izračunajte LCM števil $232$ in $84$.
rešitev.
Uporabimo formulo za iskanje LCM skozi GCD:
$LCD (a,b)=\frac(a\cdot b)(gcd (a,b))$
Poiščimo gcd števil $232$ in $84$ z uporabo evklidskega algoritma:
$232=84\cdot 2+64$,
$84=64\cdot 1+20$,
$64=20\cdot 3+4$,
Tisti. $gcd (232, 84)=4$.
Poiščimo $LCM (232, 84)$:
$LCC(232,84)=\frac(232\cdot 84)(4)=58\cdot 84=4872$
Odgovori: $NOK(232,84)=4872$.
Primer 5
Izračunajte $LCM (23, 46)$.
rešitev.
Ker $46$ je enakomerno deljivo s $23$, potem je $gcd(23, 46)=23$. Poiščimo NOC:
$LCC(23,46)=\frac(23\cdot 46)(23)=46$
Odgovori: $NOK(23,46)=46$.
Tako se lahko oblikuje pravilo:
Opomba 4
Spodaj predstavljeno gradivo je logično nadaljevanje teorije iz članka pod naslovom LCM - najmanjši skupni večkratnik, definicija, primeri, razmerje med LCM in GCD. Tukaj bomo govorili o iskanje najmanjšega skupnega večkratnika (LCM), posebno pozornost pa namenite reševanju primerov. Najprej pokažimo, kako se LCM dveh števil izračuna glede na GCD teh števil. Nato razmislite o iskanju najmanjšega skupnega večkratnika s faktorjenjem števil na prafaktorje. Nato se bomo osredotočili na iskanje LCM treh ali več števil, pozornost pa bomo posvetili tudi izračunu LCM negativnih števil.
Navigacija po straneh.
Izračun najmanjšega skupnega večkratnika (LCM) prek gcd
Eden od načinov za iskanje najmanjšega skupnega večkratnika temelji na razmerju med LCM in GCD. Obstoječe razmerje med LCM in GCD vam omogoča, da izračunate najmanjši skupni večkratnik dveh pozitivnih celih števil prek znanega največjega skupnega delitelja. Ustrezna formula ima obliko LCM(a, b)=a b: GCD(a, b) . Razmislite o primerih iskanja LCM po zgornji formuli.
Primer.
Poišči najmanjši skupni večkratnik števil 126 in 70.
rešitev.
V tem primeru a=126 , b=70 . Uporabimo razmerje med LCM in GCD, izraženo s formulo LCM(a, b)=a b: GCD(a, b). Se pravi, najprej moramo poiskati največji skupni delitelj števil 70 in 126, nato pa lahko izračunamo LCM teh števil po napisani formuli.
Poiščite gcd(126, 70) z uporabo Evklidovega algoritma: 126=70 1+56 , 70=56 1+14 , 56=14 4 , torej gcd(126, 70)=14 .
Zdaj poiščemo zahtevani najmanjši skupni večkratnik: LCM(126, 70)=126 70: GCM(126, 70)= 126 70:14=630 .
odgovor:
LCM(126, 70)=630.
Primer.
Kaj je LCM(68, 34)?
rešitev.
Ker 68 je enakomerno deljivo s 34 , potem je gcd(68, 34)=34 . Zdaj izračunamo najmanjši skupni večkratnik: LCM(68, 34)=68 34: LCM(68, 34)= 68 34:34=68 .
odgovor:
LCM(68, 34)=68.
Upoštevajte, da prejšnji primer ustreza naslednjemu pravilu za iskanje LCM za pozitivna cela števila a in b: če je število a deljivo z b, potem je najmanjši skupni večkratnik teh števil a.
Iskanje LCM z faktorizacijo števil na prafaktorje
Drug način za iskanje najmanjšega skupnega večkratnika temelji na faktoriziranju števil na prafaktorje. Če naredimo produkt vseh prafaktorjev teh števil, nato pa iz tega produkta izločimo vse skupne prafaktorje, ki so prisotni v razširitvah teh števil, potem bo dobljeni produkt enak najmanjšemu skupnemu večkratniku teh števil.
Napovedano pravilo za iskanje LCM izhaja iz enakosti LCM(a, b)=a b: GCD(a, b). Zmnožek števil a in b je namreč enak zmnožku vseh faktorjev, ki sodelujejo pri razširitvah števil a in b. V zameno je gcd(a, b) enak produktu vseh prafaktorjev, ki so hkrati prisotni v razširitvah števil a in b (kar je opisano v razdelku o iskanju gcd z uporabo razgradnje števil na prafaktorje ).
Vzemimo primer. Naj vemo, da je 75=3 5 5 in 210=2 3 5 7 . Sestavite produkt vseh faktorjev teh razširitev: 2 3 3 5 5 5 7 . Sedaj iz tega produkta izločimo vse faktorje, ki so prisotni tako v ekspanziji števila 75 kot v ekspanziji števila 210 (takšna faktorja sta 3 in 5), potem bo produkt dobil obliko 2 3 5 5 7 . Vrednost tega produkta je enaka najmanjšemu skupnemu večkratniku števil 75 in 210, tj. LCM(75, 210)= 2 3 5 5 7=1 050.
Primer.
Ko števili 441 in 700 razložite na prafaktorje, poiščite najmanjši skupni večkratnik teh števil.
rešitev.
Razstavimo števili 441 in 700 na prafaktorje:
Dobimo 441=3 3 7 7 in 700=2 2 5 5 7 .
Sedaj pa naredimo produkt vseh faktorjev, ki sodelujejo pri razširitvah teh števil: 2 2 3 3 5 5 7 7 7 . Iz tega zmnožka izločimo vse dejavnike, ki so hkrati prisotni v obeh razširitvah (takšen faktor je samo en - to je število 7): 2 2 3 3 5 5 7 7 . V to smer, LCM(441, 700)=2 2 3 3 5 5 7 7=44 100.
odgovor:
LCM(441, 700)= 44 100 .
Pravilo za iskanje LCM z razgradnjo števil na prafaktorje lahko formuliramo nekoliko drugače. Če k faktorjem iz razširitve števila a prištejemo manjkajoče faktorje iz razširitve števila a, bo vrednost dobljenega produkta enaka najmanjšemu skupnemu večkratniku števil a in b.
Na primer, vzemimo isti števili 75 in 210, njuni razširitvi na prafaktorje sta naslednji: 75=3 5 5 in 210=2 3 5 7 . Faktorjem 3, 5 in 5 iz razčlenitve števila 75 prištejemo manjkajoča faktorja 2 in 7 iz razčlenitve števila 210, dobimo produkt 2 3 5 5 7 , katerega vrednost je LCM(75 , 210).
Primer.
Poiščite najmanjši skupni večkratnik števil 84 in 648.
rešitev.
Najprej dobimo razgradnjo števil 84 in 648 na prafaktorje. Videti sta kot 84=2 2 3 7 in 648=2 2 2 3 3 3 3 . Faktorjem 2, 2, 3 in 7 iz razčlenitve števila 84 prištejemo manjkajoče faktorje 2, 3, 3 in 3 iz razčlenitve števila 648, dobimo produkt 2 2 2 3 3 3 3 7 , kar je enako 4 536 . Tako je želeni najmanjši skupni večkratnik števil 84 in 648 4.536.
odgovor:
LCM(84, 648)=4 536.
Iskanje LCM treh ali več števil
Najmanjši skupni večkratnik treh ali več števil je mogoče najti z zaporednim iskanjem LCM dveh števil. Spomnimo se ustreznega izreka, ki nam pomaga najti LCM treh ali več števil.
Izrek.
Naj so podana pozitivna cela števila a 1 , a 2 , …, a k, najmanjši skupni večkratnik m k teh števil najdemo v zaporednem izračunu m 2 = LCM (a 1 , a 2) , m 3 = LCM (m 2 , a 3) , … , m k =LCM(m k−1 , a k) .
Razmislite o uporabi tega izreka na primeru iskanja najmanjšega skupnega večkratnika štirih števil.
Primer.
Poiščite LCM štirih števil 140, 9, 54 in 250.
rešitev.
V tem primeru a 1 =140, a 2 =9, a 3 =54, a 4 =250.
Najprej najdemo m 2 \u003d LCM (a 1, a 2) \u003d LCM (140, 9). Če želite to narediti, z uporabo evklidskega algoritma določimo gcd(140, 9) , imamo 140=9 15+5 , 9=5 1+4 , 5=4 1+1 , 4=1 4 , torej gcd( 140, 9)=1 , od koder je LCM(140, 9)=140 9: LCM(140, 9)= 140 9:1=1 260 . To je m 2 =1 260 .
Zdaj najdemo m 3 \u003d LCM (m 2, a 3) \u003d LCM (1 260, 54). Izračunajmo ga preko gcd(1 260, 54) , ki je prav tako določen z Evklidovim algoritmom: 1 260=54 23+18 , 54=18 3 . Potem je gcd(1 260, 54)=18 , od koder je LCM(1 260, 54)= 1 260 54:gcd(1 260, 54)= 1 260 54:18=3 780 . To je m 3 \u003d 3 780.
Ostalo najti m 4 \u003d LCM (m 3, a 4) \u003d LCM (3 780, 250). Da bi to naredili, poiščemo GCD(3 780, 250) z uporabo Evklidovega algoritma: 3 780=250 15+30 , 250=30 8+10 , 30=10 3 . Zato je gcd(3 780, 250)=10, od koder je gcd(3 780, 250)= 3 780 250:gcd(3 780, 250)= 3 780 250:10=94 500 . To je m 4 \u003d 94 500.
Torej je najmanjši skupni večkratnik prvotnih štirih števil 94.500.
odgovor:
LCM(140, 9, 54, 250)=94.500.
V mnogih primerih je najmanjši skupni večkratnik treh ali več števil priročno najti z uporabo prafaktorjev danih števil. V tem primeru je treba upoštevati naslednje pravilo. Najmanjši skupni večkratnik več števil je enak zmnožku, ki je sestavljen takole: manjkajočim faktorjem iz razširitve drugega števila se prištejejo vsi faktorji iz razširitve prvega števila, manjkajoči faktorji iz razširitve števila dobljenim faktorjem dodamo tretje število in tako naprej.
Razmislite o primeru iskanja najmanjšega skupnega večkratnika z uporabo razgradnje števil na prafaktorje.
Primer.
Poišči najmanjši skupni večkratnik petih števil 84 , 6 , 48 , 7 , 143 .
rešitev.
Najprej dobimo razširitve teh števil na prafaktorje: 84=2 2 3 7 , 6=2 3 , 48=2 2 2 2 3 , 7 prafaktorjev) in 143=11 13 .
Če želite najti LCM teh števil, morate faktorjem prvega števila 84 (so 2 , 2 , 3 in 7 ) dodati manjkajoče faktorje iz razširitve drugega števila 6 . Razširitev števila 6 ne vsebuje manjkajočih faktorjev, saj sta tako 2 kot 3 že prisotna v razširitvi prvega števila 84. Faktorjem 2, 2, 3 in 7 prištejemo manjkajoča faktorja 2 in 2 iz razširitve tretjega števila 48, dobimo množico faktorjev 2, 2, 2, 2, 3 in 7. Temu nizu v naslednjem koraku ni treba dodajati faktorjev, saj je 7 že v njem. Na koncu faktorjem 2 , 2 , 2 , 2 , 3 in 7 prištejemo manjkajoča faktorja 11 in 13 iz razširitve števila 143 . Dobimo zmnožek 2 2 2 2 3 7 11 13 , kar je enako 48 048 .
Največji skupni delitelj
Definicija 2
Če je naravno število a deljivo z naravnim številom $b$, potem $b$ imenujemo delitelj števila $a$, število $a$ pa večkratnik števila $b$.
Naj bosta $a$ in $b$ naravni števili. Število $c$ imenujemo skupni delitelj za $a$ in $b$.
Množica skupnih deliteljev števil $a$ in $b$ je končna, saj nobeden od teh deliteljev ne more biti večji od $a$. To pomeni, da je med temi delitelji največji, ki ga imenujemo največji skupni delitelj števil $a$ in $b$ in ga označujemo z zapisom:
$gcd \ (a;b) \ ali \ D \ (a;b)$
Če želite najti največji skupni delitelj dveh števil:
- Poiščite zmnožek števil iz 2. koraka. Dobljeno število bo želeni največji skupni delitelj.
Primer 1
Poiščite gcd števil $121$ in $132.$
$242=2\cdot 11\cdot 11$
$132=2\cdot 2\cdot 3\cdot 11$
Izberite številke, ki so vključene v razširitev teh številk
$242=2\cdot 11\cdot 11$
$132=2\cdot 2\cdot 3\cdot 11$
Poiščite zmnožek števil iz 2. koraka. Dobljeno število bo želeni največji skupni delitelj.
$gcd=2\cdot 11=22$
Primer 2
Poiščite GCD monomov $63$ in $81$.
Poiskali bomo po predstavljenem algoritmu. Za to:
Razčlenimo števila na prafaktorje
$63=3\cdot 3\cdot 7$
$81=3\cdot 3\cdot 3\cdot 3$
Izberemo številke, ki so vključene v razširitev teh številk
$63=3\cdot 3\cdot 7$
$81=3\cdot 3\cdot 3\cdot 3$
Poiščimo zmnožek števil, najdenih v koraku 2. Dobljeno število bo želeni največji skupni delitelj.
$gcd=3\cdot 3=9$
GCD dveh števil lahko najdete na drug način, z uporabo niza deliteljev števil.
Primer 3
Poiščite gcd števil $48$ in $60$.
rešitev:
Poiščite množico deliteljev $48$: $\left\((\rm 1,2,3.4.6,8,12,16,24,48)\right\)$
Zdaj pa poiščimo nabor deliteljev $60$:$\ \left\((\rm 1,2,3,4,5,6,10,12,15,20,30,60)\right\)$
Poiščimo presečišče teh množic: $\left\((\rm 1,2,3,4,6,12)\right\)$ - ta množica bo določala množico skupnih deliteljev števil $48$ in $60 $. Največji element v tem nizu bo številka $12$. Torej je največji skupni delitelj $48$ in $60$ 12$.
Opredelitev NOC
Definicija 3
skupni mnogokratnik naravnih števil$a$ in $b$ je naravno število, ki je večkratnik tako $a$ kot $b$.
Navadni večkratniki števil so števila, ki so deljiva z izvirnikom brez ostanka. Na primer, za števili $25$ in $50$ bodo skupni večkratniki števila $50,100,150,200$ itd.
Najmanjši skupni večkratnik bomo imenovali najmanjši skupni večkratnik in ga označili z LCM$(a;b)$ ali K$(a;b).$
Če želite najti LCM dveh števil, potrebujete:
- Razstavite števila na prafaktorje
- Izpišite faktorje, ki so del prvega števila in jim dodajte faktorje, ki so del drugega in ne gredo k prvemu.
Primer 4
Poiščite LCM števil $99$ in $77$.
Poiskali bomo po predstavljenem algoritmu. Za to
Razstavite števila na prafaktorje
99 $=3\cdot 3\cdot 11$
Zapišite dejavnike, vključene v prvi
dodajte jim dejavnike, ki so del drugega in ne gredo k prvemu
Poiščite zmnožek števil, najdenih v koraku 2. Dobljeno število bo želeni najmanjši skupni večkratnik
$LCC=3\cdot 3\cdot 11\cdot 7=693$
Sestavljanje seznamov deliteljev števil je pogosto zelo zamudno. Obstaja način za iskanje GCD, imenovan Evklidov algoritem.
Izjave, na katerih temelji Evklidov algoritem:
Če sta $a$ in $b$ naravni števili in $a\vpike b$, potem je $D(a;b)=b$
Če sta $a$ in $b$ naravni števili, tako da $b
Z uporabo $D(a;b)= D(a-b;b)$ lahko zaporedoma znižujemo obravnavana števila, dokler ne dosežemo para števil, tako da je eno od njiju deljivo z drugim. Potem bo manjše od teh števil želeni največji skupni delitelj za števili $a$ in $b$.
Lastnosti GCD in LCM
- Vsak skupni večkratnik $a$ in $b$ je deljiv s K$(a;b)$
- Če $a\vpike b$, potem je K$(a;b)=a$
Če je K$(a;b)=k$ in $m$-naravno število, potem je K$(am;bm)=km$
Če je $d$ skupni delitelj za $a$ in $b$, potem je K($\frac(a)(d);\frac(b)(d)$)=$\ \frac(k)(d ) $
Če $a\vdots c$ in $b\vdots c$, potem je $\frac(ab)(c)$ skupni večkratnik $a$ in $b$
Za poljubni naravni števili $a$ in $b$ velja enakost
$D(a;b)\cdot K(a;b)=ab$
Vsak skupni delitelj $a$ in $b$ je delitelj $D(a;b)$