Euklidski algoritam i njegove modifikacije. Euklidov algoritam

Euklidov algoritam To je algoritam za pronalaženje najvećeg zajedničkog djelitelja (GCD) para cijelih brojeva.

Najveći zajednički djelitelj (GCD) Broj koji dijeli dva broja bez ostatka i dijeli se bez ostatka s bilo kojim drugim djeliteljem ova dva broja. Jednostavno rečeno, ovo je najveći broj kojim se dva broja za koja se traži GCD mogu podijeliti bez ostatka.

Algoritam za pronalaženje GCD po dijeljenju

1. Podijelite veći broj manjim.
2. Ako se podijeli bez ostatka, tada je manji broj GCD (trebalo bi izaći iz ciklusa).
3. Ako postoji ostatak, tada se veći broj zamjenjuje ostatkom dijeljenja.
4. Prelazimo na tačku 1.

primjer:
Pronađite GCD za 30 i 18.
30/18 = 1 (ostatak 12)
18/12 = 1 (ostatak 6)
12/6 = 2 (ostatak 0)
Kraj: GCD je djelitelj 6.
GCD (30, 18) = 6

a = 50 b = 130 dok je a! = 0 i b! = 0: ako je a> b: a = a% b drugo: b = b% a print (a + b)

U petlji, ostatak dijeljenja se upisuje u varijablu a ili b. Ciklus se završava kada je barem jedna od varijabli jednaka nuli. To znači da drugi sadrži GCD. Međutim, koji, ne znamo. Stoga, za GCD nalazimo zbir ovih varijabli. Pošto je jedna od varijabli nula, to nema utjecaja na rezultat.

Algoritam za pronalaženje GCD oduzimanjem

1. Od većeg broja oduzmite manji.
2. Ako se pokaže da je 0, to znači da su brojevi jednaki jedan drugom i da su GCD (trebalo bi izaći iz ciklusa).
3. Ako rezultat oduzimanja nije 0, tada se veći broj zamjenjuje rezultatom oduzimanja.
4. Prelazimo na tačku 1.

primjer:
Pronađite GCD za 30 i 18.
30 - 18 = 12
18 - 12 = 6
12 - 6 = 6
6 - 6 = 0
Kraj: GCD se može odbiti ili oduzima.
GCD (30, 18) = 6

a = 50 b = 130 dok a! = b: ako a> b: a = a - b ostalo: b = b - otisak (a)

1.1 Primjena Euklidovog algoritma

Kao i svaki dobar posao, Euklidov algoritam daje mnogo više nego što se prvobitno očekivalo da će iz njega dobiti. Gledajući to, jasno je, na primjer, da se skup djelitelja a i b poklapa sa skupom djelitelja (a, b). On također daje praktičan način pronalaženja brojeva u i v iz Z (ili, ako želite, iz teoreme tačke 2) tako da

r n = au + bv = (a, b).

Zaista, iz lanca jednakosti imamo:

r n = r n -2 - r n -1 q n = r n -2 - (r n -3 - r n -2 q n -1) q n = ...

(idemo duž lanca jednakosti odozdo prema gore, izražavajući ostatak od svake sljedeće jednakosti i zamjenjujući ga u izraz koji se dobije u ovom trenutku)

Au + bv = (a, b).

Bez sumnje, postupak koji je opisao Euklid za određivanje zajedničke mjere dvije veličine u odnosu na brojeve (a zajednička mjera dva prirodna broja, očigledno je njihov najveći zajednički djelitelj) izmišljen je mnogo prije Euklida. Stari kineski matematičari su takođe pronašli GCD na isti način. I samo činjenica da je ovaj postupak postao poznat u renesansi iz "Principa" dao mu je naziv "Euklidov algoritam"

Najvjerovatnije je nastao iz komercijalne prakse starih trgovaca, kada su morali upoređivati ​​različite omjere cijelih brojeva. Kako, na primjer, možete uporediti omjere brojeva 3703700 i 1234567 i brojeva 22962965 i 7654321? Bilo je sasvim prirodno pokušati saznati koliko puta manji broj stane u veći. Lako je provjeriti da je 3703700 = 2 · 1234567 + 1234566, i 22962965 = 3 · 7654321 + 2. Sada je jasno da je omjer 3703700 prema 1234567 manji od omjera 92 i 25 koji sada zapisujemo 626 od 35. as

2,99999919 <= 3, 000000261,

Drevni kalkulatori objašnjeni dugom frazom.

Kada bismo morali da uporedimo bliže omjere brojeva, na primer, i, onda bi proračuni bili komplikovaniji:

71755875 = 61735500 + 10020375;

61735500 = 6 10020375 + 1613250;

10020375 = 6 1613250 + 340875;

1613250 = 4 * 340875 + 249750;

340875 = 249750 + 91125;

249750 = 2 * 91125 + 67500;

91125 = 67500 + 23625;

67500 = 22625 + 20250;

23625 = 20250 + 3375;

20250 = 63375.

Euklidov algoritam ovdje vam omogućava da odredite GCD brojeva 71755875 i 61735500, jednako 3375 i odgovara proširenju omjera od 71755875 do 61735500 u kontinuiranom razlomku:

Pokazalo se da je Euklidov algoritam ekvivalentan modernoj proceduri za proširenje broja u kontinuirani razlomak, a osim toga, omogućava da se „zaokruži“ omjer brojeva, tj. zamijeniti razlomak s velikim nazivnikom s razlomkom koji mu je vrlo blizak manjim nazivnikom. Zaista, izraz

jednak razlomku, u modernoj matematici se naziva "prikladnim razlomkom" proširenja omjera b = u kontinuirani (ili kontinuirani) razlomak.

To je jasno

b = 1 +< 1 + и б=1 + > 1+ = ,

ukoliko

Gore navedeno poređenje je napravljeno u III vijeku. BC. Aristarh sa Samosa u svojoj raspravi O udaljenosti i veličinama Mjeseca i Sunca.

Sada je poznato da su pogodni razlomci u proširenju kontinuiranog razlomka bilo kojeg (racionalnog ili iracionalnog) broja najbolje racionalne aproksimacije ovog broja.

Algoritmi sa polinomima

Euklidov algoritam je metoda za pronalaženje najvećeg zajedničkog djelitelja dva cijela broja, kao i dva polinoma u jednoj promjenljivoj...

Jedan od najstarijih matematičkih algoritama je Euklidov algoritam za pronalaženje najvećeg zajedničkog djelitelja dva pozitivna broja. Evo njegovog najjednostavnijeg oblika. Neka su data dva cijela broja. Ako su jednaki...

Analiza Euklidovog algoritma u Euklidskim prstenovima

Pre nego što nastavite sa analizom Euklidovog algoritma, razmotrite Fibonačijeve brojeve. Suština Fibonačijevog niza je da se počevši od 1.1 sljedeći broj dobije dodavanjem prethodna dva. 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ... ...

Istorija formiranja koncepta "algoritam". Najpoznatiji algoritmi u istoriji matematike

Euklidov algoritam je svestrana metoda koja izračunava najveći zajednički djelitelj dva pozitivna cijela broja. Opis algoritma za pronalaženje GCD dijeljenjem: 1. Podijelite veći broj manjim 2. Ako se podijeli bez ostatka...

Gausov celobrojni prsten

Koristimo uobičajenu definiciju najvećeg zajedničkog djelitelja za prstenove. GCD dva Gausova broja je njihov zajednički djelitelj, koji je djeljiv sa bilo kojim drugim zajedničkim djeliteljem. Kao i sa puno cijelih brojeva...

Matematičke osnove sistema rezidualnih klasa

Pogledajmo primjer. Neka je p = 6. Tada imamo šest klasa particije skupa cijelih brojeva po modulu 6: r = 0; r = 1; r = 2; r = 3; r = 4; r = 5; gdje r predstavlja ostatak dijeljenja cijelog broja sa 6 ...

Metode izučavanja polinoma u fakultativnoj nastavi u višem razredu srednje škole

Neka je prsten polinoma gotov. Definicija 1: Neka i, ako postoji polinom, onda je ostatak dijeljenja nula, tada se naziva djelitelj polinoma i označava se: () ...

Glavne faze formiranja i strukture moderne matematike

U III veku pre nove ere, Euklidova istoimena knjiga pojavila se u Aleksandriji u ruskom prevodu "Početaka". Termin "elementarna geometrija" nastao je od latinskog naziva "Počeci". Uprkos...

Na teritoriji određenog grada N nalaze se fabrike i prodavnice u koje se isporučuju proizvodi iz ovih fabrika. Kao rezultat razvoja, identificirane su moguće rute za postavljanje komunikacija i procijenjena je cijena njihove izrade za svaku rutu ...

Primjena metoda diskretne matematike u ekonomiji

Kompanija koja se bavi prevozom kvarljive robe treba da isporuči robu iz Suifenhea do Habarovska, a postoji nekoliko ruta kojima se može izvršiti dostava. Udaljenost između Suifenhea i City 2 je 15 km ...

Razvoj koncepta "prostora" i neeuklidske geometrije

Posebne metode za integraciju racionalnih izraza

Neka je potrebno pronaći GCD polinoma i. Bez gubitka opštosti, pretpostavićemo da stepen nije veći od stepena. Predstavljamo polinom u obliku: gdje je ostatak dijeljenja sa. Tada je stepen manji od stepena delioca. Dalje...

Rezidualna teorija

Rezidualna teorija

Definicija. Broj d ?? Z, koji istovremeno dijeli brojeve a, b, c, ..., k ?? Z, naziva se zajednički djelitelj ovih brojeva. Najveći d sa ovim svojstvom naziva se najveći zajednički djelitelj. Oznaka: d = (a, b, c, ..., k). Teorema. Ako je (a, b) = d ...

Rezidualna teorija

Neka je potrebno riješiti linearnu Diofantovu jednačinu: ax + by = c, gdje je a, b, c ?? Z; a i b nisu nule. Pokušajmo spekulirati gledajući ovu jednačinu. Neka (a, b) = d. Tada je a = a 1 d; b = b 1 d i jednačina izgleda ovako: a 1 d x + b 1 d y = c, tj. d (a 1 x + b 1 y) = c ...

Euklidov algoritam za pronalaženje GCD (najvećeg zajedničkog djelitelja)

Zadana su dva nenegativna cijela broja i. Potrebno je pronaći njihov najveći zajednički djelitelj, tj. najveći broj koji je djelitelj oba i, i. Na engleskom se "najveći zajednički djelitelj" piše "najveći zajednički djelitelj", a njegova uobičajena oznaka je:

(ovdje simbol "" označava djeljivost, tj. "" znači "dijeli")

Kada je jedan od brojeva jednak nuli, a drugi različit od nule, njihov najveći zajednički djelitelj, prema definiciji, bit će ovaj drugi broj. Kada su oba broja nula, rezultat je nedefinisan (bilo koji beskonačno veliki broj može), u ovom slučaju postavljamo najveći zajednički faktor na nulu. Stoga možemo govoriti o takvom pravilu: ako je jedan od brojeva jednak nuli, tada je njihov najveći zajednički djelitelj jednak drugom broju.

Euklidov algoritam, razmatran u nastavku, rješava problem nalaženja najvećeg zajedničkog djelitelja dva broja i za.

Ovaj algoritam je prvi put opisan u Euklidovoj knjizi "Počeci" (oko 300. godine prije Krista), iako je moguće da ovaj algoritam ima ranije porijeklo.

Algoritam

Sam algoritam je izuzetno jednostavan i opisan je sljedećom formulom:

Implementacija

int gcd (int a, int b) (ako (b == 0) vrati a; inače vrati gcd (b, a% b);)

Koristeći C++ ternarni uslovni operator, algoritam se može napisati još kraće:

int gcd (int a, int b) (povratak b? gcd (b, a% b): a;)

Konačno, evo nerekurzivnog oblika algoritma:

int gcd (int a, int b) (dok (b) (a% = b; swap (a, b);) vrati a;)

Dokaz o ispravnosti

Prvo, imajte na umu da sa svakom iteracijom Euklidovog algoritma njegov drugi argument striktno opada, stoga, budući da nije negativan, Euklidov algoritam uvek završava.

Za dokaz o ispravnosti to moramo pokazati za bilo koji>.

Pokažimo da je vrijednost na lijevoj strani jednakosti djeljiva sa stvarnom vrijednošću na desnoj strani, a vrijednost na desnoj je djeljiva sa vrijednošću na lijevoj strani. Očigledno, to će značiti da se leva i desna strana poklapaju, što će dokazati ispravnost Euklidovog algoritma.

Označavamo ... Zatim, po definiciji, i.

Ali onda iz ovoga sledi:

Dakle, prisjećajući se izjave, dobijamo sistem:

Koristimo sada sljedeću jednostavnu činjenicu: ako je za neka tri broja: i zadovoljeno, onda je i: istinito. U našoj situaciji dobijamo:

Ili, zamjenjujući njegovu definiciju kao umjesto toga, dobijamo:

Dakle, izvršili smo pola dokaza: pokazali smo da lijeva strana dijeli desnu. Druga polovina dokaza je slična.

Radni sati

Procjenjuje se vrijeme rada algoritma Laméova teorema, koji uspostavlja neverovatnu vezu između Euklidovog algoritma i Fibonačijevog niza:

Ako> i za neke, onda će Euklidov algoritam izvršiti najviše rekurzivnih poziva.

Razmotrite dvije glavne metode za pronalaženje GCD na dva glavna načina: korištenjem Euklidovog algoritma i faktoringom u proste faktore. Primijenimo obje metode za dva, tri ili više brojeva.

Euklidov algoritam za pronalaženje GCD

Euklidov algoritam olakšava izračunavanje najvećeg zajedničkog djelitelja za dva pozitivna broja. Formulacije i dokaz Euklidovog algoritma dali smo u odjeljku "Najveći zajednički djelitelj: determinanta, primjeri".

Suština algoritma je da se uzastopno izvrši dijeljenje s ostatkom, pri čemu se dobija niz jednakosti oblika:

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

Možemo završiti podjelu kada r k + 1 = 0, pri čemu r k = gcd (a, b).

Primjer 1

64 i 48 .

Rješenje

Uvedemo oznaku: a = 64, b = 48.

Na osnovu Euklidovog algoritma vršimo podjelu 64 na 48 .

Dobijamo 1 i ostatak od 16. Ispada da je q 1 = 1, r 1 = 16.

U drugom koraku dijelimo 48 do 16, dobijamo 3. To je q 2 = 3, a r 2 = 0. Dakle, broj 16 je najveći zajednički djelitelj za brojeve u uvjetu.

odgovor: GCD (64, 48) = 16.

Primjer 2

Šta je GCD brojeva 111 i 432 ?

Rješenje

Podijelite 432 na 111 ... Prema Euklidovom algoritmu dobijamo lanac jednakosti 432 = 111 3 + 99, 111 = 99 1 + 12, 99 = 12 8 + 3, 12 = 3 4.

Dakle, najveći zajednički djelitelj brojeva 111 i 432 Je 3.

odgovor: GCD (111, 432) = 3.

Primjer 3

Pronađite najveći zajednički imenilac za 661 i 113.

Rješenje

Izvršimo sekvencijalno dijeljenje brojeva i dobijemo gcd (661 , 113) = 1 ... To znači da su 661 i 113 međusobno prosti brojevi. To bismo mogli shvatiti prije nego što započnemo računanje ako pogledamo tablicu prostih brojeva.

odgovor: GCD (661, 113) = 1.

Pronalaženje gcd rastavljanjem brojeva u proste faktore

Da bi se metodom faktorizacije našao najveći zajednički djelitelj dva broja, potrebno je pomnožiti sve proste faktore koji se dobiju razlaganjem ova dva broja i koji su im zajednički.

Primjer 4

Ako brojeve 220 i 600 razložimo u proste faktore, dobićemo dva proizvoda: 220 = 2 2 5 11 i 600 = 2 2 2 3 5 5... Zajednički faktori za ova dva proizvoda će biti 2, 2 i 5. To znači da je GCD (220, 600) = 2 2 5 = 20.

Primjer 5

Pronađite najveći zajednički djelitelj brojeva 72 i 96 .

Rješenje

Pronađite sve proste faktore brojeva 72 i 96 :

72 36 18 9 3 1 2 2 2 3 3

96 48 24 12 6 3 1 2 2 2 2 2 3

Osnovni faktori zajednički za dva broja su 2, 2, 2 i 3. To znači da je GCD (72, 96) = 2 2 2 3 = 24.

odgovor: GCD (72, 96) = 24.

Pravilo za pronalaženje najvećeg zajedničkog djelitelja dva broja zasniva se na svojstvima najvećeg zajedničkog djelitelja, prema kojem je GCD (ma 1, mb 1) = m GCD (a 1, b 1), gdje je m bilo koji pozitivan cijeli broj .

Pronalaženje GCD od tri ili više brojeva

Bez obzira na broj brojeva za koje trebamo pronaći GCD, postupit ćemo po istom algoritmu koji se sastoji u sekvencijalnom pronalaženju GCD dva broja. Ovaj algoritam se zasniva na primeni sledeće teoreme: GCD više brojeva a 1, a 2,…, a k jednak broju d k, koji se nalazi u sekvencijalnom proračunu 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.

Primjer 6

Pronađite najveći zajednički faktor četiri broja 78, 294, 570 i 36 .

Rješenje

Hajde da uvedemo notaciju: a 1 = 78, a 2 = 294, a 3 = 570, a 4 = 36.

Počnimo s pronalaženjem GCD brojeva 78 i 294: d 2 = Gcd (78 , 294) = 6 .

Sada počnimo da pronađemo d 3 = gcd (d 2, a 3) = gcd (6, 570). Prema Euklidovom algoritmu 570 = 6 · 95. To znači da d 3 = Gcd (6 , 570) = 6 .

Naći d 4 = gcd (d 3, a 4) = gcd (6, 36). 36 je djeljiv sa 6 bez ostatka. Ovo nam omogućava da primamo d 4 = Gcd (6 , 36) = 6 .

d 4 = 6, odnosno gcd (78 , 294 , 570 , 36) = 6 .

odgovor:

Pogledajmo sada drugi način izračunavanja GCD za te i više brojeva. GCD možemo pronaći množenjem svih zajedničkih prostih faktora brojeva.

Primjer 7

Izračunajte gcd brojeva 78, 294, 570 i 36 .

Rješenje

Razložimo ove brojeve na proste faktore: 78 = 2 · 3 · 13, 294 = 2 · 3 · 7 · 7, 570 = 2 · 3 · 5 · 19, 36 = 2 · 2 · 3 · 3.

Za sva četiri broja, zajednički prosti faktori su 2 i 3.

Ispostavilo se da je GCD (78, 294, 570, 36) = 2 3 = 6.

odgovor: GCD (78, 294, 570, 36) = 6.

Pronalaženje gcd za negativne brojeve

Ako se moramo baviti negativnim brojevima, onda možemo koristiti apsolutne vrijednosti ovih brojeva da pronađemo najveći zajednički djelitelj. To možemo učiniti poznavanjem svojstava brojeva suprotnih predznaka: brojeva n i - n imaju iste djelitelje.

Primjer 8

Pronađite gcd negativnih cijelih brojeva − 231 i − 140 .

Rješenje

Da biste izvršili proračune, uzmite module brojeva datih u uslovu. To će biti brojevi 231 i 140. Napišimo to ukratko: GCD (− 231 , − 140) = GCD (231, 140). Sada ćemo primijeniti Euklidov algoritam da pronađemo proste faktore dva broja: 231 = 140 · 1 + 91; 140 = 91 * 1 + 49; 91 = 49 * 1 + 42; 49 = 42 1 + 7 i 42 = 7 6... Dobijamo da je gcd (231, 140) = 7 .

I od GCD (− 231 , − 140) = Gcd (231 , 140) , zatim gcd brojevi − 231 i − 140 je jednako sa 7 .

odgovor: GCD (- 231, - 140) = 7.

Primjer 9

Odredite GCD tri broja - 585, 81 i − 189 .

Rješenje

Negativne brojeve u gornjoj listi zamijenimo njihovim apsolutnim vrijednostima, dobićemo GCD (− 585 , 81 , − 189) = Gcd (585 , 81 , 189) ... Zatim sve ove brojeve rastavljamo na proste faktore: 585 = 3 3 5 13, 81 = 3 3 3 3 i 189 = 3 3 3 7... Tri broja imaju zajedničke proste faktore 3 i 3. Ispada da je GCD (585, 81, 189) = GCD (- 585, 81, - 189) = 9.

odgovor: GCD (- 585, 81, - 189) = 9.

Ako primijetite grešku u tekstu, odaberite je i pritisnite Ctrl + Enter

Najveći zajednički djelitelj

Definicija 2

Ako je prirodan broj a djeljiv prirodnim brojem $ b $, tada se $ b $ naziva djelitelj $ a $, a $ a $ se naziva višekratnik $ b $.

Neka su $ a $ i $ b $ prirodni brojevi. Broj $ c $ naziva se zajedničkim djeliteljem i za $ a $ i $ b $.

Skup zajedničkih djelitelja za $ a $ i $ b $ je konačan, jer nijedan od ovih djelitelja ne može biti veći od $ a $. To znači da među ovim djeliteljima postoji najveći, koji se naziva najveći zajednički djelitelj brojeva $ a $ i $ b $, a za označavanje se koristi notacija:

$ Gcd \ (a; b) \ ili \ D \ (a; b) $

Da biste pronašli najveći zajednički djelitelj dva broja, trebate:

1. Pronađite proizvod brojeva pronađenih u koraku 2. Rezultirajući broj će biti željeni najveći zajednički faktor.

Primjer 1

Pronađite gcd brojeva $ 121 $ i $ 132. $

242 $ = 2 \ cdot 11 \ cdot 11 $

$ 132 = 2 \ cdot 2 \ cdot 3 \ cdot 11 $

Odaberite brojeve koji su uključeni u dekompoziciju ovih brojeva

242 $ = 2 \ cdot 11 \ cdot 11 $

$ 132 = 2 \ cdot 2 \ cdot 3 \ cdot 11 $

Pronađite proizvod brojeva pronađenih u koraku 2. Rezultirajući broj će biti željeni najveći zajednički faktor.

$ Gcd = 2 \ cdot 11 = 22 $

Primjer 2

Pronađite GCD monoma od 63$ i 81$.

Pronaći ćemo prema predstavljenom algoritmu. Za ovo:

Rastaviti brojeve na proste faktore

$63 = 3 \ cdot 3 \ cdot 7 $

$81 = 3 \ cdot 3 \ cdot 3 \ cdot 3 $

Biramo brojeve koji su uključeni u dekompoziciju ovih brojeva

$63 = 3 \ cdot 3 \ cdot 7 $

$81 = 3 \ cdot 3 \ cdot 3 \ cdot 3 $

Nađimo proizvod brojeva pronađenih u koraku 2. Rezultirajući broj će biti željeni najveći zajednički faktor.

$ Gcd = 3 \ cdot 3 = 9 $

GCD dva broja možete pronaći na drugi način, koristeći skup djelitelja brojeva.

Primjer 3

Pronađite GCD brojeva $48$ i $60$.

Rješenje:

Pronađite skup djelitelja broja $ 48 $: $ \ lijevo \ ((\ rm 1,2,3.4.6,8,12,16,24,48) \ desno \) $

Sada nalazimo skup djelitelja broja $ 60 $: $ \ \ lijevo \ ((\ rm 1,2,3,4,5,6,10,12,15,20,30,60) \ desno \ ) $

Nađimo presjek ovih skupova: $ \ lijevo \ ((\ rm 1,2,3,4,6,12) \ desno \) $ - ovaj skup će odrediti skup zajedničkih djelitelja brojeva $ 48 $ i 60 $. Najveći element u ovom skupu će biti broj $12$. Dakle, najveći zajednički djelitelj 48 dolara i 60 dolara bit će 12 dolara.

Definicija LCM

Definicija 3

Zajednički višekratnik prirodnih brojeva$ a $ i $ b $ je prirodan broj koji je višekratnik i $ a $ i $ b $.

Uobičajeni višekratnici su brojevi koji su djeljivi sa originalom bez ostatka. Na primjer, za brojeve 25 $ i 50 $, zajednički višekratnici će biti brojevi 50,100,150,200, itd.

Najmanji zajednički višekratnik će se zvati najmanji zajednički višekratnik i označavati ga sa LCM $ (a; b) $ ili K $ (a; b).

Da biste pronašli LCM dva broja, trebate:

1. Brojevi faktora
2. Napišite faktore koji su dio prvog broja i dodajte im faktore koji su dio drugog i ne ulaze u prvi

Primjer 4

Pronađite LCM brojeva $99$ i $77$.

Pronaći ćemo prema predstavljenom algoritmu. Za ovo

Brojevi faktora

99 $ = 3 \ cdot 3 \ cdot 11 $

Napišite faktore uključene u prvi

dodajte im faktore koji su dio drugog i ne ulaze u prvi

Pronađite proizvod brojeva pronađenih u koraku 2. Rezultirajući broj će biti željeni najmanji zajednički višekratnik

$ LCM = 3 \ cdot 3 \ cdot 11 \ cdot 7 = 693 $

Sastavljanje lista djelitelja brojeva često oduzima mnogo vremena. Postoji način da se pronađe GCD koji se zove Euklidov algoritam.

Izjave na kojima se zasniva Euklidov algoritam:

Ako su $ a $ i $ b $ prirodni brojevi, a $ a \ vdots b $, onda je $ D (a; b) = b $

Ako su $ a $ i $ b $ prirodni brojevi takvi da je $ b

Koristeći $ D (a; b) = D (a-b; b) $, možemo sukcesivno smanjivati ​​razmatrane brojeve sve dok ne dođemo do takvog para brojeva da je jedan od njih djeljiv drugim. Tada će manji od ovih brojeva biti željeni najveći zajednički djelitelj za brojeve $ a $ i $ b $.

Svojstva GCD i LCM

1. Bilo koji zajednički višekratnik $ a $ i $ b $ je djeljiv sa K $ (a; b) $
2. Ako je $ a \ vdots b $, onda je K $ (a; b) = a $

Ako je K $ (a; b) = k $ i $ m $ prirodan broj, onda je K $ (am; bm) = km $

Ako je $ d $ zajednički djelitelj za $ a $ i $ b $, tada je K ($ \ frac (a) (d); \ frac (b) (d) $) = $ \ \ frac (k) (d ) $

Ako je $ a \ vdots c $ i $ b \ vdots c $, tada je $ \ frac (ab) (c) $ zajednički višekratnik $ a $ i $ b $

Za bilo koje prirodne brojeve $ a $ i $ b $, jednakost

$ D (a; b) \ cdot K (a; b) = ab $

Svaki zajednički djelitelj brojeva $a$ i $b$ je djelitelj broja $D (a; b) $