Euklidesen algoritmo

Euklidesen algoritmoa, matematikan, bi zenbakiren zatitzaile komunetako handiena (${\displaystyle zkh}$) kalkulatzeko erabiltzen den metodo bat da. Euklidesek deskribatu zuen lehenengo aldiz bere Elementuak obran (K.a. 300). Euklidesen algoritmo hedatuarekin, gainera, zatitzaile komunetako handiena emandako bi zenbakien konbinazio lineal moduan adierazteko koefizienteak kalkula daitezke. Algoritmoa hainbat arlotan aplikatzen da; aljebran, zenbaki-teorian eta informatikan, esaterako.

Euklidesen jatorrizko algoritmoa

Grekoek matematikari buruz zuten ikuspuntuaren arabera, zenbakiak magnitude geometrikoak dira. Geometria grekoak bi segmenturen neurgarritasuna aztertzen zuen: bi segmentu (zenbaki) AB eta CD neurgarriak dira hirugarren PQ segmentu bat existitzen bada zein aurreko bien barruan egokitzen den n zenbaki osoa adina aldiz, hau da, PQ-k AB eta CD segmentuak neurtzen baditu.

Edozein segmentu bikote ez da neurgarria; pitagorikoek aurkitu zuten moduan, karratuaren diagonala eta aldea ez dira neurgarriak. Bi segmentu neurgarriak direnean, haien arteko neurri komun handiena topatu nahi izaten da.

Euklidesek bere Elementuak lanaren VII liburuko 2. proposizioan bi segmenturen (zenbakiren) neurri komun handiena topatzeko metodo bat deskribatzen du, zenbakiak haien artean lehenak ez diren kasurako.

Metodoa termino geometrikoetan azaldu zen garai hartan. Gaur egungo hizkuntza modernoan algoritmoa horrela deskribatzen da:

1. Izan bitez AB eta CD bi segmentu, non AB>CD betetzen den. AB-ri CD kentzen diogu behin eta berriz posiblea den bitartean. Amaieran hondarrik geratzen ez bada, orduan CD da neurri komun handiena.
2. EA hondarra geratzen bada, CD baino txikiagoa izango da eta prozesua errepika daiteke; CD-ri EA kenduko zaio behin eta berriz posiblea den bitartean. Azkenean hondarrik gelditzen ez bada, EA izango da neurri komuna. Bestela, EA baino txikiagoa den FC hondar berria lortuko da.
3. Prozesua errepikatu behar da hondarrik geratuko ez den arte. Lortutako azken hondarra da neurri komun handiena.

Euklidesen algoritmoa

Zatiketa Euklidearraren definizioaren arabera, bi zenbaki oso ${\displaystyle a}$ eta ${\displaystyle b}$ izanik, ${\displaystyle b>0}$, beste bi zenbaki oso ${\displaystyle q}$ eta ${\displaystyle r}$ existitzen dira eta bakarrak dira non

${\displaystyle a=bq+r}$

betetzen den, ${\displaystyle 0\leq r<|b|}$ izanik eta ${\displaystyle b}$-ren balio absolutua ${\displaystyle |b|}$ den. Hau da, ${\displaystyle a}$ zenbaki osoa ${\displaystyle b}$ zenbaki osoaz zatitzean ${\displaystyle q}$ zatidura eta ${\displaystyle r}$ hondarra lortzen dira.

Euklidesen algoritmoa zatiketa euklidearrean oinarritzen da eta bi zenbaki osoren zatitzaile komunetako handiena kalkulatzeko balio du. ${\displaystyle a}$ eta ${\displaystyle b}$ bi zenbakiren zatitzaile komunetako handiena adierazteko erabiltzen den notazioa ${\displaystyle zkh(a,b)}$ da.

Euklidesen algoritmoaren oinarrizko printzipioa ${\displaystyle zkh(a,b)=zkh(b,r)}$ da. Bertatik ondorioztatzen da ${\displaystyle zkh(a,0)=a}$ dela. Hortaz, Euklidesen algoritmoa erabiliz ${\displaystyle a}$ eta ${\displaystyle b}$ bi zenbakiren ${\displaystyle zkh(a,b)}$ zatitzaile komunetako handiena horrela kalkulatzen da:

1. ${\displaystyle b=0}$ bada ${\displaystyle zkh(a,b)=a}$ da.
2. Bestela, ${\displaystyle zkh(a,b)=zkh(b,r)}$ da, ${\displaystyle r}$ izanik ${\displaystyle a}$ eta ${\displaystyle b}$-ren arteko zatiketa euklidearraren hondarra.

Demagun ${\displaystyle a=r_{0}}$ eta ${\displaystyle b=r_{1}}$ notazioaz adierazten direla. ${\displaystyle zkh(a,b)}$ kalkulatzeko prozedura orokorra honakoa da:

Urratsa	a	b	Eragiketa	q	r	Esanahia
1	${\displaystyle r_{0}}$	${\displaystyle r_{1}}$	${\displaystyle r_{0}}$ zati ${\displaystyle r_{1}}$	${\displaystyle q_{1}}$	${\displaystyle r_{2}}$	${\displaystyle zkh(r_{0},r_{1})=zkh(r_{1},r_{2})}$
2	${\displaystyle r_{1}}$	${\displaystyle r_{2}}$	${\displaystyle r_{1}}$ zati ${\displaystyle r_{2}}$	${\displaystyle q_{2}}$	${\displaystyle r_{3}}$	${\displaystyle zkh(r_{1},r_{2})=zkh(r_{2},r_{3})}$
3	${\displaystyle r_{2}}$	${\displaystyle r_{3}}$	${\displaystyle r_{2}}$ zati ${\displaystyle r_{3}}$	${\displaystyle q_{3}}$	${\displaystyle r_{4}}$	${\displaystyle zkh(r_{2},r_{3})=zkh(r_{3},r_{4})}$
...
${\displaystyle n}$	${\displaystyle r_{n-1}}$	${\displaystyle r_{n}}$	${\displaystyle r_{n-1}}$ zati ${\displaystyle r_{n}}$	${\displaystyle q_{n}}$	${\displaystyle r_{n+1}}$	${\displaystyle zkh(r_{n-1},r_{n})=zkh(r_{n},r_{n+1})}$
${\displaystyle n+1}$	${\displaystyle r_{n}}$	${\displaystyle r_{n+1}}$	${\displaystyle r_{n}}$ zati ${\displaystyle r_{n+1}}$	${\displaystyle q_{n+1}}$	${\displaystyle 0}$	${\displaystyle zkh(r_{n},r_{n+1})=zkh(r_{n+1},0)}$

Hondarra txikituz doanez, azkenean 0 hondarra lortuko da eta prozedura amaituko da. ${\displaystyle a}$ eta ${\displaystyle b}$ zenbakien zatitzaile komunetako handiena ${\displaystyle 0}$ ez den azken hondarra da: ${\displaystyle r_{n+1}}$.

${\displaystyle zkh(a,b)=r_{n+1}}$

Adibidea.

${\displaystyle a=2366}$ eta ${\displaystyle b=273}$ izanik, ${\displaystyle zkh(2366,273)}$ horrela kalkulatzen da:

Urratsa	a	b	Eragiketa	q	r	Esanahia
1	${\displaystyle 2366}$	${\displaystyle 273}$	${\displaystyle 2366}$ zati ${\displaystyle 273}$	${\displaystyle 8}$	${\displaystyle 182}$	${\displaystyle zkh(2366,273)=zkh(273,182)}$
2	${\displaystyle 273}$	${\displaystyle 182}$	${\displaystyle 273}$ zati ${\displaystyle 182}$	${\displaystyle 1}$	${\displaystyle 91}$	${\displaystyle zkh(273,182)=zkh(182,91)}$
3	${\displaystyle 182}$	${\displaystyle 91}$	${\displaystyle 182}$ zati ${\displaystyle 91}$	${\displaystyle 2}$	${\displaystyle 0}$	${\displaystyle zkh(182,91)=zkh(91,0)}$

${\textstyle zkh(2366,273)=zkh(273,182)=zkh(182,91)=zkh(91,0)}$ sekuentziaren bidez, honakoa ondorioztatzen da: ${\displaystyle zkh(2366,273)=zkh(91,0)}$ eta ${\displaystyle zkh(91,0)=91}$ denez, ${\displaystyle zkh(2366,273)=91}$ da.

Orokortasuna

Euklidesen algoritmoak ez du zenbaki arruntetarako soilik balio; hondarra uzten duen zatiketa bat dagoen beste kasuetara ere orokor daiteke. Koefiziente arrazionalak dituzten polinomioen arteko zatiketa euklidearra ere definitu daitekeenez, haien arteko zatitzaile komunetako handiena kalkula daiteke.

Adibidea.

Euklidesen algoritmoaren bidez ${\displaystyle P(x)=x^{5}+2x^{3}+x}$ eta ${\displaystyle Q(x)=x^{4}-1}$ polinomioen arteko zatitzaile komunetako handiena horrela kalkulatzen da:

Urratsa	Eragiketa	Esanahia
1	${\displaystyle x^{5}+2x^{3}+x}$ zati ${\displaystyle x^{4}-1}$; hondarra: ${\displaystyle 2x^{3}+2x}$	${\displaystyle zkh(x^{5}+2x^{3}+x,x^{4}-1)=zkh(x^{4}-1,2x^{3}+2x)}$
2	${\displaystyle x^{4}-1}$ zati ${\displaystyle 2x^{3}+2x}$; hondarra: ${\displaystyle -x^{2}-1}$	${\displaystyle zkh(x^{4}-1,2x^{3}+2x)=zkh(2x^{3}+2x,-x^{2}-1)}$
3	${\displaystyle 2x^{3}+2x}$ zati ${\displaystyle -x^{2}-1}$; hondarra: ${\displaystyle 0}$	${\displaystyle zkh(2x^{3}+2x,-x^{2}-1)=zkh(-x^{2}-1,0)}$

Hortaz, ${\displaystyle P(x)}$ eta ${\displaystyle Q(x)}$ polinomioen zatitzaile komunetako handiena ${\displaystyle -x^{2}-1}$ dela ondorioztatzen da.

Deskribapen formala

Algoritmoa modu formalagoan adierazteko sasikodea erabil daiteke. Kasu honetan, "${\displaystyle x\;{\bmod {\;}}y}$" adierazpenaren esanahia "${\displaystyle x}$ zati ${\displaystyle y}$ eragiketarekin lortutako hondarra" da (ikus Aritmetika modular).

Algoritmo hau ez da eraginkorra konputagailuan inplementatua izateko, ${\displaystyle r_{i}}$ balio guztiak gordetzea eskatzen duelako.

Euklidesen algoritmo hedatua

Bi zenbaki osoren zatitzaile komunetako handiena haien konbinazio lineal moduan idatz daiteke. Formalki, ${\displaystyle a}$ eta ${\displaystyle b}$ bi zenbaki oso izanik, ${\displaystyle \mathrm {zkh} (a,b)=as+bt}$ betetzen duten ${\displaystyle s}$ eta ${\displaystyle t}$ koefiziente osoak existitzen dira, ${\displaystyle a\neq 0}$ edo ${\displaystyle b\neq 0}$ izanik. Gainera, ${\displaystyle \mathrm {zkh} (a,b)}$ da ${\displaystyle a}$ eta ${\displaystyle b}$ zenbakien konbinazio lineal moduan idatz daitekeen zenbaki oso positiborik txikiena. ${\displaystyle s}$ eta ${\displaystyle t}$ koefizienteak ez dira bakarrak.

Euklidesen algoritmo hedatuari esker, ${\displaystyle \mathrm {zkh} (a,b)}$ kalkulatzeaz gain ${\displaystyle s}$ eta ${\displaystyle t}$ koefiziente osoak kalkula daitezke.

Oinarrizko printzipioak

Euklidesen algoritmo hedatua azaltzeko, hainbat modu daude. Erabilienetako bat honako hau da:

1. Euklidesen algoritmoa erabiltzea. Urrats bakoitzean, ${\displaystyle a}$ zenbakia ${\displaystyle b}$ zenbakiaz zatitzean, ${\displaystyle q}$ zatidura eta ${\displaystyle r}$ hondarra lortzen dira. ${\displaystyle a=bq+r}$ ekuazioaren bidez adierazten da.
2. Ekuazio bakoitzean ${\displaystyle r}$ hondarra askatzen da (${\displaystyle r=a-bq}$).
3. Azken ekuazioaren hondarra azken-aurrekoan ordezkatzen da, eta azken-aurrekoa azken-aurrekoaren aurrekoan eta horrela lehenengo ekuaziora iritsi arte. Urrats bakoitzean ${\displaystyle r}$ hondarra zenbakien konbinazional lineal moduan adierazita agertuko da.

Aplikazioak

Zatikien sinplikazioa

Zatikiekin eragitean, sinplifikazioak egitea oso garrantzitsua gertatzen da. Esaterako, ${\displaystyle {\tfrac {65}{91}}}$ eta ${\displaystyle {\tfrac {5}{7}}}$ zatikiak baliokideak dira (ikus Zenbaki arrazional). Izan ere, ${\displaystyle c\neq 0}$ bada, ${\displaystyle {\tfrac {a}{b}}={\tfrac {ca}{cb}}}$ zatikiak baliokideak dira. Oro har, ${\displaystyle {\tfrac {a}{b}}}$ zatikia sinplifikatzeko, ${\displaystyle a}$ eta ${\displaystyle b}$ zenbakiak haien zatitzaile komunetako handienaz zatitu behar dira.

Adibidea.

${\displaystyle {\tfrac {166}{249}}}$ zatikia sinplifikatzeko, ${\displaystyle zkh(166,249)=83}$ denez, ${\displaystyle 166{\displaystyle \div }83=2}$ eta ${\displaystyle 249{\displaystyle \div }83=3}$ zatiketak egiten dira, eta ${\displaystyle {\tfrac {166}{249}}}$=${\displaystyle {\tfrac {2}{3}}}$ baliokideak direla ondorioztatzen da.

Zatiki jarraituak

Euklidesen algoritmoa aplikatzean egiten den zatiketa euklidear sorta ${\displaystyle {\tfrac {a}{b}}}$ zatikia zatiki jarraitu moduan adierazteko erabil daiteke. Izan ere, ${\displaystyle a=bq+r}$ eta ${\displaystyle r\neq 0}$ badira, zera betetzen da:

${\displaystyle {\frac {a}{b}}=q+{\frac {1}{\tfrac {b}{r}}}}$

Adibidea.

${\displaystyle {\tfrac {a}{b}}={\tfrac {93164}{5826}}}$ zatikia izanik, ${\displaystyle zkh(93164,5826)}$ Euklidesen algoritmoa erabiliz kalkulatzean, honako zatiketa euklidear sorta egiten da:

Urratsa	Eragiketa	q	r	Esanahia
1	${\displaystyle 93164}$ zati ${\displaystyle 5826}$	${\displaystyle 15}$	${\displaystyle 5774}$	${\displaystyle 93164=5826\times 15+5774}$
2	${\displaystyle 5826}$ zati ${\displaystyle 5774}$	${\displaystyle 1}$	${\displaystyle 52}$	${\displaystyle 5826=5774\times 1+52}$
3	${\displaystyle 5774}$ zati ${\displaystyle 52}$	${\displaystyle 111}$	${\displaystyle 2}$	${\displaystyle 5774=52\times 111+2}$
4	${\displaystyle 52}$ zati ${\displaystyle 2}$	${\displaystyle 26}$	${\displaystyle 0}$	${\displaystyle 52=2\times 26+0}$

Ekuazio horiek guztiak era honetan ere idatz daitezke:

1. ${\displaystyle {\frac {93164}{5826}}=15+{\frac {1}{\tfrac {5826}{5774}}}}$
2. ${\displaystyle {\frac {5826}{5774}}=1+{\frac {1}{\tfrac {5774}{52}}}}$
3. ${\displaystyle {\frac {5774}{52}}=111+{\frac {1}{\tfrac {52}{2}}}}$
4. ${\displaystyle {\frac {52}{2}}=26}$

Bigarren ekuazioa lehenengoan ordezkatuz gero, honakoa lortzen da:

${\displaystyle {\frac {93164}{5826}}=15+{\frac {1}{1+{\frac {1}{\tfrac {5774}{52}}}}}}$

Gainerakoak ere ordenatuz, honako adierazpena lortzen da:

${\displaystyle {\frac {93164}{5826}}=15+{\frac {1}{1+{\frac {1}{111+{\tfrac {1}{26}}}}}}}$

Oro har, zera baiezta daiteke:

${\displaystyle {\frac {a}{b}}=q_{1}+{\frac {1}{q_{2}+{\frac {1}{q_{3}+{\frac {1}{...q_{n-1}+{\tfrac {1}{q_{n}}}}}}}}}}$

Biderketarekiko alderantzizko modular

Artikulu nagusia: Biderketarekiko alderantzizko modular.

Bi zenbaki oso ${\displaystyle a}$ eta ${\displaystyle b}$ kongruenteak dira modulu ${\displaystyle m}$ , ${\displaystyle m}$ balioaz zatitzean hondar bera lortzen bada. Adibidez, 7 eta 12 kongruenteak dira modulu 5, 7 zenbakia eta 12 zenbakia 5ez zatitzean 2 hondarra lortzen delako. ${\displaystyle a}$ eta ${\displaystyle b}$ zenbakiak kongruenteak direla modulu ${\displaystyle m}$ adierazteko

${\displaystyle a\equiv b{\pmod {m}}}$

notazioa erabiltzen da. Aurreko adibideko kongruentzia, beraz, horrela adierazten da:

${\displaystyle 7\equiv 12{\pmod {5}}}$.

Demagun ${\displaystyle a,b}$ eta ${\displaystyle m}$ balioak ezagunak direla, baina honako kongruentzia betetzen duen ${\displaystyle x}$ ezezaguna dela:

${\displaystyle ax\equiv b{\pmod {m}}}$

${\displaystyle a^{-1}a\equiv 1{\pmod {m}}}$ betetzen duen ${\displaystyle a^{-1}}$ balioa aurkitu behar da. Horrela, aurreko ekuazioa ${\displaystyle a^{-1}}$-ekin biderkatuz, nahi den soluzioa lortuko da:

${\displaystyle x\equiv a^{-1}{\pmod {m}}}$

${\displaystyle a^{-1}}$ balioa ${\displaystyle a}$ren alderantzizkoa modulu ${\displaystyle m}$ dela esaten da.

Balio hori ez da beti existitzen. Esaterako, ${\displaystyle a=4}$ eta ${\displaystyle m=6}$ balioetarako ez da existitzen ${\displaystyle a^{-1}}$ zenbaki osorik non ${\displaystyle a^{-1}4\equiv 1{\pmod {6}}}$ betetzen den. Izan ere, ${\displaystyle a^{-1}}$ balioa existitzeko ${\displaystyle zkh(a,m)=1}$ bete behar da, hau da, zenbakiak elkarrekiko lehenak izan behar dute. Euklidesen algoritmo hedatua erabiltzean (${\displaystyle b=m}$) , ${\displaystyle 1=as+mt}$ lortzen bada, orduan ${\displaystyle s}$ balioa ${\displaystyle a}$ren alderantzizkoa da, modulu ${\displaystyle m}$. Adibidez, honako ekuazio hau ebatzi nahi bada:

${\displaystyle 5x\equiv 2{\pmod {9}}}$

Orduan, Euklidesen algoritmo hedatuarekin ${\displaystyle zkh(5,9)=1=5(2)+9(-1)}$ lortzen da. ${\displaystyle zkh(5,9)=1}$ denez, 5-ak badu alderantzizkoa modulu 9. Gainera, ${\displaystyle 1=5(2)+9(-1)}$ denez, alderantzizko hori 2 da. Hortaz,

${\displaystyle x\equiv 2(2){\pmod {9}}}$,

hau da, ${\displaystyle x=4}$ da.

Bézouten Identitatea

Artikulu nagusia: Bézouten identitate.

Bézouten identitateak zera dio: zeroren ezberdinak diren ${\displaystyle a}$ eta ${\displaystyle b}$ bi zenbaki oso eta ${\displaystyle d}$ haien zatitzaile komun handiena izanik, honakoa betetzen duten ${\displaystyle x}$ eta ${\displaystyle y}$ bi zenbaki oso existitzen direla:

${\displaystyle ax+by=d}$

${\displaystyle x}$ eta ${\displaystyle y}$ koefizienteak eta ${\displaystyle d=zkh(a,b)}$ haien zatitzaile komun handiena Euklidesen algoritmo hedatuaren bidez kalkula daitezke.

Algoritmoaren konplexutasuna

Lamé-ren teoremak baieztatzen du Euklidesen algoritmoa aplikatzean kasurik okerrena Fibonacci-ren segidako ondoz ondoko bi zenbakiren zatitzaile komunetako handiena kalkulatzean ematen dela.

Adibidea.

${\displaystyle f_{10}=55}$ eta ${\displaystyle f_{11}=89}$ zenbakien zatitzaile komunetako handiena kalkulatzeko honako eragiketak egin behar dira:

Urratsa	Eragiketa	q	r	Esanahia
1	${\displaystyle 89}$ zati ${\displaystyle 55}$	${\displaystyle 1}$	${\displaystyle 34}$	${\displaystyle zkh(89,55)=zkh(55,34)}$
2	${\displaystyle 55}$ zati ${\displaystyle 34}$	${\displaystyle 1}$	${\displaystyle 21}$	${\displaystyle zkh(55,34)=zkh(34,21)}$
3	${\displaystyle 34}$ zati ${\displaystyle 21}$	${\displaystyle 1}$	${\displaystyle 13}$	${\displaystyle zkh(34,21)=zkh(21,13)}$
4	${\displaystyle 21}$ zati ${\displaystyle 13}$	${\displaystyle 1}$	${\displaystyle 8}$	${\displaystyle zkh(21,13)=zkh(13,8)}$
5	${\displaystyle 13}$ zati ${\displaystyle 8}$	${\displaystyle 1}$	${\displaystyle 5}$	${\displaystyle zkh(13,8)=zkh(8,5)}$
6	${\displaystyle 8}$ zati ${\displaystyle 5}$	${\displaystyle 1}$	${\displaystyle 3}$	${\displaystyle zkh(8,5)=zkh(5,3)}$
7	${\displaystyle 5}$ zati ${\displaystyle 3}$	${\displaystyle 1}$	${\displaystyle 2}$	${\displaystyle zkh(5,3)=zkh(3,2)}$
8	${\displaystyle 3}$ zati ${\displaystyle 2}$	${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle zkh(3,2)=zkh(2,1)}$
9	${\displaystyle 2}$ zati ${\displaystyle 1}$	${\displaystyle 2}$	${\displaystyle 0}$	${\displaystyle zkh(2,1)=zkh(1,0)}$

Ikusten denez, bi digituko bi zenbaki horietarako 9 zatiketa egin behar izan dira. Oro har, egindako zatiketa kopurua zenbakiek duten digito kopurua bider 5 baino altuagoa ez da inoiz izango.

Konplexutasun konputazionalari dagokionez, ${\displaystyle n}$ eta ${\displaystyle m}$-ren ${\displaystyle zkh(n,m)}$ kalkulatzeko ${\displaystyle O(\log n)}$ zatiketa egin beharko dira, ${\displaystyle n>m}$ izanik.

Brigitte Valleek frogatu zuen bi zenbakiak ${\displaystyle n}$ bitetan adieraz badaitezke, orduan bataz bestean egin beharreko zatiketa kopurua ${\displaystyle {\tfrac {\pi ^{2}}{6}}n}$ dela.

Hala ere, ez da nahikoa zatiketa kopurua ezagutzea. Aurretik aipatu den moduan, Euklidesen algoritmoak polinomioetan eta zenbaki osoetan funtzionatzen du eta, oro har, edozein eremu euklidearretan. Kasu bakoitzean, algoritmoaren konplexutasuna egin behar den zatiketa kopuruaren eta zatiketa bakoitza egitearen kostuaren mende dago. Polinomioen kasuan, egin beharreko zatiketa kopurua ${\displaystyle O(\log n)}$ da, ${\displaystyle n}$ polinomioen gradua izanik.

Bibliografia

• von zur Gathen, Joachim; Gerhard, Jürgen (2003). «The Euclidean Algorithm». Modern Computer Algebra
• Cambridge University Press. ISBN 0-521-82646-2.
• Shoup, Victor (2008). «Euclid’s algorithm». A Computational Introduction to Number Theory and Algebra
• Cambridge University Press. ISBN 978-0-521-85154-1.
• Johnsonbaugh, Richard (2005). «Introducción a la teoría de números». Matemáticas Discretas. México: PEARSON EDUCACIÓN. ISBN 970-26-0637-3.
• Ralph P. Grimaldi (1998). «Propiedades de los números enteros: Inducción matemática». Matemáticas Discreta y Combinatoria. México: Addison Wesley Longman de México. ISBN 968-444-324-2.
• Lipschutz, Seymour; Lipson, Marc (2009). «Propiedades de los enteros». Matemáticas Discretas. McGraw-Hill. ISBN 978-970-10-7236-3.
• Brassard, Gilles; Bratley, Paul (1997). «Análisis de algoritmos». Fundamentos de Algoritmia. Madrid: PRENTICE HALL. ISBN 84-89660-00-X.
• Vallée, Brigitte (2002). «Dynamical Analysis of α-Euclidean Algorithms»
• Journal of Algorithms 44 (1). ISSN 0196-6774 , pp. 246-285.
• Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford (2009). «Number-Theoretic Algorithms». Introduction to Algorithms. The MIT Press. ISBN 978-0-262-53305-8.
• Barrera Mora, Fernando (2005). «Definiciones y resultados generales». Introducción a la Teoría de Grupos
• Publicaciones Electrónicas de la Sociedad Matemática Mexicana. ISBN 968-9161-02-4.
• Cárdenas, Humberto; Lluis, Emilio; Raggi, Francisco; Tomás, Francisco (2004). «Divisibilidad». Álgebra Superior. México: Trillas. ISBN 968-24-3783-0.
• Pérez Seguí, María Luisa (2006). «Divisibilidad». Teoría de Números. Instituto de Matemáticas, UNAM. ISBN 970-32-1170-0.
• Sánchez Velázquez, Jesús (1998). «Algoritmos para números grandes». Introducción al análisis de algoritmos. México: Trillas. ISBN 968-24-4341-5.
• Baldor, Aurelio (2008). «Máximo común divisor». Álgebra. México: Grupo Editorial Patria. ISBN 978-970-817-000-0.

Euklidesen algoritmoa polinomioekin

Izan bitez f, g ∈ K[x] eta deg f ≥ deg g. Zatiketaren algoritmoa erabiliz, f = gh + r non r = 0 edo deg r < deg g den. Orduan,

• r = 0 bada, g f-ren zatitzailea da eta bien zatitzaile komun handiena g-ren multiplo monikoa da;
• r 6= 0 bada, f eta g-ren zatitzaile komunak eta g eta r-ren zatitzaile komunak berdinak dira.

Bigarren kasuan, zatiketaren algoritmoa erabil dezakegu g eta r-rako eta lortzen dugun hondar berria 0 ez bada, r-ren maila baino txikiagoa izango du. Behin eta berriro erabiliko dugu algoritmoa hondarra 0 izan arte. Hori noizbait gertatuko da eta orduantxe erabili dugun zatitzailea moniko eginez, lortu dugu zatitzaile komun handienaren definizioa betetzen duen polinomioa. Hala dela ikusteko, polinomio horrek Bézouten identitatea betetzen dela ondorioztatzen da lehenengo. Hori Euklidesen algoritmoak ematen du, zenbakien kasuan ikusi dugun moduan. Behin identitate hori eskutan, argi dago f eta g-ren edozein zatitzailek lortu dugun polinomioa zatituko duela.

Kanpo estekak

• Datuak: Q230848
• Multimedia: Euclidean algorithm / Q230848