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

Najveći zajednički djelitelj(NOD) je broj koji dijeli dva broja bez ostatka i sam je djeljiv bez ostatka s bilo kojim drugim djeliteljem data dva broja. Jednostavno, ovo je najviše veliki 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 brojem.
2. Ako se podijeli bez ostatka, tada je manji broj GCD (trebalo bi izaći iz ciklusa).
3. Ako postoji ostatak, onda veći broj zamijenite ga ostatkom podjele.
4. Pređimo 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 od 6.
GCD(30, 18) = 6

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

U petlji, ostatak dijeljenja se upisuje u varijablu a ili b. Petlja se završava kada je barem jedna od varijabli nula. To znači da drugi sadrži gcd. Međutim, ne znamo koji tačno. 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. Oduzmite manji broj od većeg broja.
2. Ako je rezultat 0, to znači da su brojevi jednaki jedan drugom i da su GCD (trebalo bi izaći iz petlje).
3. Ako rezultat oduzimanja nije jednak 0, tada zamijenite veći broj rezultatom oduzimanja.
4. Pređimo 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 je minuend ili subtrahend.
GCD(30, 18) = 6

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

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

S obzirom na dva nenegativna cijela broja i . Potrebno je pronaći njihov najveći zajednički djelitelj, tj. najveći broj koji je djelitelj oba , i . On engleski jezik"najveći zajednički djelitelj" se piše "najveći zajednički djelitelj", a njegova uobičajena oznaka je:

(ovdje simbol "" označava djeljivost, tj. "" označava "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 jednaka nuli, rezultat je nedefiniran (dostat će svaki beskonačno veliki broj), u ovom slučaju postavljamo najveći zajednički djelitelj na nulu. Stoga možemo govoriti o sljedećem pravilu: ako je jedan od brojeva jednak nuli, tada je njihov najveći zajednički djelitelj jednak drugom broju.

Euklidov algoritam, o kojem se raspravlja u nastavku, rješava problem pronalaženja najvećeg zajedničkog djelitelja dva broja i za .

Ovaj algoritam je prvi put opisan u Euklidovim elementima (oko 300. godine prije Krista), iako je sasvim 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) ( return b ? gcd (b, a % b) : a; )

Na kraju, predstavljamo nerekurzivni oblik 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, onda Euklidov algoritam uvek završava.

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

Pokažimo da je količina na lijevoj strani jednačine podijeljena realnom na desnoj, a količina na desnoj je podijeljena s onom na lijevoj strani. Očigledno, to će značiti da se lijeva i desna strana poklapaju, što će dokazati ispravnost Euklidovog algoritma.

Označimo . Zatim, po definiciji, i .

Ali onda odavde sledi:

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

Koristimo sada sljedeću jednostavnu činjenicu: ako za neka tri broja: i , tada također vrijedi: . U našoj situaciji dobijamo:

Ili, zamjenjujući njegovu definiciju kao , dobivamo:

Dakle, uradili smo pola dokaza: pokazali smo da lijeva strana dijeli desnu. Druga polovina dokaza se radi na sličan način.

Radni sati

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

Ako > i za neke , tada Euklidski algoritam više neće izvoditi rekurzivne pozive.

Najveća zajednička linija dijeljenja dva regionalna broja $a$ i $b$ - $GCD(a, b)$ - je najveći broj, na nekom broju $a$ i $b$ su podijeljeni bez ostatka.

Da biste pronašli $GCD(a, b)$ možete nastaviti na sljedeći prirodan način: razložiti oba broja la po stepenu prostih brojeva: $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$ i $ \beta_k$ može biti jednak nuli). Tada je $$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.$$ Na primjer, da bismo pronašli najčešću vrijednost od $2625$ i $8100 $ dobijamo: $2625 = 2^0 \cdot 3^1 \cdot 5^3 \cdot 7^1, 8100 = 2^2 \cdot 3^4 \cdot 5^2 \cdot 7^0$, znači $GCD(2625, 8100) = 2^0 \cdot 3^1 \cdot 5^2 \cdot 7^0 = 75$.

Suštinski nedostatak ove metode je u tome što dijeljenje velikog broja na jednostavne množevine nije tako jednostavno, sto, ili bolje rečeno, ne tako brzo.

Euklid u 7. knjizi “Početak” opisuje al-go-ritam “zajedničke mjere dva broja”. Al-go-ritam opisuje geo-met-ri-che-ski, kao sličnost zajedničke mjere dvaju rezova. Svodi se na „praćenje od-nacije” od većeg-od-manjeg-iz-reza. Sada je ovaj al-go-ritam sa zidova kao al-go-ritam Ev-kli-da za pronalaženje najčešćih de-li-those -za dva on-turalna broja.

Osnovna ideja na kojoj se bazira al-go-ritam je da su $GCD$ brojevi $a$ i $b$ jednaki $GCD$ chi-sel $b$ i $a-b$. Odavde slijedi da ako dodate $a$ na $b$ sa ostatkom, tj. predstavljeno u obliku $a = b \cdot q + r$, tada je $GCD(a, b) = GCD(b, r)$.

Opisat ćemo prekrasan geo-met-ri-che-skaya in-ter-pre-ta-tion al-go-rit-ma, inter-active-tiv-naya re-a-li-za -tion nečega ispred-isti-viši.

U ravnom uglu sa dugim stranicama $a$ i $b$ za najveći mogući kvadrat. U preostalom ravnom ugljenu opet uzimamo najveći mogući kvadrat. I tako sve dok se ne pokrije cijeli originalni pravougaonik. Dužina kvadrata je sto i bit će jednaka $GCD(a, b)$.

Detaljnije, ali geo-met-ri-che-skaya in-ter-pre-ta-tion op-sa-na ispod, i par-ral-lel-ali sa-ve-de-ali arif-me-ti- che-skoe opis-sa-nie al-go-rit-ma Ev-kli-da.

Inter-pre-ta-tion al-go-rit-ma	Al-go-ritam Ev-kli-da
U pravougaonom uglu sa dugim stranicama $a$ i $b$ $(a \gt b)$ za najlepši kvadrat male veličine (sa stotinu $b$). Ova operacija se ponavlja za neobojeni dio što je više moguće.	Veći broj $a$ dijeli se sa ostatkom manjim brojem $b$: $a = b \cdot q_1 + r_1$.
Ako takvi kvadrati pokrivaju cijeli pravougaonik, tada je broj $b$ $GCD$.	Ako je ostatak tekućeg $r_1$ iz operacije jednak nuli, tada je manji broj $b$ $GCD$.
Ako je ostao pravougaonik (sa stotinama $b$ i $r_1$), on ima najveći mogući broj kvadrata maksimalne veličine (sa stotinu $r_1$).	Ako ostatak od $r_1$ nije jednak nuli, tada se manji broj $b$ dijeli sa ostatkom $r_1$: $b = r_1 \cdot q_2 + r_2 $.
Ako kvadrat sa stotinu $r_1$ pokriva cijeli pravougaonik, onda je $r_1$ $gcd$.	Ako je, kao rezultat drugog brisanja, ostatak trenutnog $r_2$ jednak nuli, tada je $r_1$ $GCD$.
Ako je ostao pravougaonik (sa stoljećima $r_1$ i $r_2$), on ima najveći mogući broj kvadrata maksimalne veličine (sa stotinu $r_2$).	Ako ostatak trenutnog $r_2$ u drugom podjeli nije jednak nuli, tada se $r_1$ dijeli sa $r_2$: $r_1 = r_2 \cdot q_3 + r_3$ .
I tako sve dok se cijeli originalni pravougaonik ne izreže u kvadrat. (Prije ili kasnije, to će se dogoditi, jer se stotine kvadrata smanjuju i u svakom slučaju je moguće na pola niti preostalog pravokutnog kvadrata sa stotinu jedinica).	I tako sve dok ostatak $r_n$ ne bude jednak nuli (prije ili kasnije će se to dogoditi, jer se -ku-ostaci smanjuju).
Dužina kvadrata od stotinu mi-no-mali-no-go je $NOD$ izvornih brojeva.	Posljednja struja ostatka različita od nule $r_(n-1)$ je $GCD$ početnih brojeva.

Al-go-ritam Ev-kli-da je moćan alat koji se koristi u rješavanju raznih ličnih problema. Na primjer, koristi se za rješavanje jednačina u cijelim brojevima, predstavljajući brojeve u obliku konstantnih (lančanih) razlomaka, može se generalizirati kako bi se pronašao najčešći de-li-dva mnogo-go-člana-nov.

Književnost

Euklid. Na-cha-la Ev-kli-da. Knjige VII, X. - M.-L.: GITTL, 1950.

R. Ku-rant, G. Robins. Šta je ovo ma-te-ma-ti-ka? - M.: MTsNMO, 2010.

Razmotrimo dvije glavne metode pronalaženja GCD-a na dva glavna načina: korištenjem Euklidovog algoritma i dekompozicijom na proste faktore. Primijenimo obje metode za dva, tri ili više brojeva.

Euklidski algoritam za pronalaženje GCD

Euklidski algoritam olakšava izračunavanje najvećeg zajedničkog faktora dva pozitivna broja. Formulacije i dokaz Euklidovog algoritma predstavili 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 sljedeće oznake: a = 64, b = 48.

Na osnovu Euklidovog algoritma izvršićemo podjelu 64 on 48 .

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

Drugi korak je podjela 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 iz uvjeta.

odgovor: GCD (64, 48) = 16.

Primjer 2

Šta je GCD brojeva? 111 I 432 ?

Rješenje

Mi se delimo 432 on 111 . Prema Euklidskom 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 je 111 I 432 – ovo je 3.

odgovor: GCD (111, 432) = 3.

Primjer 3

Pronađite najveći zajednički djelitelj brojeva 661 i 113.

Rješenje

Podijelimo brojeve redom i dobijemo GCD (661 , 113) = 1 . To znači da su 661 i 113 obostrani primarni brojevi. To bismo mogli shvatiti prije nego što započnemo računanje ako bismo konsultirali tabelu prostih brojeva.

odgovor: GCD (661, 113) = 1.

Pronalaženje GCD-a rastavljanjem brojeva u proste faktore

Da bi se metodom faktorizacije pronašao najveći zajednički djelitelj dva broja, potrebno je pomnožiti sve proste faktore koji se dobiju rastavljanjem ova dva broja na faktore 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 u ova dva proizvoda su 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

Uobičajeni prosti faktori 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 (m a 1, m b 1) = m gcd (a 1, b 1), gdje je m bilo koji pozitivan cijeli broj .

Pronalaženje gcd tri ili više brojeva

Bez obzira na broj brojeva za koje treba da nađemo gcd, postupit ćemo po istom algoritmu, tj. sekvencijalni nalaz GCD dva broja. Ovaj algoritam se zasniva na primeni sledeće teoreme: GCD više brojeva a 1 , a 2 , … , a k jednak broju dk, koji se nalazi sekvencijalnim izračunavanjem 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 djelitelj četiri broja 78, 294, 570 i 36 .

Rješenje

Uvedemo oznaku: 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 sa pronalaženjem 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đimo d 4 = GCD (d 3 , a 4) = GCD (6, 36). 36 djeljivo sa 6 bez ostatka. Ovo nam omogućava da dobijemo d 4 = GCD (6 , 36) = 6 .

d4 = 6, odnosno GCD (78 , 294 , 570 , 36) = 6 .

odgovor:

Pogledajmo sada drugi način izračunavanja GCD za te i više brojeva. Možemo pronaći gcd 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 činioci će biti brojevi 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 negativnih brojeva

Ako imamo posla s negativnim brojevima, onda možemo koristiti module ovih brojeva da pronađemo najveći zajednički djelitelj. To možemo učiniti, poznavajući svojstvo brojeva suprotnih predznaka: brojeva n I -n imaju iste djelitelje.

Primjer 8

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

Rješenje

Za izvođenje proračuna uzimamo module brojeva datih u uvjetu. To će biti brojevi 231 i 140. Zapišimo to ukratko: GCD (− 231 , − 140) = GCD (231, 140) . Sada primjenjujemo 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 brojeva − 231 I − 140 jednaki 7 .

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

Primjer 9

Odrediti gcd tri broja − 585, 81 i − 189 .

Rješenje

Zamijenimo negativne brojeve u gornjoj listi njihovim apsolutnim vrijednostima, dobićemo GCD (− 585 , 81 , − 189) = GCD (585 , 81 , 189) . Zatim sve ove brojeve činimo u proste faktore: 585 = 3 3 5 13, 81 = 3 3 3 3 i 189 = 3 3 3 7. Zajednički za tri broja su prosti faktori 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, označite je i pritisnite Ctrl+Enter

Široko se koristi u e-trgovini. Algoritam se također koristi u rješavanju linearnih Diofantovih jednadžbi, u konstruiranju kontinuiranih razlomaka i u Sturmovoj metodi. Euklidov algoritam je glavni alat za dokazivanje teorema u modernoj teoriji brojeva, kao što je Lagrangeova teorema o zbiru četiri kvadrata i fundamentalna teorema aritmetike.

Enciklopedijski YouTube

1 / 5

✪ Matematika. Prirodni brojevi: Euklidov algoritam. Foxford Online Learning Center

✪Euklidski algoritam

✪ Euklidski algoritam, brz način nađi gcd

✪ Matematika 71. Najveći zajednički djelitelj. Euklidov algoritam - Akademija zabavnih nauka

✪ 20 while petlja Python Euklidski algoritam

Titlovi

Priča

Drevni grčki matematičari nazvali su ovaj algoritam ἀνθυφαίρεσις ili ἀνταναίρεσις - “međusobno oduzimanje”. Ovaj algoritam nije otkrio Euklid, jer je već spomenut u Topeka Aristotel. U Euklidovim Elementima opisano je dva puta - u Knjizi VII za pronalaženje najvećeg zajedničkog djelitelja dva prirodni brojevi i u X knjizi za pronalaženje najveće zajedničke mjere za dvije homogene veličine. U oba slučaja dat je geometrijski opis algoritma za pronalaženje “zajedničke mjere” dva segmenta.

Opis

Euklidov algoritam za cijele brojeve

Neka a (\displaystyle a) I b (\displaystyle b)- cijeli brojevi koji u isto vrijeme nisu jednaki nuli i niz brojeva

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))

određeno činjenicom da svaki r k (\displaystyle r_(k))- ovo je ostatak od dijeljenja prethodnog broja sa prethodnim, a pretposljednji se dijeli s posljednjim u potpunosti, odnosno:

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 , (\displaystyle 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).)

Zatim GCD( a, b), najveći zajednički djelitelj a I b, je jednako r n, posljednji nenulti član ovog niza.

Postojanje takav r 1 , r 2 , ..., r n, odnosno mogućnost dijeljenja s ostatkom m on n za bilo koji cijeli broj m i cjelina n≠ 0, može se dokazati indukcijom na m.

Ispravnost Ovaj algoritam slijedi iz sljedeće dvije izjave:

• Neka a = b⋅q + r, tada je gcd (a, b) = gcd (b, r).

Dokaz

• GCD( r, 0) = r za bilo koji različit od nule r(pošto je 0 djeljiv s bilo kojim cijelim brojem osim nule).

Geometrijski euklidski algoritam

Neka su data dva segmenta dužine a I b. Oduzmite manji segment od većeg segmenta i zamenite veći segment rezultujućom razlikom. Ponavljamo ovu operaciju dok se segmenti ne izjednače. Ako se to dogodi, tada su originalni segmenti uporedivi, a posljednji rezultujući segment je njihova najveća zajednička mjera. Ako nema opće mjere, onda je proces beskonačan. U ovom obliku, algoritam je opisao Euklid i implementiran je pomoću šestara i ravnala.

Primjer

Za ilustraciju, Euklidski algoritam će se koristiti za pronalaženje gcd a= 1071 i b= 462. Prvo oduzmite višekratnik 462 od 1071 dok ne dobijemo razliku manju od 462. Moramo oduzeti 462 dvaput, ( q 0 = 2), ostavljajući ostatak od 147:

1071 = 2 × 462 + 147.

Zatim oduzimajte višekratnike 147 od 462 dok ne dobijemo razliku manju od 147. Moramo oduzeti 147 tri puta ( q 1 = 3), ostavljajući ostatak od 21:

462 = 3 × 147 + 21.

Zatim oduzimajte višekratnike 21 od 147 dok razlika ne bude manja od 21. Moramo oduzeti 21 sedam puta ( q 2 = 7), ne ostavljajući ostatak:

147 = 7 × 21 + 0.

Dakle, niz a > b > r 1 > r 2 > r 3 > … > r n u ovom konkretnom slučaju će izgledati ovako:

1071 > 462 > 147 > 21.

Pošto je posljednji ostatak nula, algoritam završava brojem 21 i gcd(1071, 462) = 21.

U tabelarnom obliku, koraci su bili sljedeći:

Prijave

Prošireni euklidski algoritam i Bezoutova relacija

Formule za r i (\displaystyle r_(i)) može se prepisati na sljedeći način:

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) (\displaystyle 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 (\displaystyle (a,b)=r_(n)=as+bt)

Evo s I t cijeli. Ovaj prikaz najvećeg zajedničkog djelitelja naziva se Bezoutova relacija i brojevi s I t- Bezout koeficijenti. Bezuova relacija je ključna u dokazu Euklidove leme i osnovne teoreme aritmetike.

Kontinuirani razlomci

Euklidov algoritam je usko povezan sa kontinuiranim razlomcima. Stav a/b može se predstaviti kao kontinuirani razlomak:

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

U ovom slučaju, kontinuirani razlomak bez posljednjeg člana jednak je omjeru Bezoutovih koeficijenata t/s, snimljeno sa znakom minus:

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

Niz jednakosti koje definiraju Euklidski algoritam može se prepisati u obliku:

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 − 2 r N 1 = q N (\displaystyle (\begin(aligned)(\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(poravnano)))

Posljednji član na desnoj strani jednačine uvijek je jednak inverznoj lijevoj strani sljedeće jednačine. Stoga se prve dvije jednadžbe mogu kombinirati u obliku:

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))))))

Treća jednakost se može koristiti za zamjenu nazivnika izraza r 1 /r 0 , dobijamo:

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)))))))

Zadnji omjer ostatka r k /r k−1 se uvijek može zamijeniti sljedećom jednadžbom u nizu, i tako dalje do posljednje jednačine. Rezultat je kontinuirani razlomak:

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))))))))))=)

Generalizirani euklidski algoritam za polinome

Euklidski algoritam i prošireni Euklidski algoritam prirodno se generaliziraju na prsten polinoma k[x] iz jedne varijable preko proizvoljnog polja k, budući da je za takve polinome definirana operacija dijeljenja s ostatkom. Izvođenje Euklidovog algoritma za polinome na sličan način kao Euklidski algoritam za cijele brojeve proizvodi polinomski niz ostatka (PRS).

Primjer za prsten Z[x]

Neka je cont(f) po definiciji gcd koeficijenata polinoma f(x) iz Z[x] - sadržaj polinom. Poziva se količnik f(x) podijeljen sa cont(f). primitivni dio polinom f(x) i označava se sa primpart(f(x)). Ove definicije će biti potrebne za pronalaženje gcd dva polinoma p1(x) I p2(x) u prstenu Z[x]. Za polinome nad cijelim brojevima vrijedi sljedeće:

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

P r i m p a r t ((\displaystyle primpart() GCD ( p 1 (x) , p 2 (x) )) = (\displaystyle \(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))\).)

Dakle, problem nalaženja GCD dva proizvoljna polinoma se svodi na problem nalaženja GCD primitivnih polinoma.

Neka postoje dva primitivna polinoma p 1 (x) i p 2 (x) iz Z[x], za koje vrijedi relacija između njihovih potencija: deg(p 1 (x)) = m i deg(p 2 (x) ) = n, m > n. Dijeljenje polinoma sa ostatkom pretpostavlja tačnu djeljivost najvećeg koeficijenta dividende najvećim koeficijentom djelitelja, u opštem slučaju, dijeljenje s ostatkom se ne može izvršiti. Stoga se uvodi algoritam pseudo-podjele, koji i dalje omogućava da se dobije pseudo-količnik i pseudo-ostatak (prem), koji će i sami pripadati skupu polinoma nad cijelim brojevima.

Pod pseudo-dijeljenjem podrazumijevamo da samoj diobi prethodi množenje polinoma p 1 (x) (\displaystyle p_(1)(x)) on (l c (p 2 (x))) m − n + 1 (\displaystyle (lc(p_(2)(x)))^(m-n+1)), to je

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)),}

Gdje q (x) (\displaystyle q(x)) I r (x) (\displaystyle r(x))- pseudo-količnik i pseudo-ostatak, respektivno.

dakle, p 1 (x) , p 2 (x) ∈ Z [ x ] (\displaystyle p_(1)(x),p_(2)(x)\in Z[x]), i stepen ⁡ (p 1) = n 1 ≥ stepen ⁡ (p 2) = n 2 (\displaystyle \deg(p_(1))=n_(1)\geq \deg(p_(2))=n_(2) ). Tada se Euklidski algoritam sastoji od sljedećih koraka:

1. Proračun sadržaja GCD:

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

2. Proračun primitivnih dijelova:

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. Konstrukcija niza polinomskih ostataka:

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)).)