Opredelitev. Največje naravno število, ki ga lahko brez ostanka delimo s številoma a in b, imenujemo največji skupni delitelj (GCD) te številke.
Poiščimo največjega skupni delilnikštevilki 24 in 35.
Delitelji števila 24 so števila 1, 2, 3, 4, 6, 8, 12, 24, delitelji števila 35 pa števila 1, 5, 7, 35.
Vidimo, da imata števili 24 in 35 le en skupni delitelj - število 1. Takšni števili se imenujeta medsebojno prime.
Opredelitev. Naravna števila imenujemo medsebojno prime, č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.
Izmed dejavnikov, vključenih v razširitev prvega od teh števil, prečrtamo tiste, ki niso vključeni v razširitev drugega števila (tj. dve dvojki).
Preostala faktorja sta 2 * 2 * 3. Njun 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 števil 15, 45, 75 in 180 je število 15, saj so z njim deljiva vsa druga števila: 45, 75 in 180.
Najmanjši skupni večkratnik (LCM)
Opredelitev. Najmanjši skupni večkratnik (LCM) naravna števila a in b sta najmanjše naravno število, ki je večkratnik tako a kot b. Najmanjši skupni večkratnik (LCM) števil 75 in 60 je mogoče najti, ne da bi zaporedoma zapisali večkratnike teh števil. Da bi to naredili, razgradimo 75 in 60 na glavni dejavniki: 75 = 3 * 5 * 5 in 60 = 2 * 2 * 3 * 5.
Izpišimo faktorje, vključene v razširitev prvega od teh števil, in jim prištejmo manjkajoča faktorja 2 in 2 iz razširitve drugega števila (tj. 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ščejo tudi najmanjši skupni večkratnik treh ali več števil.
Za poiščite najmanjši skupni večkratnik več naravnih števil, potrebujete:
1) jih razložite na prafaktorje;
2) zapiš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 števil 12, 15, 20 in 60 je 60, ker je deljivo z vsemi temi števili.
Pitagora (VI stol. pr. n. št.) in njegovi učenci so preučevali vprašanje deljivosti števil. številka, enaka vsoti Vse njegove delitelje (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 znanstveniki še vedno ne vedo, ali obstajajo liha popolna števila ali obstaja največje popolno število.
Zanimanje starodavnih matematikov za praštevila izhaja iz dejstva, da je vsako število praštevilo ali pa ga je mogoče predstaviti kot produkt praštevila, torej praštevila so 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, manj pogosta 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 Elementi, ki je bila dva tisoč let glavni učbenik matematike, dokazal, da je praštevil neskončno veliko, tj. za vsakim praštevilom stoji še večje praštevilo. število.
Da bi našli praštevila, je drug grški matematik iz istega časa, Eratosten, prišel do te metode. Zapisal je vsa števila od 1 do nekega števila, nato pa prečrtal eno, ki ni niti praštevilo niti sestavljeno število, nato pa skozi 1 prečrtal vsa števila, ki prihajajo za 2 (števila, ki so večkratniki 2, tj. 4, 6, 8 itd.). Prva preostala številka za 2 je bila 3. Nato so bile za dve prečrtane vse številke za 3 (števila, ki so večkratniki 3, tj. 6, 9, 12 itd.). na koncu so ostala samo praštevila neprečrtana.
Iskanje največjega skupnega delitelja treh ali več števil se lahko zmanjša na zaporedno iskanje gcd dveh števil. To smo omenili pri preučevanju lastnosti GCD. Tam smo oblikovali in dokazali izrek: največji skupni delitelj več števil a 1, a 2, …, a k enako številu dk, ki se ugotovi z zaporednim izračunom GCD(a 1 , a 2)=d 2, GCD(d 2 , a 3)=d 3, GCD(d 3 , a 4)=d 4, …,GCD(d k-1 , a k)=d k.
Poglejmo, kako izgleda postopek iskanja gcd več števil, tako da pogledamo rešitev primera.
Primer.
Poiščite največji skupni delitelj štirih števil 78 , 294 , 570 in 36 .
rešitev.
V tem primeru a 1 =78, a 2 =294, a 3 =570, a 4 =36.
Najprej z evklidskim algoritmom določimo največji skupni delitelj d 2 prvi dve številki 78 in 294 . Pri deljenju dobimo enačbe 294=78 3+60; 78=60 1+18;60=18·3+6 in 18=6·3. torej d 2 =NOT(78, 294)=6.
Zdaj pa izračunajmo d 3 =NOT(d 2, a 3)=NOT(6, 570). Ponovno uporabimo evklidski algoritem: 570=6·95, torej, d 3 =NOT(6, 570)=6.
Ostaja še izračunati d 4 =NOT(d 3, a 4)=NOT(6, 36). Ker 36 deljeno z 6 , To d 4 =NOT(6, 36)=6.
Tako je največji skupni delitelj štirih danih števil enak d 4 =6, to je GCD(78, 294, 570, 36)=6.
odgovor:
GCD(78, 294, 570, 36)=6.
Razlaganje števil na prafaktorje vam omogoča tudi izračun gcd treh ali več števil. V tem primeru je največji skupni delitelj najden kot produkt vseh skupnih prafaktorjev danih števil.
Primer.
Izračunajte gcd števil iz prejšnjega primera z uporabo njihovih prafaktorjev.
rešitev.
Razčlenimo številke 78 , 294 , 570 in 36 s prafaktorji, dobimo 78=2·3·13,294=2·3·7·7, 570=2 3 5 19, 36=2·2·3·3. Skupni prafaktorji vseh danih štirih števil so števila 2 in 3 . torej GCD(78, 294, 570, 36)=2·3=6.
odgovor:
GCD(78, 294, 570, 36)=6.
Vrh strani
Iskanje gcd negativnih števil
Če so eno, več ali vsa števila, katerih največji delitelj je treba najti, negativna števila, potem je njihov gcd enak največjemu skupnemu delitelju modulov teh števil. To je posledica dejstva, da nasprotna števila a in −a imajo enake delitelje, kot smo razpravljali pri preučevanju lastnosti deljivosti.
Primer.
Poiščite gcd negativnih celih števil −231 in −140 .
rešitev.
Modul števila −231 enako 231 , in modul števila −140 enako 140 , In GCD(−231, −140)=GCD(231, 140). Evklidski algoritem nam daje naslednje enakosti: 231=140 1+91; 140=91 1+49; 91=49 1+42; 49=42 1+7 in 42=7 6. torej GCD(231, 140)=7. Potem je želeni največji skupni delitelj negativnih števil −231 in −140 enako 7 .
odgovor:
GCD(−231, −140)=7.
Primer.
Določite gcd treh števil −585 , 81 in −189 .
rešitev.
Pri iskanju največjega skupnega delitelja lahko negativna števila nadomestimo z njihovimi absolutnimi vrednostmi, tj. GCD(−585, 81, −189)=GCD(585, 81, 189). Razširitve številk 585 , 81 in 189 v prafaktorje imajo obliko 585=3·3·5·13, 81=3·3·3·3 in 189=3·3·3·7. Skupni prafaktorji teh treh števil so 3 in 3 . Potem GCD(585, 81, 189)=3·3=9, torej, GCD(−585, 81, −189)=9.
odgovor:
GCD(−585, 81, −189)=9.
35. Korenine polinoma. Bezoutov izrek. (33 in več)
36. Več korenin, kriterij za množičnost korenin.
Največji skupni delitelj in najmanjši skupni večkratnik sta ključna pojma aritmetike, ki vam omogočata enostavno delovanje navadni ulomki. LCM in se najpogosteje uporabljata za iskanje skupnega imenovalca več ulomkov.
Osnovni pojmi
Delitelj celega števila X je drugo celo število Y, s katerim se X deli brez ostanka. Na primer, delitelj 4 je 2, 36 pa 4, 6, 9. Večkratnik celega števila X je število Y, ki je deljivo z X brez ostanka. Na primer, 3 je večkratnik 15 in 6 je večkratnik 12.
Za vsak par števil lahko najdemo njihove skupne delitelje in večkratnike. Na primer, za 6 in 9 je skupni večkratnik 18, skupni delitelj pa 3. Očitno imajo pari lahko več deliteljev in večkratnikov, zato se pri izračunih uporablja največji delitelj GCD in najmanjši večkratnik LCM.
Najmanjši delitelj je brez pomena, saj je za vsako število vedno ena. Tudi največji mnogokratnik je nesmiseln, saj gre zaporedje večkratnikov v neskončnost.
Iskanje gcd
Obstaja veliko metod za iskanje največjega skupnega delitelja, med katerimi so najbolj znane:
- zaporedno naštevanje deliteljev, izbiranje skupnih za par in iskanje največjega med njimi;
- razstavljanje števil na nedeljive faktorje;
- Evklidski algoritem;
- binarni algoritem.
Danes ob izobraževalne ustanove Najbolj priljubljeni sta metodi prafaktorizacije in evklidskega algoritma. Slednje pa se uporablja pri reševanju Diofantovih enačb: iskanje GCD je potrebno za preverjanje enačbe glede možnosti razrešitve v celih številih.
Iskanje NOC
Najmanjši skupni večkratnik se določi tudi z zaporednim štetjem ali faktorizacijo na nedeljive faktorje. Poleg tega je enostavno najti LCM, če je največji delitelj že določen. Za števili X in Y sta LCM in GCD povezana z naslednjim razmerjem:
LCD(X,Y) = X × Y / GCD(X,Y).
Na primer, če je GCM(15,18) = 3, potem je LCM(15,18) = 15 × 18 / 3 = 90. Najbolj očiten primer uporabe LCM je iskanje skupnega imenovalca, ki je najmanjši skupni večkratnik dani ulomki.
Kopraštevila
Če par števil nima skupnih deliteljev, se tak par imenuje soprost. Gcd za take pare je vedno enaka ena, na podlagi povezave med delitelji in večkratniki pa je gcd za pare sopraprostih enak njihovemu produktu. Na primer, števili 25 in 28 sta relativno praštevili, ker nimata skupnih deliteljev, LCM(25, 28) = 700, kar ustreza njunemu produktu. Kateri koli dve nedeljivi števili bosta vedno relativno praštevili.
Skupni delitelj in večkratni kalkulator
Z našim kalkulatorjem lahko izračunate GCD in LCM za poljubno število števil, med katerimi lahko izbirate. Naloge za izračun skupnih deliteljev in večkratnikov najdemo v aritmetiki 5. in 6. razreda, vendar sta GCD in LCM ključna pojma v matematiki in se uporabljata v teoriji števil, planimetriji in komunikativni algebri.
Primeri iz resničnega življenja
Skupni imenovalec ulomkov
Najmanjši skupni večkratnik se uporablja pri iskanju skupnega imenovalca več ulomkov. Spusti noter aritmetični problem sešteti morate 5 ulomkov:
1/8 + 1/9 + 1/12 + 1/15 + 1/18.
Če želite dodati ulomke, je treba izraz zmanjšati na skupni imenovalec, kar se zmanjša na problem iskanja LCM. Če želite to narediti, izberite 5 številk v kalkulatorju in vnesite vrednosti imenovalcev v ustrezne celice. Program bo izračunal LCM (8, 9, 12, 15, 18) = 360. Zdaj morate za vsak ulomek izračunati dodatne faktorje, ki so definirani kot razmerje med LCM in imenovalcem. Torej bi dodatni množitelji izgledali takole:
- 360/8 = 45
- 360/9 = 40
- 360/12 = 30
- 360/15 = 24
- 360/18 = 20.
Po tem pomnožimo vse ulomke z ustreznim dodatnim faktorjem in dobimo:
45/360 + 40/360 + 30/360 + 24/360 + 20/360.
Takšne ulomke zlahka seštejemo in dobimo rezultat 159/360. Ulomek zmanjšamo za 3 in vidimo končni odgovor - 53/120.
Reševanje linearnih Diofantovih enačb
Linearne Diofantove enačbe so izrazi oblike ax + by = d. Če je razmerje d / gcd(a, b) celo število, potem je enačba rešljiva v celih številih. Preverimo nekaj enačb, da vidimo, ali imajo celoštevilsko rešitev. Najprej preverimo enačbo 150x + 8y = 37. S pomočjo kalkulatorja najdemo GCD (150,8) = 2. Razdelimo 37/2 = 18,5. Število ni celo število, zato enačba nima celih korenov.
Preverimo enačbo 1320x + 1760y = 10120. S kalkulatorjem poiščite GCD(1320, 1760) = 440. Delite 10120/440 = 23. Kot rezultat dobimo celo število, zato je Diofantova enačba rešljiva v celih koeficientih .
Zaključek
GCD in LCM igrata veliko vlogo v teoriji števil, koncepta sama pa se pogosto uporabljata na najrazličnejših področjih matematike. Uporabite naš kalkulator za izračun največjih deliteljev in najmanjših večkratnikov poljubnega števila števil.
Toda veliko naravnih števil je deljivih tudi z drugimi naravnimi števili.
Na primer:
Število 12 je deljivo z 1, z 2, s 3, s 4, s 6, z 12;
Število 36 je deljivo z 1, z 2, s 3, s 4, s 6, z 12, z 18, s 36.
Števila, s katerimi je število deljivo s celoto (pri 12 so to 1, 2, 3, 4, 6 in 12), se imenujejo delitelji števil. Delitelj naravnega števila a- je naravno število, ki deli dano številko a brez sledu. Naravno število, ki ima več kot dva delitelja, imenujemo sestavljeno. Upoštevajte, da imata števili 12 in 36 skupne faktorje. Ta števila so: 1, 2, 3, 4, 6, 12. Največji delitelj teh števil je 12.
Skupni delitelj dveh danih števil a in b- to je število, s katerim sta obe dani števili deljeni brez ostanka a in b. Skupni delitelj več števil (NOD) je število, ki služi kot delitelj za vsakega od njih.
Na kratko največji skupni delitelj števil a in b zapiši takole:
Primer: GCD (12; 36) = 12.
Delitelji števil v zapisu rešitve so označeni z veliko črko »D«.
primer:
GCD (7; 9) = 1
Števili 7 in 9 imata samo en skupni delitelj – število 1. Takšni števili se imenujeta medsebojno primechi slami.
Kopraštevila- to so naravna števila, ki imajo samo en skupni delitelj - število 1. Njihova gcd je 1.
Največji skupni delitelj (GCD), lastnosti.
- Osnovna lastnost: največji skupni delitelj m in n je deljivo s poljubnim skupnim deliteljem teh števil. Primer: Pri številih 12 in 18 je največji skupni delitelj 6; delijo ga vsi skupni delitelji teh števil: 1, 2, 3, 6.
- Posledica 1: množica skupnih deliteljev m in n sovpada z množico deliteljev GCD( m, n).
- Posledica 2: množica skupnih mnogokratnikov m in n sovpada z množico več LCM ( m, n).
To zlasti pomeni, da morate za redukcijo ulomka v nezmanjšano obliko deliti njegov števec in imenovalec z njunim gcd.
- Največji skupni delitelj števil m in n lahko definiramo kot najmanjši pozitivni element množice vseh njihovih linearnih kombinacij:
in jo zato predstavljajo kot linearno kombinacijo števil m in n:
To razmerje se imenuje Bezoutov odnos, in koeficientov u in v — Brezoutovi koeficienti. Bezoutovi koeficienti so učinkovito izračunani z razširjenim evklidskim algoritmom. Ta trditev posplošuje na množice naravnih števil - njen pomen je, da je podskupina skupine, ki jo generira množica, ciklična in jo generira en element: GCD ( a 1 , a 2 , … , a n).
Izračunajte največji skupni delitelj (GCD).
Učinkoviti načini za izračun gcd dveh števil so Evklidski algoritem in dvojiškoalgoritem. Poleg tega je vrednost gcd ( m,n) lahko enostavno izračunamo, če poznamo kanonično razširitev števil m in n na prafaktorje:
kjer sta različna praštevila in in sta nenegativni celi števili (lahko sta ničli, če ustreznega praštevila ni v razširitvi). Nato GCD ( m,n) in NOC ( m,n) so izražene s formulami:
Če obstaja več kot dve številki: , se njihov gcd najde z naslednjim algoritmom:
- to je želeni GCD.
Tudi zato, da bi našli največji skupni delitelj, lahko vsako od danih števil razložite na prafaktorje. Nato posebej zapiši samo tiste dejavnike, ki so vključeni v vsa navedena števila. Nato zapisana števila pomnožimo skupaj – rezultat množenja je največji skupni delitelj .
Oglejmo si korak za korakom izračun največjega skupnega delitelja:
1. Razstavite delitelje števil na prafaktorje:
Izračune je priročno pisati z navpično vrstico. Na levi strani črte najprej zapišemo dividendo, na desno - delitelj. Nato v levi stolpec zapišemo vrednosti količnikov. Takoj razložimo s primerom. Razložimo števili 28 in 64 na prafaktorje.
2. Pri obeh številih poudarimo iste prafaktorje:
28 = 2 . 2 . 7
64 = 2 . 2 . 2 . 2 . 2 . 2
3. Poišči zmnožek enakih prafaktorjev in zapiši odgovor:
GCD (28; 64) = 2. 2 = 4
Odgovor: GCD (28; 64) = 4
Lokacijo GCD lahko formalizirate na dva načina: v stolpcu (kot je storjeno zgoraj) ali "v vrstici".
Prvi način za pisanje GCD:
Poiščite gcd 48 in 36.
GCD (48; 36) = 2. 2. 3 = 12
Drugi način pisanja GCD:
Sedaj pa v vrstico zapišimo rešitev iskanja GCD. Poiščite gcd 10 in 15.
D (10) = (1, 2, 5, 10)
D (15) = (1, 3, 5, 15)
D (10, 15) = (1, 5)
Da bi razumeli, kako izračunati LCM, morate najprej določiti pomen izraza "več".
Večkratnik A je naravno število, ki je deljivo z A brez ostanka. Število, ki je večkratnik števila 5, lahko štejemo za 15, 20, 25 itd.
Obstajajo lahko delilniki določenega števila omejena količina, vendar obstaja neskončno število večkratnikov.
Skupni večkratnik naravnih števil je število, ki je z njimi deljivo brez ostanka.
Kako najti najmanjši skupni večkratnik števil
Najmanjši skupni večkratnik (LCM) števil (dva, tri ali več) je najmanjše naravno število, ki je deljivo z vsemi temi števili.
Če želite najti LOC, lahko uporabite več metod.
Za majhna števila je priročno zapisati vse večkratnike teh števil v črto, dokler med njimi ne najdete nekaj skupnega. Večkratnike označujemo z veliko črko K.
Na primer, večkratnike števila 4 lahko zapišemo takole:
K (4) = (8,12, 16, 20, 24, ...)
K (6) = (12, 18, 24, ...)
Tako lahko vidite, da je najmanjši skupni večkratnik števil 4 in 6 število 24. Ta zapis je narejen na naslednji način:
LCM(4, 6) = 24
Če so številke velike, poiščite skupni večkratnik treh ali več števil, potem je bolje uporabiti drugo metodo izračuna LCM.
Za dokončanje naloge morate dana števila razložiti na prafaktorje.
Najprej morate na črto zapisati razgradnjo največjega števila, pod njim pa ostalo.
Razčlenitev vsakega števila lahko vsebuje različno število faktorjev.
Na primer, razložimo števili 50 in 20 na prafaktorje.
Pri širjenju manjšega števila je treba poudariti dejavnike, ki jih pri širjenju prvega ni. veliko število, nato pa ji jih dodajte. V predstavljenem primeru manjka dvojka.
Zdaj lahko izračunate najmanjši skupni večkratnik 20 in 50.
LCM(20, 50) = 2 * 5 * 5 * 2 = 100
Torej, produkt prafaktorjev več in faktorji drugega števila, ki niso bili vključeni v razširitev večjega števila, bodo najmanjši skupni večkratnik.
Če želite najti LCM treh ali več števil, jih morate vse razložiti na prafaktorje, kot v prejšnjem primeru.
Kot primer lahko poiščete najmanjši skupni večkratnik števil 16, 24, 36.
36 = 2 * 2 * 3 * 3
24 = 2 * 2 * 2 * 3
16 = 2 * 2 * 2 * 2
Tako le dve dvojki iz razširitve šestnajstice nista bili vključeni v faktorizacijo večjega števila (ena je v razširitvi štiriindvajsetice).
Tako jih je treba razširitvi dodati večje število.
LCM(12, 16, 36) = 2 * 2 * 3 * 3 * 2 * 2 = 9
Obstajajo posebni primeri določanja najmanjšega skupnega večkratnika. Torej, če je mogoče eno od števil brez ostanka deliti z drugim, potem bo večje od teh števil najmanjši skupni večkratnik.
Na primer, LCM za dvanajst in štiriindvajset je štiriindvajset.
Če je treba najti najmanjši skupni večkratnik soprostih števil, ki nimajo enakih deliteljev, bo njihov LCM enak njihovemu produktu.
Na primer, LCM (10, 11) = 110.