Evklidov algoritem in njegove modifikacije. Evklidov algoritem

Evklidov algoritem Je algoritem za iskanje največjega skupnega delitelja (GCD) para celih števil.

Največji skupni delitelj (GCD) Je število, ki deli dve števili brez ostanka in se brez ostanka deli s katerim koli drugim delilcem teh dveh števil. Preprosto povedano, to je največje število, s katerim je mogoče dve številki, za katera se išče GCD, deliti brez ostanka.

Algoritem za iskanje GCD z deljenjem

1. Večje število delimo z manjšim.
2. Če je deljeno brez preostanka, je manjše število GCD (cikel bi morali zapustiti).
3. Če obstaja ostanek, se večje število nadomesti s preostankom deljenja.
4. Gremo do točke 1.

Primer:
Poiščite GCD za 30 in 18.
30/18 = 1 (preostalo 12)
18/12 = 1 (preostanek 6)
12/6 = 2 (preostanek 0)
Konec: GCD je delilec 6.
GCD (30, 18) = 6

a = 50 b = 130, medtem ko a! = 0 in b! = 0: če a> b: a = a% b drugače: b = b% a natis (a + b)

V zanki se preostanek delitve zapiše v spremenljivko a ali b. Cikel se konča, ko je vsaj ena od spremenljivk enaka nič. To pomeni, da druga vsebuje GCD. Katerega pa, ne vemo. Zato za GCD najdemo vsoto teh spremenljivk. Ker je ena od spremenljivk nič, to ne vpliva na rezultat.

Algoritem za iskanje GCD z odštevanjem

1. Od večjega števila odštejemo manjše.
2. Če se izkaže, da je 0, to pomeni, da so številke med seboj enake in so GCD (iz cikla bi morali zapustiti).
3. Če rezultat odštevanja ni 0, se večje število nadomesti z rezultatom odštevanja.
4. Gremo do točke 1.

Primer:
Poiščite GCD za 30 in 18.
30 - 18 = 12
18 - 12 = 6
12 - 6 = 6
6 - 6 = 0
Konec: GCD se odšteje ali odšteje.
GCD (30, 18) = 6

a = 50 b = 130 medtem ko a! = b: če a> b: a = a - b drugače: b = b - tisk (a)

1.1 Uporaba Evklidovega algoritma

Kot vsako dobro opravljeno delo tudi Euclidov algoritem daje veliko več, kot je bilo prvotno pričakovano, da bo iz njega dobil. Če pogledamo, je na primer jasno, da množica deliteljev a in b sovpada z množico deliteljev (a, b). Prav tako daje praktičen način iskanja števil u in v iz Z (ali, če želite, iz izreka 2. točke), tako da

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

Dejansko imamo iz verige enakosti:

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

(gremo po verigi enakosti od spodaj navzgor, izrazimo preostanek vsake naslednje enakosti in ga nadomestimo z izrazom, ki ga dobimo do tega trenutka)

Au + bv = (a, b).

Nedvomno je bil postopek, ki ga je opisal Evklid za določanje skupne mere dveh veličin glede na števila (in skupna mera dveh naravnih števil je očitno njihov največji skupni delilec), izumil že veliko pred Evklidom. Starodavni kitajski matematiki so prav tako našli GCD na enak način. In samo dejstvo, da je ta postopek postal znan v renesansi iz "Načel", mu je dalo ime "Evklidov algoritem"

Najverjetneje je nastala iz poslovne prakse starodavnih trgovcev, ko so morali primerjati različna razmerja celih števil. Kako lahko na primer primerjate razmerja števil 3703700 in 1234567 ter številk 22962965 in 7654321? Povsem naravno je bilo poskusiti ugotoviti, kolikokrat manjše število paše v večje. Preprosto je preveriti, da je 3703700 = 2 · 1234567 + 1234566 in 22962965 = 3 · 7654321 + 2. Zdaj je jasno, da je razmerje med 3703700 in 1234567 manjše od razmerja 9 in 265, ki ga zdaj pišemo 265. kot

2,99999919 <= 3, 000000261,

Starodavni kalkulatorji so razloženi z dolgo besedno zvezo.

Če bi morali na primer primerjati tesnejša razmerja številk in, bi bili izračuni bolj zapleteni:

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 algoritem tukaj vam omogoča, da določite GCD številk 71755875 in 61735500, ki je enak 3375 in ustreza razširitvi razmerja 71755875 do 61735500 v neprekinjenem ulomku:

Euklidov algoritem se izkaže za enakovreden sodobnemu postopku za razširitev števila v neprekinjen ulomek, poleg tega pa omogoča, da "zaokrožimo" razmerje števil, t.j. zamenjaj ulomek z velikim imenovalcem z ulomkom, ki mu je zelo blizu, z manjšim imenovalcem. Pravzaprav izraz

enako ulomku, se v sodobni matematiki imenuje "primeren ulomek" razširitve razmerja b = v neprekinjen (ali kontinuiran) ulomek.

To je jasno

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

v kolikor

Zgornja primerjava je bila narejena v III stoletju. pr. Aristarh iz Samosa v svoji razpravi O razdalji in velikostih lune in sonca.

Zdaj je znano, da so primerni ulomki v razširjanju neprekinjenih ulomkov katerega koli (racionalnega ali iracionalnega) števila najboljši racionalni približki tega števila.

Algoritmi s polinomi

Euklidov algoritem je metoda za iskanje največjega skupnega delitelja dveh celih števil, pa tudi dveh polinomov v eni spremenljivki ...

Eden najstarejših matematičnih algoritmov je Evklidov algoritem za iskanje največjega skupnega delitelja dveh pozitivnih števil. Tukaj je njegova najpreprostejša oblika. Naj sta podani dve celi števili. Če sta enaka...

Analiza evklidskega algoritma v evklidskih obročkih

Preden nadaljujete z analizo evklidskega algoritma, upoštevajte Fibonaccijeva števila. Bistvo Fibonaccijevega zaporedja je, da od 1.1 dobimo naslednjo številko s seštevanjem prejšnjih dveh. 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ... ...

Zgodovina nastanka koncepta "algoritem". Najbolj znani algoritmi v zgodovini matematike

Evklidov algoritem je vsestranska metoda, ki izračuna največji skupni delitelj dveh pozitivnih celih števil. Opis algoritma za iskanje GCD z deljenjem: 1. Večje število delimo z manjšim 2. Če je deljeno brez ostanka ...

Gaussov celoštevilski prstan

Za obroče uporabljamo običajno definicijo največjega skupnega delitelja. GCD dveh Gaussovih števil je njun skupni delitelj, ki je deljiv s katerim koli drugim skupnim deliteljem. Kot pri veliko celih številih ...

Matematični temelji sistema rezidualnih razredov

Poglejmo primer. Naj je p = 6. Potem imamo šest razredov particije množice celih števil po modulu 6: r = 0; r = 1; r = 2; r = 3; r = 4; r = 5; kjer r pomeni preostanek deljenja celega števila s 6 ...

Metode preučevanja polinomov pri izbirnem pouku v višjih razredih srednje šole

Naj bo krog polinomov končan. Definicija 1: Naj in, če obstaja polinom, je preostanek delitve nič, potem se imenuje delilec polinoma in je označen: () ...

Glavne faze oblikovanja in strukture sodobne matematike

V III stoletju pred našim štetjem se je v Aleksandriji v ruskem prevodu "Začetki" pojavila Evklidova knjiga z istim imenom. Izraz "elementarna geometrija" izvira iz latinskega imena "začetki". Kljub...

Na ozemlju določenega mesta N se nahajajo tovarne in trgovine, v katere se dobavljajo izdelki iz teh tovarn. Kot rezultat razvoja so bile opredeljene možne poti za polaganje komunikacij in ocenjeni stroški njihove izdelave za vsako pot ...

Uporaba metod diskretne matematike v ekonomiji

Podjetje, ki se ukvarja s prevozom pokvarljivega blaga, mora dostaviti blago iz Suifenheja v Habarovsk, in obstaja več poti, po katerih je mogoče dostaviti. Razdalja med Suifenhe in City 2 je 15 km ...

Razvoj koncepta "prostora" in neevklidske geometrije

Posebne metode za integracijo racionalnih izrazov

Naj je treba najti GCD polinomov in. Brez izgube splošnosti bomo domnevali, da stopnja ni višja od stopnje. Polinom predstavljamo v obliki: kjer je preostanek deljenja z. Potem je stopnja manjša od stopnje delitelja. Nadalje ...

Rezidualna teorija

Rezidualna teorija

Opredelitev. Število d ?? Z, ki hkrati deli števila a, b, c, ..., k ?? Z, se imenuje skupni delilec teh števil. Največji d s to lastnostjo se imenuje največji skupni delilec. Zapis: d = (a, b, c, ..., k). Izrek. Če (a, b) = d ...

Rezidualna teorija

Naj bo potrebno rešiti linearno diofantovo enačbo: ax + by = c, kjer je a, b, c ?? Z; a in b nista ničli. Poskusimo špekulirati s pogledom na to enačbo. Naj (a, b) = d. Potem je a = a 1 d; b = b 1 d in enačba izgleda takole: a 1 d x + b 1 d y = c, tj. d (a 1 x + b 1 y) = c ...

Evklidov algoritem za iskanje GCD (največji skupni delilec)

Podani sta dve nenegativni celi števili in. Treba je najti njihov največji skupni delitelj, tj. največje število, ki je delilec obeh in, in. V angleščini se "največji skupni delilec" piše "največji skupni delitelj", njegova skupna oznaka pa je:

(tukaj simbol "" označuje deljivost, t.j. "" pomeni "deli")

Ko je eno od števil enako nič, drugo pa ni nič, bo njihov največji skupni delilec po definiciji to drugo število. Ko sta obe številki nič, je rezultat nedefiniran (primerno je vsako neskončno veliko število), v tem primeru nastavimo največji skupni delitelj na nič. Zato lahko govorimo o takem pravilu: če je eno od števil enako nič, je njihov največji skupni delilec enak drugemu številu.

Evklidov algoritem, obravnavan v nadaljevanju, rešuje problem iskanja največjega skupnega delitelja dveh števil in za.

Ta algoritem je bil prvič opisan v Evklidovi knjigi "Začetki" (približno 300 pr.n.št.), čeprav je verjetno, da ima ta algoritem zgodnejši izvor.

algoritem

Sam algoritem je izjemno preprost in je opisan z naslednjo formulo:

Izvajanje

int gcd (int a, int b) (če (b == 0) vrni a; sicer vrni gcd (b, a% b);)

Z uporabo ternarnega pogojnega operaterja C ++ lahko algoritem zapišemo še krajše:

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

Končno je tu še nerekurzivna oblika algoritma:

int gcd (int a, int b) (medtem ko (b) (a% = b; zamenjaj (a, b);) vrni a;)

Dokaz o pravilnosti

Prvič, upoštevajte, da se z vsako ponovitvijo evklidskega algoritma njegov drugi argument strogo zmanjša, zato, ker ni negativen, evklidski algoritem vedno konča.

Za dokazilo o pravilnosti to moramo pokazati za vse>.

Pokažimo, da je vrednost na levi strani enakosti deljiva z realno vrednostjo na desni, vrednost na desni pa je deljiva z vrednostjo na levi. Očitno bo to pomenilo, da leva in desna stran sovpadata, kar bo dokazalo pravilnost Evklidovega algoritma.

Označujemo ... Potem po definiciji in.

Ampak potem iz tega sledi:

Torej, če se spomnimo izjave, dobimo sistem:

Uporabimo zdaj naslednje preprosto dejstvo: če je za nekatera tri števila: in je izpolnjeno, potem je in: res. V naši situaciji dobimo:

Ali, če namesto tega nadomestimo njegovo definicijo, dobimo:

Torej, izvedli smo polovico dokaza: pokazali smo, da leva stran deli desno. Druga polovica dokaza je podobna.

Delovni čas

Ocenjen je čas delovanja algoritma Laméjev izrek, ki vzpostavlja neverjetno povezavo med evklidskim algoritmom in Fibonaccijevim zaporedjem:

Če> in za nekatere, potem bo Evklidov algoritem opravil največ rekurzivnih klicev.

Razmislite o dveh glavnih metodah za iskanje GCD na dva glavna načina: z uporabo evklidskega algoritma in z faktorjenjem v prafaktorje. Uporabimo obe metodi za dve, tri ali več številk.

Evklidov algoritem za iskanje GCD

Euklidov algoritem olajša izračun največjega skupnega delitelja za dve pozitivni števili. Formulacije in dokaz Evklidovega algoritma smo podali v poglavju "Največji skupni delilec: determinanta, primeri".

Bistvo algoritma je zaporedno izvajanje delitve s preostankom, med katerim se dobijo številne enakosti v obliki:

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

Delitev lahko končamo, ko r k + 1 = 0, pri čemer r k = gcd (a, b).

Primer 1

64 in 48 .

Rešitev

Uvedemo zapis: a = 64, b = 48.

Na podlagi evklidskega algoritma izvedemo delitev 64 na 48 .

Dobimo 1 in preostanek 16. Izkazalo se je, da je q 1 = 1, r 1 = 16.

V drugem koraku razdelimo 48 do 16 dobimo 3. to je q 2 = 3, a r 2 = 0. Tako je število 16 največji skupni delilec za števila v pogoju.

odgovor: GCD (64, 48) = 16.

Primer 2

Kaj je GCD številk 111 in 432 ?

Rešitev

Razdeli 432 na 111 ... Po Euclidovem algoritmu dobimo verigo enakosti 432 = 111 3 + 99, 111 = 99 1 + 12, 99 = 12 8 + 3, 12 = 3 4.

Tako je največji skupni delilec števil 111 in 432 je 3.

odgovor: GCD (111, 432) = 3.

Primer 3

Poiščite največji skupni imenovalec 661 in 113.

Rešitev

Izvedemo zaporedno delitev števil in dobimo gcd (661 , 113) = 1 ... To pomeni, da sta 661 in 113 sopraprosti števili. To bi lahko ugotovili pred začetkom izračuna, če bi pogledali tabelo praštevil.

odgovor: GCD (661, 113) = 1.

Iskanje gcd s faktorjenjem števil v prafaktorje

Da bi z metodo faktorizacije poiskali največji skupni delilec dveh števil, je treba pomnožiti vse prafaktorje, ki jih dobimo z razgradnjo teh dveh števil in so jima skupni.

Primer 4

Če številki 220 in 600 razdelimo v prafaktorje, dobimo dva produkta: 220 = 2 2 5 11 in 600 = 2 2 2 3 5 5... Skupni dejavniki teh dveh izdelkov bodo 2, 2 in 5. To pomeni, da je GCD (220, 600) = 2 2 5 = 20.

Primer 5

Poiščite največji skupni delilec števil 72 in 96 .

Rešitev

Poišči vse prafaktorje števil 72 in 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

Primarni faktorji, skupni dvema številkama, so 2, 2, 2 in 3. To pomeni, da je GCD (72, 96) = 2 2 2 3 = 24.

odgovor: GCD (72, 96) = 24.

Pravilo za iskanje največjega skupnega delitelja dveh števil temelji na lastnostih največjega skupnega delitelja, po katerem je GCD (ma 1, mb 1) = m GCD (a 1, b 1), kjer je m katero koli pozitivno celo število .

Iskanje GCD treh ali več številk

Ne glede na število številk, za katere moramo najti GCD, bomo ravnali po istem algoritmu, ki je sestavljen iz zaporednega iskanja GCD dveh številk. Ta algoritem temelji na uporabi naslednjega izreka: GCD več številk a 1, a 2,…, a k enako številu d k, ki ga najdemo v zaporednem izrač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.

Primer 6

Poiščite največji skupni faktor štirih števil 78, 294, 570 in 36 .

Rešitev

Uvedemo zapis: a 1 = 78, a 2 = 294, a 3 = 570, a 4 = 36.

Začnimo z iskanjem GCD številk 78 in 294: d 2 = Gcd (78 , 294) = 6 .

Zdaj začnimo iskati d 3 = gcd (d 2, a 3) = gcd (6, 570). Po Evklidovem algoritmu 570 = 6 · 95. To pomeni d 3 = Gcd (6 , 570) = 6 .

Poiščite d 4 = gcd (d 3, a 4) = gcd (6, 36). 36 je brez ostanka deljivo s 6. To nam omogoča prejemanje d 4 = Gcd (6 , 36) = 6 .

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

odgovor:

Zdaj pa poglejmo drug način za izračun GCD za te in več številk. GCD lahko najdemo tako, da pomnožimo vse skupne pra faktorje števil.

Primer 7

Izračunaj gcd številk 78, 294, 570 in 36 .

Rešitev

Razstavimo ta števila na prafaktorje: 78 = 2 · 3 · 13, 294 = 2 · 3 · 7 · 7, 570 = 2 · 3 · 5 · 19, 36 = 2 · 2 · 3 · 3.

Za vsa štiri števila sta skupna pra faktorja 2 in 3.

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

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

Iskanje gcd za negativna števila

Če se moramo ukvarjati z negativnimi števili, potem lahko uporabimo absolutne vrednosti teh številk, da poiščemo največji skupni delilec. To lahko storimo tako, da poznamo lastnost števil z nasprotnimi predpisi: števila n in - n imajo enake delilnike.

Primer 8

Poiščite gcd negativnih celih števil − 231 in − 140 .

Rešitev

Za izračune vzemite module številk, podanih v pogoju. To bosta številki 231 in 140. Naj na kratko zapišemo: GCD (− 231 , − 140) = GCD (231, 140). Zdaj bomo uporabili Evklidov algoritem za iskanje prafaktorjev dveh števil: 231 = 140 · 1 + 91; 140 = 91 * 1 + 49; 91 = 49 * 1 + 42; 49 = 42 1 + 7 in 42 = 7 6... Dobimo, da je gcd (231, 140) = 7 .

In od GCD (− 231 , − 140) = Gcd (231 , 140) , nato številke gcd − 231 in − 140 je enako 7 .

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

Primer 9

Določite GCD treh številk - 585, 81 in − 189 .

Rešitev

Negativna števila na zgornjem seznamu zamenjamo z njihovimi absolutnimi vrednostmi, dobimo GCD (− 585 , 81 , − 189) = Gcd (585 , 81 , 189) ... Nato vsa ta števila razstavimo na prafaktorje: 585 = 3 3 5 13, 81 = 3 3 3 3 in 189 = 3 3 3 7... Vsem trem številom sta skupna pra faktorja 3 in 3. Izkazalo se je, da je GCD (585, 81, 189) = GCD (- 585, 81, - 189) = 9.

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

Če opazite napako v besedilu, jo izberite in pritisnite Ctrl + Enter

Največji skupni delilec

Opredelitev 2

Če je naravno število a deljivo z naravnim številom $ b $, potem $ b $ imenujemo delilec $ a $, $ a $ pa večkratnik $ b $.

Naj sta $ a $ in $ b $ naravni števili. Število $ c $ se imenuje skupni delilec za $ a $ in $ b $.

Množica skupnih deliteljev za $ 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 se imenuje največji skupni delilec števil $ a $ in $ b $, za označevanje pa se uporablja zapis:

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

Če želite najti največji skupni delilec dveh števil, morate:

1. Poiščite zmnožek števil, najdenih v koraku 2. Dobljeno število bo želeni največji skupni faktor.

Primer 1

Poiščite gcd številk $ 121 $ in $ 132. $

242 $ = 2 \ cdot 11 \ cdot 11 $

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

Izberite številke, ki so vključene v razgradnjo teh številk

242 $ = 2 \ cdot 11 \ cdot 11 $

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

Poiščite zmnožek števil, najdenih v koraku 2. Dobljeno število bo želeni največji skupni faktor.

$ Gcd = 2 \ cdot 11 = 22 $

Primer 2

Poiščite GCD monomov 63 $ in 81 $.

Poiskali bomo po predstavljenem algoritmu. Za to:

Razčlenite števila na prafaktorje

63 $ = 3 \ cdot 3 \ cdot 7 $

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

Izberemo števila, ki so vključena v razgradnjo teh števil

63 $ = 3 \ cdot 3 \ cdot 7 $

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

Poiščimo zmnožek številk, ki jih najdemo v koraku 2. Dobljeno število bo želeni največji skupni faktor.

$ Gcd = 3 \ cdot 3 = 9 $

GCD dveh številk lahko najdete na drug način, z uporabo nabora deliteljev števil.

Primer 3

Poiščite GCD številk 48 $ in 60 $.

rešitev:

Poiščite množico deliteljev števila $ 48 $: $ \ levo \ ((\ rm 1,2,3.4.6,8,12,16,24,48) \ desno \) $

Zdaj najdemo množico deliteljev števila $ 60 $: $ \ \ levo \ ((\ rm 1,2,3,4,5,6,10,12,15,20,30,60) \ desno \ ) $

Poiščimo presečišče teh množic: $ \ levo \ ((\ rm 1,2,3,4,6,12) \ desno \) $ - ta množica bo določila množico skupnih deliteljev števil $ 48 $ in 60 $. Največji element v tem nizu bo številka 12 $. Torej bo največji skupni delilec 48 $ in 60 $ 12 $.

Opredelitev LCM

Opredelitev 3

Skupni večkratnik naravnih števil$ a $ in $ b $ je naravno število, ki je večkratnik tako $ a $ kot $ b $.

Navadni večkratniki števil so števila, ki jih je mogoče deliti 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 se imenuje najmanjši skupni večkratnik in ga označimo z LCM $ (a; b) $ ali K $ (a; b).

Če želite najti LCM dveh številk, potrebujete:

1. Številke faktorjev
2. Zapišite faktorje, ki so del prvega števila, in jim dodajte faktorje, ki so del drugega in ne gredo v prvo

Primer 4

Poiščite LCM številk 99 $ in 77 $.

Poiskali bomo po predstavljenem algoritmu. Za to

Številke faktorjev

99 $ = 3 \ cdot 3 \ cdot 11 $

Napišite dejavnike, ki so vključeni v prvi

dodajte jim dejavnike, ki so del drugega in ne gredo v prvo

Poiščite zmnožek številk, ki jih najdete v 2. koraku. Dobljeno število bo želeni najmanjši skupni večkratnik

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

Sestavljanje seznamov številskih deliteljev je pogosto zelo zamudno. Obstaja način za iskanje GCD, imenovan Evklidov algoritem.

Izjave, na katerih temelji Evklidov algoritem:

Če sta $ a $ in $ b $ naravna števila in $ a \ vdots b $, potem je $ D (a; b) = b $

Če sta $ a $ in $ b $ naravni števili, tako da je $ b

Z uporabo $ D (a; b) = D (a-b; b) $ lahko zaporedoma zmanjšujemo obravnavana števila, dokler ne dosežemo takšnega para števil, da je eno od njih deljivo z drugim. Potem bo manjše od teh številk želeni največji skupni delilec za števili $ a $ in $ b $.

Lastnosti GCD in LCM

1. Vsak skupni večkratnik $ a $ in $ b $ je deljiv s K $ (a; b) $
2. Če je $ a \ vdots 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 delilec za $ a $ in $ b $, potem je K ($ \ frac (a) (d); \ frac (b) (d) $) = $ \ \ frac (k) (d ) $

Če je $ a \ vdots c $ in $ b \ vdots c $, potem je $ \ frac (ab) (c) $ skupni večkratnik $ a $ in $ b $

Za poljubna naravna števila $ a $ in $ b $ velja enakost

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

Vsak skupni delilec števil $ a $ in $ b $ je delilec števila $ D (a; b) $