Eukleidese algoritm on algoritm täisarvude paari suurima ühisjagaja (gcd) leidmiseks.

suurim ühine jagaja(GCD) on arv, mis jagab kahte arvu ilma jäägita ja jagub ise ilma jäägita antud kahe arvu ühegi teise jagajaga. Lihtsamalt öeldes on see suur number, mille abil saab kaks arvu, mille jaoks gcd-d otsitakse, jagada ilma jäägita.

Algoritm GCD leidmiseks jagamise teel

1. Jagage suurem arv väiksemaga.
2. Kui see jagatakse ilma jäägita, on väiksem arv GCD (peaksite tsüklist väljuma).
3. Kui jääb üle, siis rohkem asendatakse ülejäänud jaoskonnaga.
4. Liigume edasi punkti 1 juurde.

Näide:
Leidke GCD 30 ja 18 jaoks.
30/18 = 1 (ülejäänud 12)
18/12 = 1 (ülejäänud 6)
12/6 = 2 (ülejäänud 0)
Lõpp: GCD on 6 jagaja.
gcd(30, 18) = 6

a = 50 b = 130, samas kui a != 0 ja b != 0 : kui a > b: a = a % b else : b = b % a print (a + b)

Tsüklis kirjutatakse jaotuse jääk muutujale a või b. Tsükkel lõpeb, kui vähemalt üks muutujatest on null. See tähendab, et teine ​​sisaldab GCD-d. Siiski me ei tea, milline. Seetõttu leiame GCD jaoks nende muutujate summa. Kuna üks muutujatest on null, ei mõjuta see tulemust.

Algoritm GCD leidmiseks lahutamise teel

1. Lahutage suuremast arvust väiksem.
2. Kui see osutub 0, tähendab see, et arvud on üksteisega võrdsed ja on GCD (peaksite tsüklist väljuma).
3. Kui lahutamise tulemus ei võrdu 0-ga, siis asendatakse suurem arv lahutamise tulemusega.
4. Liigume edasi punkti 1 juurde.

Näide:
Leidke GCD 30 ja 18 jaoks.
30 - 18 = 12
18 - 12 = 6
12 - 6 = 6
6 - 6 = 0
Lõpp: GCD on minuend või alaosa.
gcd(30, 18) = 6

a = 50 b = 130, samas kui a != b: kui a > b: a = a - b else : b = b - a print (a)

Eukleidese algoritm GCD (suurim ühine jagaja) leidmiseks

Arvestades kaks mittenegatiivset täisarvu ja . On vaja leida nende suurim ühine jagaja, s.o. suurim arv, mis on jagaja nii ja Ja . peal inglise keel"suurim ühine jagaja" on kirjutatud "suurim ühine jagaja" ja selle ühine tähistus on:

(siin tähistab "" jagatavust, st "" tähistab "jagab")

Kui üks arvudest on võrdne nulliga ja teine ​​on nullist erinev, on nende suurim ühine jagaja definitsiooni järgi see teine ​​arv. Kui mõlemad arvud on nullid, on tulemus määratlemata (sobib iga lõpmata suur arv), sel juhul seame suurima ühisjagaja nulliks. Seetõttu võime rääkida sellisest reeglist: kui üks arvudest on võrdne nulliga, siis on nende suurim ühisjagaja võrdne teise arvuga.

Eukleidese algoritm, mida arutatakse allpool, lahendab kahe arvu ja jaoks suurima ühise jagaja leidmise ülesande.

Seda algoritmi kirjeldati esmakordselt raamatus Euclid's Elements (umbes 300 eKr), kuigi on täiesti võimalik, et sellel algoritmil on varasem päritolu.

Algoritm

Algoritm ise on äärmiselt lihtne ja seda kirjeldatakse järgmise valemiga:

Rakendamine

int gcd (int a, int b) ( kui (b == 0 ) tagastab a; muidu tagastab gcd (b, a % b) ; )

Kasutades kolmepoolset tingimuslikku operaatorit C++, saab algoritmi kirjutada veelgi lühemalt:

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

Lõpuks anname algoritmi mitterekursiivse vormi:

int gcd (int a, int b) ( while (b) ( a % = b; vahetus (a, b) ; ) tagastab a; )

Õigsuse tõend

Esiteks pange tähele, et iga Eukleidilise algoritmi iteratsiooniga väheneb selle teine ​​argument rangelt, seega kuna see on mittenegatiivne, siis Eukleidilise algoritmi alati lõpeb.

Sest õigsuse tõendid peame seda näitama mis tahes > puhul.

Näitame, et võrduse vasakpoolne väärtus jagub parempoolse tegelikuga ja parempoolne väärtus vasakpoolse väärtusega. Ilmselt tähendab see seda, et vasak ja parem osa on samad, mis tõestab Eukleidese algoritmi õigsust.

Tähistage . Seejärel definitsiooni järgi ja .

Siis aga järgneb:

Seega, meenutades avaldust, saame süsteemi:

Kasutame nüüd järgmist lihtsat fakti: kui mõne kolme arvu puhul kehtib: ja , siis kehtib ja: . Meie olukorras saame:

Või asendades selle määratluse kui , saame:

Niisiis, oleme teinud poole tõestuse: oleme näidanud, et vasak pool jagab paremat. Tõestuse teine ​​pool tehakse sarnaselt.

Töötunnid

Algoritmi tööaeg on hinnanguline Lame'i teoreem, mis loob üllatava seose Eukleidese algoritmi ja Fibonacci jada vahel:

Kui > ja mõne puhul , siis teeb Eukleidese algoritm maksimaalselt rekursiivseid kõnesid.

Kahe tu-ral-arvu $a$ ja $b$ suurim ühine de-li-tel - $gcd(a, b)$ - on suurim arv , mõnel sülemil numbrid $a$ ja $b$ on de-lyat-Xia jäljetult.

$ GCD (a, b) $ leidmiseks võite juua järgmisel loomulikul viisil: lahutage mõlemad arvud la algarvude astmete järgi: $a = 2^(\alpha_1) \cdot 3^( \alpha_2) \cdot \ldots \cdot p^(\alpha_n)_n$ , $b = 2 ^(\beta_1) \cdot 3^(\beta_2) \cdot \ldots \cdot p^(\beta_n)_n$ , ($\alpha_k$ ja $\beta_k$ võivad olla nullid). Siis $$gcd(a, b) = 2^(\min(\alpha_1, \beta_1)) \cdot 3^(\min(\alpha_2, \beta_2)) \cdot \ldots \cdot p^(\ min( \alpha_n, \beta_n))_n.$$ $ hankige see: 2625 $ = 2^0 \cdot 3^1 \cdot 5^3 \cdot 7^1, 8100 = 2^2 \cdot 3^4 \cdot 5^ 2 \cdot 7^0 $ tähendab $gcd(2625, 8100) = 2^0 \cdot 3^1 \cdot 5^2 \cdot 7^0 = 75 $.

Selle meetodi oluline puudus on see, et suure arvu jagamine lihtsateks kordajateks ei ole nii pro- sada, vaid täpsemalt - mitte nii kiire.

Eukleides kirjeldab seitsmendas raamatus “Algus” “kahe arvu üldmõõdu” leidmise al-go-rütmi. Al-go-rütm kirjeldab-san geo-met-ri-che-ski kui kahe lõike üldmõõdu on-hod-de-tion. See taandub "pärast-va-tel-no-mu from-nya-ty" alates rohkem alates-lõigatud-vähem alates-lõikamisest. Nüüd on see al-go-rütm from-ve-walls nagu al-go-rütm Ev-kli-da kõige-bol-she-go-go-de-li-te -la kaks on-tu- leidmiseks. ral-nyh chi-külad.

Põhiidee, mingil alusel os-no-van al-go-rütm, seisneb selles, et $GCD$ chi-sat $a$ ja $b$ on võrdsed $ GCD$ chi-sat $b$ ja $ a-b$. Siit-jah, järeldub, et kui valada $a$ peale $b$ koos jäägiga, st. panna kujul $a = b \cdot q + r$, siis $gcd(a, b) = gcd(b, r)$.

Kirjeldame kellegi sülemi kaunist geo-met-ri-che-skuyu inter-ter-pre-ta-tion al-go-rit-ma, inter-active-tiv-naya re-a-li-za -tion. enne-lo-the-on-the-she.

Ristkülikus-no-ke, mille külgede pikkus on $a$ ja $b$ servast-shi-va-em max-si-mal-but-possible ruudust kaugemal. Ülejäänud ristkülikus-mo-coal-no-ke jälle for-the-edge-shi-va-em on mak-si-mal-aga võimalik ruut. Ja nii edasi ja edasi, kuni kogu väljuv ristkülik pole üle värvitud. Saja-ro-ny sa-mo-go-ma-lazi-ko-th ruudu-ra-ta pikkus võrdub $ GCD (a, b) $.

Rohkem in-fraction-but geo-met-ri-che-sky in-ter-pre-ta-tion op-sa-on sama, ja para-ral-lel-but with-ve-de-but arith-me -ti-che-al-go-rit-ma Ev-kli-da kirjeldus.

In-ter-pre-ta-tion al-go-rit-ma	Al-go-rütm Ev-cli-da
Ristkülikus, mille küljed on $a$ ja $b$ $(a \gt b)$ üle si-mal-but-th-me-ra servade (saja $b$). Seda toimingut korratakse värvimata osaga nii palju kui võimalik.	Suurem arv $a$ kustutatakse ja jääk väiksemal arvul $b$: $a = b \cdot q_1 + r_1$.
Kui sellised ruudud katavad kogu ristküliku, siis on arv $b$ $GCD$.	Kui ra-veenide de-le-tionist jääv $r_1$ on nu-lu, siis väiksem arv $b$ on $GCD$.
Kui jääb alles ristkülik-tähis (saja-ro-on-mi $b$ ja $r_1$), on sellel maksimaalselt valuliku kaelaga ruutude arv max-si-mal-but-th-mõõt -ra (küljega $r_1$).	Kui $r_1$ jääk ei ole võrdne nulliga, kustutatakse väiksem arv $b$ ja jääk väärtusel $r_1$: $b = r_1 \cdot q_2 + r_2 $.
Kui ruut sajaga $r_1$ katab kogu ristküliku, siis $r_1$ on $GCD$.	Kui teise de-le-tion'i tulemuses on $r_2$ jääk võrdne nulliga, siis $r_1$ on $GCD$.
Kui on olemas ristkülik-tähis (saja-ro-on-mi $r_1$ ja $r_2$), on sellel maksimaalselt valuliku kaelaga ruutude arv max-si-small-size-me-ra (küljega $r_2$).	Kui $r_2$ jääk teise de-le-ni ajal ei ole võrdne nulliga, siis kustutatakse $r_1$ väärtusega $r_2$: $r_1 = r_2 \cdot q_3 + r_3$ .
Ja nii edasi ja edasi, kuni kogu täisnurk-tähis ei ole ruut-ra-ta-mi. (Varem või hiljem see juhtub, sest sada ruut-ra-t-d vähendavad-sha-ut-sya ja igal juhul saate pool niiti ülejäänud parem-mo-coal-nick quad-ra-ta -mi saja-ro-one ühikuga).	Ja nii edasi ja nii edasi, kuni ülejäänud jooksev $r_n$ on võrdne nulliga (ra-aga või hiljem see juhtub, sest -ku ülejäänud-ki vähendab-sha-ut-sya).
Saja mi-no-small-but-go ruudu pikkus on stardinumbrite $ GCD $.	Viimane, mis ei ole võrdne nulliga, jääkvool $r_(n-1)$ on algarvude $GCD$.

Al-go-rütm Ev-kli-yes on võimas instrument, mida kasutatakse erinevate isiklike probleemide lahendamisel. Näiteks kasutab ta võrrandite lahendamiseks täisarvudes, mis esitavad arve lõpmatuse kujul -break-nyh (chain-th) draw-beat, seda saab üldistada, et leida kõige-suurem-ta-mine-mine-. de-li-te-la kahest mitmekordsest go-liikmest.

Kirjandus

Euclid. Na-cha-la Ev-cli-da. Raamatud VII, X. - M.-L.: GITTL, 1950.

R. Courant, G. Robins. Mis see ma-te-ma-ti-ka on? - M.: MTsNMO, 2010.

Mõelge kahele peamisele meetodile GCD leidmiseks kahel peamisel viisil: kasutades Eukleidese algoritmi ja faktoringut. Kasutame mõlemat meetodit kahe, kolme ja enama arvu puhul.

Eukleidese algoritm GCD leidmiseks

Eukleidese algoritmi abil on lihtne arvutada kahe positiivse arvu suurimat ühisjagajat. Oleme esitanud Eukleidese algoritmi sõnastused ja tõendid jaotises Suurim ühine jagaja: determinant, näited.

Algoritmi põhiolemus on järjepidevalt jagamine jäägiga, mille käigus saadakse vormi võrdsuste jada:

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

Saame jaotuse lõpetada millal rk + 1 = 0, kus r k = gcd (a , b).

Näide 1

64 ja 48 .

Otsus

Tutvustame tähistust: a = 64 , b = 48 .

Eukleidese algoritmi alusel viime läbi jagamise 64 peal 48 .

Saame 1 ja ülejäänud 16 . Selgub, et q 1 = 1, r 1 = 16.

Teine samm on jagamine 48 kella 16-ks saame 3 . St q2 = 3, a r2 = 0. Seega on arv 16 tingimuse arvude suurim ühine jagaja.

Vastus: gcd(64, 48) = 16.

Näide 2

Mis on numbrite GCD 111 ja 432 ?

Otsus

Jaga 432 peal 111 . Eukleidese algoritmi järgi saame võrduste ahela 432 = 111 3 + 99 , 111 = 99 1 + 12 , 99 = 12 8 + 3 , 12 = 3 4 .

Seega arvude suurim ühisjagaja 111 ja 432 on 3.

Vastus: gcd(111, 432) = 3.

Näide 3

Leidke 661 ja 113 suurim ühisjagaja.

Otsus

Jagame arvud järjestikku ja saame GCD (661 , 113) = 1 . See tähendab, et 661 ja 113 on suhteliselt algarvud. Kui vaataksime algarvude tabelit, saaksime selle välja mõelda enne arvutuste alustamist.

Vastus: gcd(661, 113) = 1.

GCD leidmine arvude algteguriteks faktoriseerimise teel

Faktooringuga kahe arvu suurima ühisjagaja leidmiseks on vaja korrutada kõik nende kahe arvu lahutamisel saadud algtegurid, mis on neile ühised.

Näide 4

Kui jagame arvud 220 ja 600 algteguriteks, saame kaks korrutist: 220 = 2 2 5 11 ja 600 = 2 2 2 3 5 5. Nende kahe toote ühised tegurid on 2, 2 ja 5. See tähendab, et NOD (220, 600) = 2 2 5 = 20.

Näide 5

Leidke arvude suurim ühisjagaja 72 ja 96 .

Otsus

Leia kõik arvude algtegurid 72 ja 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

Kahe arvu ühised algtegurid: 2 , 2 , 2 ja 3 . See tähendab, et NOD (72, 96) = 2 2 2 3 = 24.

Vastus: gcd(72, 96) = 24.

Kahe arvu suurima ühisjagaja leidmise reegel põhineb suurima ühisjagaja omadustel, mille kohaselt gcd (m a 1 , m b 1) = m gcd (a 1 , b 1) , kus m on mis tahes positiivne täisarv .

Kolme või enama numbri GCD leidmine

Sõltumata arvude arvust, mille jaoks peame leidma GCD, tegutseme sama algoritmi järgi, mis seisneb kahe järjestikuse arvu GCD leidmises. See algoritm põhineb järgmise teoreemi rakendamisel: Mitme arvu GCD a 1 , a 2 , … , a k on võrdne arvuga d k, mis leitakse gcd järjestikuses arvutuses (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.

Näide 6

Leidke nelja arvu 78, 294, 570 ja suurim ühisjagaja 36 .

Otsus

Tutvustame tähistust: a 1 = 78, a 2 = 294, a 3 = 570, a 4 = 36.

Alustame arvude 78 ja 294 GCD leidmisega: d2= GCD (78 , 294) = 6 .

Nüüd hakkame otsima d 3 \u003d GCD (d 2, a 3) \u003d GCD (6, 570) . Eukleidese algoritmi järgi 570 = 6 95 . See tähendab et d 3 = GCD (6 , 570) = 6 .

Otsige üles d 4 \u003d GCD (d 3, a 4) \u003d GCD (6, 36). 36 jagub 6-ga ilma jäägita. See võimaldab meil saada d4= GCD (6 , 36) = 6 .

d4 = 6, see tähendab GCD (78 , 294 , 570 , 36) = 6 .

Vastus:

Ja nüüd vaatame veel ühte võimalust nende ja muude numbrite jaoks GCD arvutamiseks. Leiame gcd, korrutades kõik arvude tavalised algtegurid.

Näide 7

Arvutage arvude 78 , 294 , 570 ja gcd 36 .

Otsus

Jaotame need arvud algteguriteks: 78 = 2 3 13 , 294 = 2 3 7 7 , 570 = 2 3 5 19 , 36 = 2 2 3 3 .

Kõigi nelja numbri puhul on ühised algtegurid arvud 2 ja 3.

Selgub, et NOD (78, 294, 570, 36) = 2 3 = 6.

Vastus: gcd(78, 294, 570, 36) = 6.

Negatiivsete arvude gcd leidmine

Kui peame tegelema negatiivsete arvudega, siis saame kasutada nende arvude mooduleid suurima ühisjagaja leidmiseks. Seda saame teha, teades vastandmärgiga numbrite omadust: arvud n ja -n neil on samad jagajad.

Näide 8

Leidke negatiivsete täisarvude gcd − 231 ja − 140 .

Otsus

Arvutuste tegemiseks võtame tingimuses antud arvude moodulid. Need on numbrid 231 ja 140. Ütleme selle lühidalt: GCD (− 231 , − 140) = GCD (231, 140). Nüüd rakendame Eukleidese algoritmi kahe arvu algtegurite leidmiseks: 231 = 140 1 + 91 ; 140 = 91 1 + 49; 91 = 49 1 + 42; 49 = 42 1 + 7 ja 42 = 7 6. Saame, et gcd (231, 140) = 7 .

Ja alates NOD-st (− 231 , − 140) = GCD (231 , 140) , siis numbrite gcd − 231 ja − 140 võrdub 7 .

Vastus: gcd (− 231 , − 140) = 7 .

Näide 9

Määrake kolme arvu gcd - 585, 81 ja − 189 .

Otsus

Asendame ülaltoodud loendis olevad negatiivsed arvud nende absoluutväärtustega, saame GCD (− 585 , 81 , − 189) = GCD (585 , 81 , 189) . Seejärel jagame kõik antud arvud algteguriteks: 585 = 3 3 5 13, 81 = 3 3 3 3 ja 189 = 3 3 3 7. Algtegurid 3 ja 3 on kolmele arvule ühised. Selgub, et gcd (585 , 81 , 189) = gcd (- 585 , 81 , - 189) = 9 .

Vastus: GCD (− 585 , 81 , − 189) = 9 .

Kui märkate tekstis viga, tõstke see esile ja vajutage Ctrl+Enter

Laialt levinud e-kaubanduses. Samuti kasutatakse algoritmi lineaarsete diofantiini võrrandite lahendamisel, jätkumurdude konstrueerimisel Sturmi meetodil. Eukleidese algoritm on tänapäevase arvuteooria põhiliseks vahendiks teoreemide tõestamiseks, näiteks Lagrange'i teoreem nelja ruudu summa kohta ja aritmeetika põhiteoreem.

Entsüklopeediline YouTube

1 / 5

✪ Matemaatika. Naturaalarvud: Eukleidese algoritm. Foxfordi veebiõppekeskus

✪ Eukleidese algoritm

✪ Eukleidese algoritm, kiire viis GCD leidmiseks

✪ Matemaatika 71. Suurim ühine jagaja. Eukleidese algoritm – Meelelahutusteaduste Akadeemia

✪ 20, kui silmuse Euclid Python algoritm

Subtiitrid

Lugu

Vana-Kreeka matemaatikud nimetasid seda algoritmi ἀνθυφαίρεσις või ἀνταναίρεσις - "vastastikune lahutamine". Seda algoritmi Euclid ei avastanud, kuna seda on juba mainitud Topeka Aristoteles. Eukleidese "Algustes" on seda kirjeldatud kaks korda – VII raamatus kahe suurima ühise jagaja leidmiseks. naturaalarvud ja raamatus X kahe homogeense suuruse suurima ühise mõõdu leidmiseks. Mõlemal juhul antakse kahe segmendi "ühismõõdu" leidmiseks algoritmi geomeetriline kirjeldus.

Kirjeldus

Eukleidese algoritm täisarvude jaoks

Las olla a (\displaystyle a) ja b (\displaystyle b)- täisarvud, mis ei ole samal ajal võrdsed nulliga, ja numbrijada

a > b > r 1 > r 2 > r 3 > r 4 > … > r n (\displaystyle a>b>r_(1)>r_(2)>r_(3)>r_(4)>\ \dots \ >r_(n))

määrab asjaolu, et iga r k (\displaystyle r_(k))- see on eelmise arvu jagamise jääk eelmisega ja eelviimane jagatakse viimasega, see tähendab:

a = b q 0 + r 1 , (\displaystyle a=bq_(0)+r_(1),) b = r 1 q 1 + r 2, (\displaystyle b=r_(1)q_(1)+r_(2),) r 1 = r 2 q 2 + r 3 , (\kuvastiil r_(1)=r_(2)q_(2)+r_(3),) ⋯ (\displaystyle \cdots) r k − 2 = r k − 1 q k − 1 + r k , (\displaystyle r_(k-2)=r_(k-1)q_(k-1)+r_(k),) ⋯ (\displaystyle \cdots) r n − 2 = r n − 1 q n − 1 + r n , (\displaystyle r_(n-2)=r_(n-1)q_(n-1)+r_(n),) r n − 1 = r n q n . (\displaystyle r_(n-1)=r_(n)q_(n).)

Siis gcd( a, b), suurim ühine jagaja a ja b, on võrdne r n , selle jada viimane nullist erinev liige.

Olemasolu selline r 1 , r 2 , ..., r n ehk jäägiga jagamise võimalus m peal n mis tahes terviku jaoks m ja terve n≠ 0 on tõestatud induktsiooniga sees m.

Korrektsus see algoritm tuleneb kahest järgmisest väitest:

• Las olla a = b⋅q + r, siis gcd(a, b) = gcd(b, r).

Tõestus

• GCD( r, 0) = r iga nullist erineva jaoks r(sest 0 jagub mis tahes täisarvuga peale nulli).

Eukleidese geomeetriline algoritm

Olgu antud kaks pikkusesegmenti a ja b. Lahutage väiksem segment suuremast segmendist ja asendage suurem segment saadud erinevusega. Korrake seda toimingut, kuni segmendid on võrdsed. Kui see juhtub, on algsed segmendid võrreldavad ja viimane saadud segment on nende suurim ühine mõõt. Kui ühist mõõtu pole, on protsess lõputu. Sellisel kujul kirjeldab algoritmi Euclid ja see on rakendatud kompassi ja joonlaua abil.

Näide

Illustreerimiseks kasutatakse gcd leidmiseks Eukleidese algoritmi a= 1071 ja b= 462. Alustuseks lahutage 1071-st 462 kordne, kuni saame erinevuse, mis on väiksem kui 462. Me peame lahutama 462 kaks korda, ( q 0 = 2), jäädes 147-ga:

1071 = 2 × 462 + 147.

Seejärel lahutame 462-st 147 kordse, kuni saame erinevuse alla 147. Me peame lahutama 147 kolm korda ( q 1 = 3), ülejäänud 21:

462 = 3 x 147 + 21.

Seejärel lahutame 147-st 21 kordse, kuni saame erinevuse, mis on väiksem kui 21. Me peame lahutama 21 seitse korda ( q 2 = 7), jäädes ilma jäägita:

147 = 7 x 21 + 0.

Seega jada a > b > r 1 > r 2 > r 3 > … > r n sel konkreetsel juhul näeks välja selline:

1071 > 462 > 147 > 21.

Kuna viimane jääk on null, lõpeb algoritm 21-ga ja gcd(1071, 462) = 21.

Tabelina olid sammud järgmised:

Rakendused

Laiendatud Eukleidese algoritm ja Bezouti seos

Valemid jaoks r i (\displaystyle r_(i)) saab ümber kirjutada nii:

r 1 = a + b (− q 0) (\displaystyle r_(1)=a+b(-q_(0))) r 2 = b − r 1 q 1 = a (− q 1) + b (1 + q 1 q 0) (\kuvastiil r_(2)=b-r_(1)q_(1)=a(-q_( 1))+b(1+q_(1)q_(0))) ⋮ (\displaystyle \vdots) GCD (a , b) = r n = a s + b t (\kuvastiil (a,b)=r_(n)=as+bt)

Siin s ja t terve. Seda suurima ühise jagaja esitust nimetatakse Bezouti seoseks ja arvudeks s ja t- koefitsiendid Bezu . Bezouti seos on võtmeks Eukleidese lemma tõestuses ja aritmeetika põhiteoreemis.

Jätkuvad murded

Eukleidese algoritm on jätkuvate murdudega üsna tihedalt seotud. Suhtumine a/b lubab jätkuvat murdosa esitust:

ab = [q0; q 1 , q 2 , ⋯ , q n ] (\displaystyle (\frac (a)(b))=).

Sel juhul on jätkuv murd ilma viimase liikmeta võrdne Bezouti koefitsientide suhtega t/s miinusmärgiga võetud:

[q 0; q 1 , q 2 , ⋯ , q n − 1 ] = − t s (\displaystyle =-(\frac (t)(s))).

Eukleidese algoritmi defineerivate võrdsuste jada saab ümber kirjutada järgmisel kujul:

a b = q 0 + r 0 b b r 0 = q 1 + r 1 r 0 r 0 r 1 = q 2 + r 2 r 1 ⋮ r k − 2 r k − 1 = q k + r k r k − 1 ⋮ r N − 2 r N − 1 = q N (\displaystyle (\begin(joonatud)(\frac (a)(b))&=q_(0)+(\frac (r_(0))(b))\\(\frac (b) )(r_(0)))&=q_(1)+(\frac (r_(1))(r_(0)))\\(\frac (r_(0))(r_(1)))& =q_(2)+(\frac (r_(2))(r_(1)))\\&()\ \vdots \\(\frac (r_(k-2))(r_(k-1) ))&=q_(k)+(\frac (r_(k))(r_(k-1)))\\&()\ \vdots \\(\frac (r_(N-2))(r_ (N-1)))&=q_(N)\end(joondatud)))

Viimane liige võrrandi paremal küljel on alati võrdne järgmise võrrandi vasaku külje pöördarvuga. Seetõttu saab kaks esimest võrrandit ühendada järgmisel kujul:

a b = q 0 + 1 q 1 + r 1 r 0 (\displaystyle (\frac (a)(b))=q_(0)+(\cfrac (1)(q_(1)+(\cfrac (r_( 1))(r_(0))))))

Kolmandat võrdsust saab kasutada avaldise nimetaja asendamiseks r 1 /r 0, saame:

a b = q 0 + 1 q 1 + 1 q 2 + r 2 r 1 (\displaystyle (\frac (a)(b))=q_(0)+(\cfrac (1)(q_(1)+(\ cfrac (1)(q_(2)+(\cfrac (r_(2))(r_(1)))))))

Viimase jäägi suhe r k /r k−1 saab alati asendada jada järgmise võrrandiga ja nii edasi kuni viimase võrrandini. Tulemuseks on jätkuv murdosa:

a b = q 0 + 1 q 1 + 1 q 2 + 1 ⋱ + 1 q N = [ q 0 ; q 1 , q 2 , … , q N ] (\displaystyle (\frac (a)(b))=q_(0)+(\cfrac (1)(q_(1)+(\cfrac (1)(q_) (2)+(\cfrac (1)(\ddots +(\cfrac (1)(q_(N)))))))))=)

Üldistatud Eukleidese algoritm polünoomide jaoks

Eukleidese algoritm ja laiendatud Eukleidese algoritm üldistavad loomulikult polünoomide ringi k[x] ühest muutujast suvalise välja kohal k, kuna selliste polünoomide jaoks on defineeritud jäägiga jagamise tehe. Eukleidese polünoomide algoritmi täitmisel saadakse sarnaselt Eukleidese täisarvude algoritmiga polünoomijääkide jada (PRS).

Rõnga näide Z[x]

Olgu cont(f) definitsiooni järgi polünoomi f(x) kordajate gcd väärtusest Z[x] - sisu polünoom. Nimetatakse jagatis, mis jagab f(x) kont(f)-ga primitiivne osa polünoom f(x) ja seda tähistatakse primpart(f(x)). Neid määratlusi on vaja kahe polünoomi gcd leidmiseks lk 1 (x) ja lk 2 (x) ringis Z[x]. Täisarvudest ületavate polünoomide puhul kehtib järgmine:

C o n t ((\displaystyle cont() NODNOD ( c o n t (p 1 (x)) , c o n t (p 2 (x)) ), (\displaystyle \(cont(p_(1)(x)),cont(p_(2)(x))\),)

P r i m p a r t ((\displaystyle primpart() GCD ( p 1 (x) , p 2 (x) )) = (\kuvastiil \(p_(1) (x), p_(2) (x)\))=) GCD (p r i m p a r t (p 1 (x)) , p r i m p a r t (p 2 (x)) ). (\displaystyle \(primpart(p_(1)(x)),primpart(p_(2)(x))\).)

Seega taandub kahe suvalise polünoomi gcd leidmise probleem primitiivsete polünoomide gcd leidmise probleemiks.

Olgu Z[x]-st kaks primitiivset polünoomi p 1 (x) ja p 2 (x), mille astmete seos on täidetud: deg(p 1 (x)) = m ja deg(p 2 (x) ) = n, m > n. Polünoomide jagamine jäägiga eeldab dividendi kõrgeima koefitsiendi täpset jagamist jagaja kõrgeima koefitsiendiga, jäägiga jagamist üldjuhul teha ei saa. Seetõttu võetakse kasutusele pseudojaotusalgoritm, mis võimaldab siiski saada pseudo jagatise ja pseudojäägi (prem), mis ise kuuluvad täisarvude kohal olevate polünoomide hulka.

Pseudojaotuse all peame silmas seda, et jagamisele endale eelneb polünoomi korrutis p 1 (x) (\displaystyle p_(1) (x)) peal (l c (p 2 (x))) m − n + 1 (\displaystyle (lc(p_(2)(x)))^(m-n+1)), st

L c (p 2 (x)) m − n + 1 p 1 (x) = p 2 (x) q (x) + r 2 (x), deg ⁡ (r (x))< deg ⁡ (p 2 (x)) , {\displaystyle lc(p_{2}(x))^{m-n+1}p_{1}(x)=p_{2}(x)q(x)+r_{2}(x),\deg(r(x))<\deg(p_{2}(x)),}

kus q (x) (\displaystyle q(x)) ja r (x) (\displaystyle r(x))- vastavalt pseudoosaline ja pseudojääk.

Niisiis, p 1 (x) , p 2 (x) ∈ Z [ x ] (\displaystyle p_(1) (x), p_(2) (x)\in Z[x]), enamgi veel kraad ⁡ (p 1) = n 1 ≥ kraad ⁡ (p 2) = n 2 (\displaystyle \deg(p_(1))=n_(1)\geq \deg(p_(2))=n_(2) ). Seejärel koosneb Eukleidese algoritm järgmistest sammudest:

1. GCD sisu arvutamine:

C:= (\displaystyle c:=) GCD ( c o n t (p 1) , c o n t (p 2) ) (\displaystyle \(cont(p_(1)),cont(p_(2))\)).

2. Primitiivsete osade arvutamine:

P 1 ′ (x) := p r i m p a r t (p 1 (x)) ; (\displaystyle p_(1)"(x):=primpart(p_(1)(x));)

P 2 ′ (x) := p r i m p a r t (p 2 (x)) . (\displaystyle p_(2)"(x):=primpart(p_(2)(x)).)

3. Polünoomijääkide jada koostamine:

P 1 ′ (x) , (\displaystyle p_(1)"(x),)

P 2 ′ (x) , (\displaystyle p_(2)"(x),)

P 3 (x) := p r e m (p 1 ′ (x) , p 2 ′ (x)) , (\displaystyle p_(3) (x):=prem(p_(1)"(x), p_(2 )"(x)))

P 4 (x) := p r e m (p 2 ′ (x) , p 3 (x)) , (\displaystyle p_(4)(x):=prem(p_(2)"(x), p_(3) (x)))

P 5 (x) := p r e m (p 3 (x) , p 4 (x)) , (\displaystyle p_(5) (x):=prem(p_(3) (x), p_(4) (x ))))

. . . (\displaystyle ...)

P h (x) := p r e m (p h − 2 (x) , p h − 1 (x)) . (\displaystyle p_(h)(x):=prem(p_(h-2)(x),p_(h-1)(x)).)