Vozlišče zneska. Največji skupni delitelj (GCD): definicija, primeri in lastnosti

Spletni kalkulator omogoča hitro iskanje največjega skupnega delitelja in najmanjšega skupnega večkratnika dveh in katerega koli drugega števila števil.

Kalkulator za iskanje GCD in LCM

Poiščite GCD in LOC

Najden GCD in LOC: 5806

Kako uporabljati kalkulator

V vnosno polje vnesite številke
Če vnesete napačne znake, bo vnosno polje označeno rdeče
kliknite gumb "Najdi GCD in LOC".

Kako vnašati številke

Številke vnašamo ločene s presledkom, piko ali vejico
Dolžina vnesenih številk ni omejena, zato iskanje GCD in LCM dolgih števil ni težko

Kaj sta GCD in NOC?

Največji skupni delitelj več števil je največje naravno celo število, s katerim so vsa prvotna števila deljiva brez ostanka. Največji skupni delitelj je skrajšano označen kot GCD.
Najmanjši skupni večkratnik več številk je nai manjše število, ki je deljivo z vsakim od prvotnih števil brez ostanka. Najmanjši skupni večkratnik je skrajšan kot NOC.

Kako preveriti, ali je število deljivo z drugim številom brez ostanka?

Če želite ugotoviti, ali je eno število deljivo z drugim brez ostanka, lahko uporabite nekatere lastnosti deljivosti števil. Nato lahko s kombiniranjem preverite deljivost nekaterih izmed njih in njihovih kombinacij.

Nekateri znaki deljivosti števil

1. Preizkus deljivosti števila z 2
Če želite ugotoviti, ali je število deljivo z dvema (ali je sodo), je dovolj, da pogledate zadnjo številko tega števila: če je enako 0, 2, 4, 6 ali 8, potem je število sodo, kar pomeni, da je deljivo z 2.
primer: ugotovi, ali je število 34938 deljivo z 2.
rešitev: Poglej zadnja številka: 8 pomeni, da je število deljivo z dve.

2. Preizkus deljivosti števila s 3
Število je deljivo s 3, če je vsota njegovih števk deljiva s tri. Če želite torej ugotoviti, ali je število deljivo s 3, morate izračunati vsoto števk in preveriti, ali je deljivo s 3. Tudi če je vsota števk zelo velika, lahko ponovite isti postopek.
primer: ugotovi, ali je število 34938 deljivo s 3.
rešitev: Preštejemo vsoto števil: 3+4+9+3+8 = 27. 27 je deljivo s 3, kar pomeni, da je število deljivo s tri.

3. Preizkus deljivosti števila s 5
Število je deljivo s 5, če je njegova zadnja številka nič ali pet.
primer: ugotovi, ali je število 34938 deljivo s 5.
rešitev: poglejte zadnjo števko: 8 pomeni, da število NI deljivo s pet.

4. Preizkus deljivosti števila z 9
Ta znak je zelo podoben znaku deljivosti s tri: število je deljivo z 9, če je vsota njegovih števk deljiva z 9.
primer: ugotovi, ali je število 34938 deljivo z 9.
rešitev:Štejemo vsoto števil: 3+4+9+3+8 = 27. 27 je deljivo z 9, kar pomeni, da je število deljivo z devet.

Kako najti GCD in LCM dveh števil

Kako najti gcd dveh števil

večina na preprost način Izračun največjega skupnega delitelja dveh števil pomeni iskanje vseh možnih deliteljev teh števil in izbiro največjega med njimi.

Oglejmo si to metodo na primeru iskanja GCD(28, 36):

Obe števili razdelimo na faktorje: 28 = 1·2·2·7, 36 = 1·2·2·3·3
Najdemo skupni dejavniki, torej tiste, ki jih imata obe števili: 1, 2 in 2.
Izračunamo produkt teh faktorjev: 1 2 2 = 4 - to je največji skupni delitelj števil 28 in 36.

Kako najti LCM dveh števil

Obstajata dva najpogostejša načina za iskanje najmanjšega večkratnika dveh števil. Prvi način je, da lahko zapišete prva večkratnika dveh števil, nato pa med njimi izberete število, ki bo skupno obema številoma in hkrati najmanjše. In drugo je najti gcd teh števil. Upoštevajmo le to.

Če želite izračunati LCM, morate izračunati produkt prvotnih števil in ga nato deliti s predhodno najdenim GCD. Poiščimo LCM za isti števili 28 in 36:

Poiščite zmnožek števil 28 in 36: 28·36 = 1008
GCD(28, 36), kot je že znano, je enak 4
LCM(28, 36) = 1008 / 4 = 252.

Iskanje GCD in LCM za več števil

Največji skupni delitelj je mogoče najti za več števil, ne le za dve. V ta namen se števila, ki jih je treba najti za največji skupni delitelj, faktorizirajo na prafaktorje, nato se najde produkt skupnih faktorjev glavni dejavniki te številke. Za iskanje gcd več števil lahko uporabite tudi naslednjo relacijo: GCD(a, b, c) = GCD(GCD(a, b), c).

Podobno razmerje velja za najmanjši skupni večkratnik: LCM(a, b, c) = LCM(LCM(a, b), c)

primer: poiščite GCD in LCM za številke 12, 32 in 36.

Najprej faktorizirajmo števila: 12 = 1·2·2·3, 32 = 1·2·2·2·2·2, 36 = 1·2·2·3·3.
Poiščimo skupne faktorje: 1, 2 in 2.
Njihov produkt bo dal GCD: 1·2·2 = 4
Zdaj pa poiščimo LCM: da bi to naredili, najprej poiščimo LCM(12, 32): 12·32 / 4 = 96 .
Če želite najti LCM vseh treh števil, morate poiskati NOT(96, 36): 96 = 1·2·2·2·2·2·3 , 36 = 1·2·2·3·3 , NOT = 1·2· 2 3 = 12.
LCM(12, 32, 36) = 96·36 / 12 = 288.

Ena od nalog, ki predstavlja težavo sodobnim šolarjem, ki so vajeni primerno in neustrezno uporabljati v pripomočke vgrajene kalkulatorje, je iskanje največjega skupnega delitelja (NDK) dveh ali več števil.

Nemogoče je rešiti nobeno matematična težava, če se ne ve, po čem pravzaprav sprašujejo. Če želite to narediti, morate vedeti, kaj pomeni ta ali oni izraz., ki se uporablja v matematiki.

Morati vedeti:

Če je določeno število mogoče uporabiti za štetje razne predmete, na primer devet stebrov, šestnajst hiš, potem je naravno. Najmanjši med njimi bo eden.
Ko naravno število delimo z drugim naravnim številom, rečemo, da je manjše število delitelj večjega števila.
Če dva ali več različne številke so deljivi z določenim številom brez ostanka, potem pravijo, da bo slednji njihov skupni delitelj (CD).
Največji od OD se imenuje največji skupni delitelj (GCD).
V takem primeru, ko ima število samo dva naravni delilnik(sam je enota), se imenuje preprost. Najmanjše med njimi je dve in je tudi edino sodo število v njunem nizu.
Če imata dve števili največji skupni delitelj ena, bosta relativno praštevili.
Število, ki ima več kot dva delitelja, imenujemo sestavljeno.
Postopek iskanja vseh prafaktorjev, ki bodo, če jih pomnožimo skupaj, dali zmnožek začetna vrednost v matematiki se imenuje faktorizacija. Poleg tega se enaki dejavniki v razširitvi lahko pojavijo večkrat.

V matematiki so sprejeti naslednji zapisi:

Delitelji D (45) = (1;3;5;9;45).
OD (8;18) = (1;2).
GCD (8;18) = 2.

Različni načini za iskanje GCD

Na vprašanje je najlažje odgovoriti kako najti gcd v primeru, da je manjše število delitelj večjega. To bo v tak primer največji skupni delitelj.

Na primer, GCD (15;45) = 15, GCD (48;24) = 24.

Toda takšni primeri v matematiki so zelo redki, zato se za iskanje GCD uporabljajo bolj zapletene tehnike, čeprav je še vedno zelo priporočljivo preveriti to možnost pred začetkom dela.

Metoda razgradnje na enostavne faktorje

Če morate najti gcd dveh ali več različnih števil, je dovolj, da vsakega od njih razstavite na preproste faktorje in nato izvedete postopek množenja tistih od njih, ki so prisotni v vsakem od števil.

Primer 1

Poglejmo, kako najti GCD 36 in 90:

36 = 1*2*2*3*3;
90 = 1*2*3*3*5;

GCD (36;90) = 1*2*3*3 = 18.

Zdaj pa poglejmo, kako najti isto stvar V primer trehštevilke, vzemimo 54 kot primer; 162; 42.

36 že vemo, kako razstaviti, ugotovimo ostalo:

162 = 1*2*3*3*3*3;
42 = 1*2*3*7;

Tako je gcd (36;162;42) = 1*2*3 = 6.

Upoštevati je treba, da je pisanje enote v razširitvi popolnoma neobvezno.

Razmislimo o načinu kako preprosto razračunati na prafaktorje, za to bomo na levi zapisali številko, ki jo potrebujemo, na desni pa bomo zapisali glavni dejavniki.

Stolpci so lahko ločeni z znakom delitve ali preprosto navpično črto.

36 / 2 bomo nadaljevali naš proces delitve;
18/2 naprej;
9/3 in znova;
3/3 je zdaj čisto osnovno;
1 - rezultat je pripravljen.

Zahtevano 36 = 2*2*3*3.

Evklidski način

Ta možnost je človeštvu znana že od nekdaj starogrška civilizacija, je v marsičem preprostejši in ga pripisujejo velikemu matematiku Evklidu, čeprav so zelo podobne algoritme uporabljali že prej. Ta metoda je uporaba naslednjega algoritma, delimo večje število s preostankom za manj. Nato naš delitelj delimo z ostankom in to nadaljujemo v krogu, dokler ne pride do popolnega deljenja. Zadnja vrednost in se izkaže za želeni največji skupni delitelj.

Tukaj je primer uporabe tega algoritma :

Poskusimo ugotoviti, kakšen GCD imata 816 in 252:

816 / 252 = 3 in ostanek je 60. Zdaj delimo 252 s 60;
252 / 60 = 4 ostanek bo tokrat 12. Nadaljujmo naš krožni proces, delimo šestdeset z dvanajst;
60 / 12 = 5. Ker tokrat nismo prejeli nobenega ostanka, imamo pripravljen rezultat, dvanajst bo vrednost, ki jo iščemo.

Torej, na koncu našega procesa dobili smo gcd (816;252) = 12.

Dejanja, če je treba določiti GCD, če sta določeni več kot dve vrednosti

Ugotovili smo že, kaj storiti v primeru, ko sta dve različni številki, zdaj se bomo naučili, kako ravnati, če sta 3 ali več.

Kljub vsej navidezni zapletenosti, to nalogo nam ne bo več povzročalo težav. Zdaj izberemo poljubni dve števili in določimo vrednost, ki jo iščemo. Naslednji korak je iskanje gcd dobljenega rezultata in tretjine nastavite vrednosti. Nato spet ravnamo po že znanem principu za četrto peto in tako naprej.

Zaključek

Torej, kljub na videz veliki kompleksnosti naloge, ki je bila prvotno postavljena pred nas, je v resnici vse preprosto, glavna stvar je, da lahko natančno izvedete postopek delitve in se držite katerega koli od dveh zgoraj opisanih algoritmov.

Čeprav sta obe metodi povsem sprejemljivi, v Srednja šola prva metoda se veliko pogosteje uporablja. To je posledica dejstva, da bo faktorizacija na prafaktorje potrebna pri preučevanju naslednjega izobraževalna tema- določitev največjega skupnega večkratnika (LCM). Vendar velja še enkrat opozoriti, da uporabe evklidskega algoritma nikakor ni mogoče šteti za napačno.

Video

S tem videoposnetkom se lahko naučite, kako najti največji skupni delitelj.

Niste dobili odgovora na svoje vprašanje? Predlagajte temo avtorjem.

Ta članek je posvečen vprašanju iskanja največjega skupnega delitelja. Najprej bomo razložili, kaj to je, in podali nekaj primerov, predstavili definicije največjega skupnega delitelja 2, 3 ali več števil, nato pa se osredotočili na splošne lastnosti ta koncept in dokazali jih bomo.

Yandex.RTB R-A-339285-1

Kaj so skupni delilniki

Da bi razumeli, kaj je največji skupni delitelj, najprej formuliramo, kaj na splošno je skupni delitelj za cela števila.

V članku o večkratnikih in deliteljih smo povedali, da ima celo število vedno več deliteljev. Tu nas zanimajo delitelji določenega števila celih števil naenkrat, predvsem tistih, ki so vsem skupna (enaka). Zapišimo osnovno definicijo.

Definicija 1

Skupni delitelj več celih števil je število, ki je lahko delitelj vsakega števila iz navedene množice.

Primer 1

Tu so primeri takšnega delitelja: tri bo skupni delitelj za številki - 12 in 9, saj veljata enakosti 9 = 3 · 3 in − 12 = 3 · (− 4). Števili 3 in - 12 imata še druge skupne faktorje, kot so 1, − 1 in − 3. Vzemimo drug primer. Štiri cela števila 3, − 11, − 8 in 19 bodo imela dva skupna faktorja: 1 in - 1.

Če poznamo lastnosti deljivosti, lahko rečemo, da lahko vsako celo število delimo z ena in minus ena, kar pomeni, da bo vsaka množica celih števil že imela vsaj dva skupna delitelja.

Upoštevajte tudi, da če imamo skupni delitelj b za več števil, potem lahko ista števila delimo s nasprotno število, to je na - b. Načeloma lahko vzamemo le pozitivne delitelje, potem bodo tudi vsi skupni delitelji večji od 0. Tudi ta pristop je mogoče uporabiti, vendar ga popolnoma zanemariti negativna števila ne naredi tega.

Kaj je največji skupni delitelj (GCD)

V skladu z lastnostmi deljivosti, če je b delitelj celega števila a, ki ni enako 0, potem modul b ne more biti večji od modula a, zato ima vsako število, ki ni enako 0, končna številka delilniki. To pomeni, da bo končno tudi število skupnih deliteljev več celih števil, od katerih je vsaj eno različno od nič, in iz njihovega celotnega niza lahko vedno izberemo največ velika številka(prej smo govorili o konceptu največjega in najmanjšega celega števila, svetujemo vam, da ponovite to gradivo).

V nadaljnjih razpravah bomo domnevali, da bo vsaj eno iz množice števil, za katere moramo najti največji skupni delitelj, drugačno od 0. Če so vsi enaki 0, je lahko njihov delitelj poljubno celo število, in ker jih je neskončno veliko, ne moremo izbrati največjega. Z drugimi besedami, nemogoče je najti največji skupni delitelj za množico števil, ki je enaka 0.

Preidimo na formulacijo glavne definicije.

Definicija 2

Največji skupni delitelj več števil je največje celo število, ki deli vsa ta števila.

V pisni obliki največji skupni delitelj najpogosteje označujemo z okrajšavo GCD. Za dve števili jo lahko zapišemo kot gcd (a, b).

Primer 2

Kaj je primer gcd za dve celi števili? Na primer, za 6 in - 15 bi bilo 3. Utemeljimo to. Najprej zapišemo vse delitelje števila šest: ± 6, ± 3, ± 1, nato pa še vse delitelje števila petnajst: ± 15, ± 5, ± 3 in ± 1. Nato izberemo skupne: to so − 3, − 1, 1 in 3. Od teh morate izbrati največje število. To bo 3.

Za tri ali več števil bo določitev največjega skupnega faktorja skoraj enaka.

Definicija 3

Največji skupni delitelj treh ali več števil bo največje celo število, ki bo delilo vsa ta števila hkrati.

Za števila a 1, a 2, …, a n je primerno delitelj označiti kot NOT (a 1, a 2, …, a n). Vrednost samega delitelja je zapisana kot GCD (a 1, a 2, ..., a n) = b.

Primer 3

Tukaj so primeri največjega skupnega delitelja več celih števil: 12, - 8, 52, 16. Enako bo štiri, kar pomeni, da lahko zapišemo, da je GCD (12, - 8, 52, 16) = 4.

Pravilnost te trditve lahko preveriš tako, da zapišeš vse delitelje teh števil in nato izbereš največjega izmed njih.

V praksi so pogosto primeri, ko je največji skupni delitelj enak enemu od števil. To se zgodi, ko dano številko vsa druga števila lahko delite (v prvem odstavku članka smo podali dokaz za to trditev).

Primer 4

Tako je največji skupni delitelj števil 60, 15 in - 45 15, saj je petnajst deljivo ne samo s 60 in - 45, ampak tudi samo s seboj in za vsa ta števila ni večjega delitelja.

Poseben primer je medsebojno konstituiran praštevila. So cela števila z največjim skupnim deliteljem 1.

Osnovne lastnosti GCD in Evklidskega algoritma

Največji skupni delitelj ima nekaj značilne lastnosti. Oblikujmo jih v obliki izrekov in dokažimo vsakega od njih.

Upoštevajte, da so te lastnosti oblikovane za cela števila Nad ničlo, upoštevali pa bomo le pozitivne delitelje.

Definicija 4

Števili a in b imata največji skupni delitelj enak gcd za b in a, to je gcd (a, b) = gcd (b, a). Obračanje številk ne vpliva na končni rezultat.

Ta lastnost izhaja iz same definicije GCD in ne potrebuje dokazovanja.

Definicija 5

Če lahko število a delimo s številom b, potem bo množica skupnih deliteljev teh dveh števil podobna množici deliteljev števila b, to je gcd (a, b) = b.

Dokažimo to trditev.

Dokazi 1

Če imata števili a in b skupne delitelje, potem lahko vsako od njiju delimo z njima. Hkrati, če je a večkratnik b, bo vsak delitelj b tudi delitelj a, saj ima deljivost tako lastnost, kot je prehodnost. To pomeni, da bo vsak delitelj b skupen številoma a in b. To dokazuje, da če lahko a delimo z b, potem bo množica vseh deliteljev obeh števil sovpadala z množico deliteljev enega števila b. In ker je največji delitelj katerega koli števila to število samo, bo tudi največji skupni delitelj števil a in b enak b, tj. GCD (a, b) = b. Če je a = b, potem je gcd (a, b) = gcd (a, a) = gcd (b, b) = a = b, na primer gcd (132, 132) = 132.

S to lastnostjo lahko poiščemo največji skupni delitelj dveh števil, če je mogoče eno od njiju deliti z drugim. Ta delitelj je enak enemu od teh dveh števil, s katerima je mogoče deliti drugo število. Na primer, gcd (8, 24) = 8, ker je 24 večkratnik osmih.

Definicija 6 Dokaz 2

Poskusimo dokazati to lastnost. Na začetku imamo enakost a = b q + c in vsak skupni delilec a in b bo delil tudi c, kar je razloženo ustrezno lastnino deljivost. Zato bo vsak skupni delitelj b in c delil a. To pomeni, da bo množica skupnih deliteljev a in b sovpadala z množico deliteljev b in c, vključno z največjim med njimi, kar pomeni, da velja enakost gcd (a, b) = gcd (b, c).

Opredelitev 7

Naslednja lastnost se imenuje evklidski algoritem. Z njegovo pomočjo lahko izračunate največji skupni delitelj dveh števil, pa tudi dokažete druge lastnosti GCD.

Preden formuliramo lastnost, vam svetujemo, da ponovite izrek, ki smo ga dokazali v članku o deljenju z ostankom. V skladu z njim lahko deljivo število a predstavimo kot b · q + r, pri čemer je b tukaj delitelj, q neko celo število (imenovano tudi nepopoln kvocient), r pa ostanek, ki izpolnjuje pogoj 0 ≤ r ≤ b.

Recimo, da imamo dve celi števili, večji od 0, za kateri bodo veljale naslednje enakosti:

a = b q 1 + r 1, 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1

Te enakosti se končajo, ko r k + 1 postane enako 0. To se bo zagotovo zgodilo, saj je zaporedje b > r 1 > r 2 > r 3, ... niz padajočih celih števil, ki jih je lahko le končno število. To pomeni, da je r k največji skupni delitelj a in b, to je r k = gcd (a, b).

Najprej moramo dokazati, da je r k skupni delitelj števil a in b, nato pa še, da r k ni le delitelj, temveč največji skupni delitelj dveh danih števil.

Poglejmo zgornji seznam enakosti od spodaj navzgor. Po zadnji enakosti je
r k − 1 lahko delimo z r k . Na podlagi tega dejstva in prejšnje dokazane lastnosti največjega skupnega delitelja lahko trdimo, da lahko r k − 2 delimo z r k , saj
r k − 1 je deljeno z r k in r k je deljeno z r k .

Tretja enakost od spodaj nam omogoča sklep, da lahko r k − 3 delimo z r k itd. Drugi od spodaj je, da je b deljiv z r k, prvi pa, da je a deljiv z r k. Iz vsega tega sklepamo, da je r k skupni delitelj a in b.

Zdaj pa dokažimo, da je r k = GCD (a , b) . Kaj moram storiti? Dokažite, da bo vsak skupni delitelj a in b delil r k. Označimo ga z r 0 .

Poglejmo isti seznam enakosti, vendar od zgoraj navzdol. Na podlagi prejšnje lastnosti lahko sklepamo, da je r 1 deljiv z r 0, kar pomeni, da je po drugi enakosti r 2 deljen z r 0. Po vseh enačbah se spustimo navzdol in iz zadnje sklepamo, da je r k deljiv z r 0 . Zato je r k = gcd (a , b) .

Ob upoštevanju te lastnosti sklepamo, da je množica skupnih deliteljev a in b podobna množici deliteljev GCD teh števil. Ta izjava, ki je posledica Evklidovega algoritma, nam bo omogočila izračun vseh skupnih deliteljev dveh danih števil.

Pojdimo na druge lastnosti.

Opredelitev 8

Če sta a in b celi števili, ki nista enaki 0, potem morata obstajati še dve celi števili u 0 in v 0, za kateri bo veljala enakost GCD (a, b) = a · u 0 + b · v 0.

Enakost, podana v izjavi o lastnostih, je linearna predstavitev največjega skupnega delitelja a in b. Imenuje se Bezoutova relacija, števili u 0 in v 0 pa Bezoutova koeficienta.

Dokazi 3

Dokažimo to lastnost. Zapišimo zaporedje enačb z evklidskim algoritmom:

Prva enakost nam pove, da je r 1 = a − b · q 1 . Označimo 1 = s 1 in − q 1 = t 1 ter zapišimo to enakost v obliki r 1 = s 1 · a + t 1 · b. Tu bosta števili s 1 in t 1 celi števili. Druga enakost nam omogoča, da sklepamo, da je r 2 = b − r 1 · q 2 = b − (s 1 · a + t 1 · b) · q 2 = − s 1 · q 2 · a + (1 − t 1 · q 2) b . Označimo − s 1 · q 2 = s 2 in 1 − t 1 · q 2 = t 2 in prepišemo enakost kot r 2 = s 2 · a + t 2 · b, kjer bosta tudi s 2 in t 2 cela števila. To je zato, ker so tudi vsota celih števil, njihov produkt in razlika cela števila. Na povsem enak način dobimo iz tretje enakosti r 3 = s 3 · a + t 3 · b, iz naslednje r 4 = s 4 · a + t 4 · b itd. Na koncu ugotovimo, da je r k = s k · a + t k · b za celo število s k in t k . Ker je r k = GCD (a, b), označimo s k = u 0 in t k = v 0. Posledično lahko dobimo linearno predstavitev GCD v zahtevani obliki: NTO (a, b) = a · u 0 + b · v 0.

Opredelitev 9

GCD (m a, m b) = m GCD (a, b) za katero koli naravna vrednota m.

Dokaz 4

To lastnost je mogoče utemeljiti na naslednji način. Pomnožimo obe strani vsake enakosti v evklidskem algoritmu s številom m in dobimo, da je NOT (m · a, m · b) = m · r k, in r k je NOT (a, b). To pomeni gcd (m a, m b) = m gcd (a, b). To je lastnost največjega skupnega delitelja, ki se uporablja pri iskanju GCD z metodo faktorizacije.

Opredelitev 10

Če imata števili a in b skupni delitelj p, velja gcd (a: p, b: p) = gcd (a, b): p. V primeru, ko je p = NKT (a, b), dobimo NKT (a: NKT (a, b), b: NKT (a, b) = 1, torej števili a: NKT (a, b) in b : GCD (a , b) sta relativno praštevila.

Ker je a = p (a: p) in b = p (b: p), potem lahko na podlagi prejšnje lastnosti ustvarimo enakosti oblike gcd (a, b) = gcd (p (a: p), p · (b: p)) = p · GCD (a: p , b: p) , med katerimi bo dokaz te nepremičnine. To izjavo uporabljamo, ko dajemo navadni ulomki Za ireduktibilna oblika.

Opredelitev 11

Največji skupni delitelj a 1, a 2, …, a k bo število d k, ki ga lahko najdemo z zaporednim izračunom NOT (a 1, a 2) = d 2, NOT (d 2, a 3) = d 3 , NOT (d 3 , a 4) = d 4 , … , NOT (d k - 1 , a k) = d k .

Ta lastnost je uporabna pri iskanju največjega skupnega delitelja treh ali več števil. Z njegovo uporabo lahko to dejanje zmanjšate na operacije z dvema številkama. Njegova osnova je posledica evklidskega algoritma: če množica skupnih deliteljev a 1, a 2 in a 3 sovpada z množico d 2 in a 3, potem bo sovpadala tudi z delitelji d 3. Delitelji števil a 1, a 2, a 3 in a 4 bodo sovpadali z delitelji števila d 3, kar pomeni, da bodo sovpadali tudi z delitelji števila d 4 itd. Na koncu dobimo, da bodo skupni delitelji števil a 1, a 2, ..., a k sovpadali z delitelji d k, in ker bo največji delitelj števila d k to število samo, potem je GCD (a 1, a 2, ..., a k) = d k.

To je vse, kar bi vam radi povedali o lastnostih največjega skupnega delitelja.

Če v besedilu opazite napako, jo označite in pritisnite Ctrl+Enter

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 število 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 kažejo velika začetnica"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 le 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 opredelimo kot najmanjšo pozitivni element nabor vseh njihovih linearnih kombinacij:

in jo zato predstavljajo kot linearno kombinacijo števil m in n:

To razmerje se imenuje Bezoutovo razmerje, in koeficientov u in v — Brezoutovi koeficienti. Bezoutovi koeficienti so učinkovito izračunani z razširjenim evklidskim algoritmom. Ta izjava se 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čunate, če poznate kanonična razgradnjaštevilke 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 njun gcd najde z na naslednji algoritem:

- 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 izpišite samo tiste dejavnike, ki so vključeni v vse podane številke. 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.