Ver la fonte de Algoritmu d'Euclides

El '''algoritmu d'Euclides''' ye un métodu antiguo y eficiente pa [[cálculu|calcular]] el [[máximu común divisor]] ('''MCD'''). Foi orixinalmente descritu por [[Euclides]] na so obra ''[[Elementos d'Euclides|Elementos]]''. El '''algoritmu d'Euclides estendíu''' ye un llixeru cambéu que dexa amás espresar al máximu común divisor como una [[combinación llinial]]. Esti algoritmu tien aplicaciones en diverses árees como [[álxebra]], [[teoría de númberos]] y [[ciencies de la computación]], ente otres. Con unos llixeros cambeos suel ser utilizáu n'ordenadores electrónicos por cuenta de la so gran eficiencia.

== Algoritmu orixinal de Euclides ==
[[Ficheru:Segmentos conmensurables.svg|lang=ast|thumb|''AB'' y ''CD'' los segmentos conmensurables.]]
[[Ficheru:Algoritmo de Euclides geométrico.svg|thumb|Exemplu del algoritmu orixinal de Euclides.]]
Na concepción griega de la matemática, los númberos entendíense como magnitúes xeométriques. Una tema recurrente na xeometría griega ye'l de la [[conmensurabilidad]] de dos [[segmentu|segmentos]]: dos segmentos (númberos) ''AB'' y ''CD'' son conmensurables cuando esiste un tercer segmentu ''PQ'' que cabo esautamente un númberu enteru de vegaes nos primeros dos; esto ye, ''PQ'' «mide» (mensura: midida) a los segmentos ''AB'' y ''CD''.

Non cualquier par de segmentos ye conmensurable, como atoparon los pitagóricos cuando establecen que'l llau y la diagonal d'un cuadráu nun son conmensurables, pero nel casu de dos segmentos conmensurables deseyar topar la mayor midida común posible.

Euclides describe na [[proposición]] VI I.2 de los sos [[Elementos d'Euclides|Elementos]] un métodu que dexa topar la mayor midida común posible de dos númberos (segmentos) que nun sían primos ente sigo, anque d'alcuerdu a la dómina tal métodu esplicar en términos xeométricos, lo que s'ilustra na siguiente trescripción.

<div style="width:75%">
{{cita|1='''P'atopar la máxima midida común de dos númberos que nun sían primos ente sigo.'''
[[Ficheru:Euclides VII-2.svg|center|200px]]
Sían ''AB'' y ''CD'' los dos númberos que nun son primos unu al otru. Precísase entós atopar la máxima midida común de ''AB'' y ''CD''.

Si ''CD'' mide ''AB'' entós ye una midida común yá que ''CD'' midir a sigo mesmu. Y ye manifiestu que tamién ye la mayor midida pos nada mayor a ''CD'' puede midir a ''CD''. Pero si ''CD'' nun mide a ''AB'' entós dalgún númberu va quedar de ''AB'' y ''CD'', el menor siendo de cutio restáu del mayor y que va midir al númberu que-y preciede. Porque una unidá nun va quedar pos si nun ye asina, ''AB'' y ''CD'' van ser primos unu del otru [Prop. VII.1], lo cual ye lo contrario de lo que se supunxo.

Poro, dalgún númberu queda que va midir el númberu que-y preciede. Y seya ''CD'' midiendo ''BE'' dexando ''EA'' menor que sí mesmu y seya ''EA'' midiendo '' DF'' dexando ''FC'' menor que sí mesmu y seya ''FC'' midida de ''AE''. Entós, como ''FC'' mide ''AE'' y ''AE'' mide ''DF'', ''FC'' va ser entós midida de ''DF''. Y tamién se mide a sigo mesmu. Por tanto tamién va midir tou ''CD''. Y ''CD'' mide a ''BE''. Entós ''CF'' mide a ''BE'' y tamién mide a ''EA''. Asina mide a tou ''BA'' y tamién mide a ''CD''. Esto ye, ''CF'' mide tanto a ''AB'' y ''CD'' polo que ye una midida común de ''AB'' y ''CD''.

Afirmo que tamién ye la mayor midida común posible porque si nun lu fora, entós un númberu mayor que ''CF'' mide a los númberos ''AB'' y ''CD'', seya ésti ''G''. Puesto que ''G'' mide a ''CD'' y ''CD'' mide a ''BE'', ''G'' tamién mide a ''BE''. Amás, mide a tou ''BA'' polo que mide tamién a la residuu ''AE''. Y ''AE'' mide a ''DF'' polo que ''G'' tamién mide a ''DF''. Mide tamién a tou ''DC'' polo que mide tamién a la residuu ''CF'', ye dicir el mayor mide al menor, lo cual ye imposible.

Poro, nengún númberu mayor a ''CF'' puede midir a los númberos ''AB'' y ''CD''. Entós ''CF'' ye la mayor midida común de ''AB'' y ''CD'', lo cual quería demostrase.
|2=[[Euclides]]. ''[[Elementos d'Euclides|Elementos]] VII.2''}}</div>

En llinguaxe modernu, l'algoritmu descríbese como sigue:
# Daos dos segmentos ''AB'' y ''CD'' (con ''AB>CD''), restamos ''CD'' de ''AB'' tantes vegaes como seya posible. Si nun hai residuu, entós ''CD'' ye la máxima midida común.
# Si llógrase un residuu ''EA'', ésti ye menor que ''CD'' y podemos repitir el procesu: restamos ''EA'' tantes vegaes como seya posible de ''CD''. Si a la fin nun queda una residuu, ''EA'' ye la midida común. En casu contrariu llogramos una nueva residuu ''FC'' menor a EA.
# El procesu repitir hasta qu'en dalgún momentu nun se llogra residuu. Entós la última residuu llograda ye la mayor midida común.

El fechu de que los segmentos son conmesurables ye clave p'asegurar que'l procesu termina tarde o aína

== Algoritmu d'Euclides tradicional ==
Al [[Algoritmu de la división|estremar]] <math>a</math> ente <math>b</math> (númberos enteros), llógrase un [[División (matemátiques)|cociente]] <math>q</math> y un [[Restu|residuu]] <math>r</math>. Ye posible demostrar que'l máximu común divisor de <math>a</math> y <math>b</math> ye'l mesmu que'l de <math>b</math> y <math>r</math>(Sía c el máximu común divisor de <math>a</math> y <math>b</math>,.Como <math>a=bq+r</math> y <math>c</math> estrema a <math>a</math> y a <math>b</math> estrema tamién a <math>r</math>. Si esistiera otru númberu mayor que <math>c</math> qu'estrema a <math>b</math> y a <math>r</math>, tamién estremaría a <math>a</math> , polo que <math>c</math> nun sería'l mcd de <math>a</math> y <math>b</math>, lo que contradiz la hipótesis). Ésti ye'l fundamentu principal del algoritmu. Tamién ye importante tener en cuenta que'l máximu común divisor de cualquier númberu <math>a</math> y <math>0</math> ye precisamente <math>a</math>. Pa fines práuticos, la notación <math>\mathrm{mcd}(a,b)</math> significa ''máximu común divisor de <math>a</math> y <math>b</math>''.

Según lo antes mentáu, pa calcular el máximu común divisor de 2366 y 273 puede prosiguir de la siguiente manera:
{| {{tablaguapa}}
!Pasu!!Operación!!Significáu
|-
|1||2366 estremáu ente 273 ye 8 y sobren 182||<math>\mathrm{mcd}(2366,273)=\mathrm{mcd}(273,182)</math>
|-
|2||273 estremáu ente 182 ye 1 y sobren 91||<math>\mathrm{mcd}(273,182)=\mathrm{mcd}(182,91)</math>
|-
|3||182 estremáu ente 91 ye 2 y arrayadura 0||<math>\mathrm{mcd}(182,91)=\mathrm{mcd}(91,0)</math>
|}
La secuencia d'igualdaes <math>\mathrm{mcd}(2366,273)=\mathrm{mcd}(273,182)=\mathrm{mcd}(182,91)=\mathrm{mcd}(91,0)</math> impliquen que <math>\mathrm{mcd}(2366,273)=\mathrm{mcd}(91,0)</math>. Puesto que <math>\mathrm{mcd}(91,0)=91</math>, entós conclúyese que <math>\mathrm{mcd}(2366,273)=91</math>. Este mesmu procedimientu puede aplicase a cualesquier dos númberos naturales. Polo xeneral, si deseyar atopar el máximu común divisor de dos númberos naturales <math>a</math> y <math>b</math>, síguense les siguientes regles:
# Si <math>b=0</math> entós <math>\mathrm{mcd}(a,b)=a</math> y l'algoritmu termina #
N'otru casu, <math>\mathrm{mcd}(a,b)=\mathrm{mcd}(b,r)</math> onde <math>r</math> ye'l restu d'estremar <math>a</math> ente <math>b</math>. Pa calcular <math>\mathrm{mcd}(b,r)</math> utilícense estes mesmes regles

Asuma que llamamos <math>a=r_0</math> y <math>b=r_1</math>. Aplicando estes regles llógrase la siguiente secuencia d'operaciones:
{| {{tablaguapa}}
!Pasu!!Operación!!Significáu
|-
|1||<math>r_0</math> estremáu ente <math>r_1</math> ye <math>q_1</math> y sobren <math>r_2</math>||<math>\mathrm{mcd}(r_0,r_1)=\mathrm{mcd}(r_1,r_2)</math>
|-
|2||<math>r_1</math> estremáu ente <math>r_2</math> ye <math>q_2</math> y sobren <math>r_3</math>||<math>\mathrm{mcd}(r_1,r_2)=\mathrm{mcd}(r_2,r_3)</math>
|-
|3||<math>r_2</math> estremáu ente <math>r_3</math> ye <math>q_3</math> y sobren <math>r_4</math>||<math>\mathrm{mcd}(r_2,r_3)=\mathrm{mcd}(r_3,r_4)</math>
|-
|<math>\vdots</math>||<math>\vdots</math>||<math>\vdots</math>
|-
|<math>n</math>||<math>r_{n-1}</math> estremáu ente <math>r_n</math> ye <math>q_n</math> y sobren <math>r_{n+1}</math>||<math>\mathrm{mcd}(r_{n-1},r_n)=\mathrm{mcd}(r_n,r_{n+1})</math>
|-
|<math>n+1</math>||<math>r_n</math> estremáu ente <math>r_{n+1}</math> ye <math>q_{n+1}</math> y arrayadura <math>0</math>||<math>\mathrm{mcd}(r_n,r_{n+1})=\mathrm{mcd}(r_{n+1},0)</math>
|}
Como la socesión de residuos va menguando, a la fin una residuu tien que ser cero y ye nesi momentu cuando l'algoritmu termina. El máximu común divisor ye precisamente <math>r_{n+1}</math> (la última residuu que nun ye cero).

=== Xeneralización ===
En realidá l'algoritmu d'Euclides funciona non yá pa los númberos naturales, sinón pa cualesquier elementos nos qu'esista una "división con residuu". A esti tipu de divisiones llámase-yos [[División euclidiana|divisiones euclidianes]] y a los conxuntos onde puede definise dicha división llámase-yos [[Dominiu euclídeo|dominios euclídeos]]. Por casu, el conxuntu de los [[Númberu enteru|númberos enteros]] y el de los [[polinomiu|polinomios]] con coeficientes racionales son dominios euclídeos porque podemos definir una división con residuu (vease [[División polinomial]]). D'esta manera, puede calculase el máximu común divisor de dos númberos enteros o de dos polinomios.

Por casu, pa calcular el máximu común divisor de los polinomios <math>P(x)=x^5+2x^3+x</math> y <math>Q(x)=x^4-1</math> l'algoritmu d'Euclides suxer la siguiente secuencia d'operaciones:
{| {{tablaguapa}}
!Pasu!!Operación!!Significáu
|-
|1||<math>x^5+2x^3+x</math> estremáu ente <math>x^4-1</math> ye <math>x</math> y arrayadura <math>2x^3+2x</math>||<math>\mathrm{mcd}(x^5+2x^3+x,x^4-1)=\mathrm{mcd}(x^4-1,2x^3+2x)</math>
|-
|2||<math>x^4-1</math> estremáu ente <math>2x^3+2x</math> ye <math>\textstyle{\frac12x}</math> y arrayadura <math>-x^2-1</math>||<math>\mathrm{mcd}(x^4-1,2x^3+2x)=\mathrm{mcd}(2x^3+2x,-x^2-1)</math>
|-
|3||<math>2x^3+2x</math> estremáu ente <math>-x^2-1</math> ye <math>-2x</math> y arrayadura 0||<math>\mathrm{mcd}(2x^3+2x,-x^2-1)=\mathrm{mcd}(-x^2-1,0)</math>
|}
D'esta manera conclúyese que'l so máximu común divisor ye <math>-x^2-1</math>.

=== Descripción formal ===
Puede espresase esti algoritmu de manera más formal usando [[pseudocódigo]]. Nesti casu la espresión "<math>x \; \bmod \; y</math>" significa "la residuu d'estremar <math>x</math> ente <math>y</math>" (vease [[Aritmética modular]]).
{{Algoritmu|de Euclides|
'''Entrada:''' Valores <math>a</math> y <math>b</math> pertenecientes a un dominiu euclídeo

'''Salida:''' Un máximu común divisor de <math>a</math> y <math>b</math>
# <math>r_0\gets a</math>, <math>r_1\gets b</math>
# <math>i\gets1</math>
# '''Mientres''' <math>r_i\neq 0</math> '''faiga lo siguiente:'''
## <math>r_{i+1}\gets r_{i-1}\;\bmod\; r_i</math>
## <math>i\gets i+1</math>
# '''La resultancia ye:''' <math>r_{i-1}</math>
|1}}
Vale la pena notar qu'esti algoritmu nun ye eficiente ser implementáu direutamente nun ordenador, yá que riquiría memorizar tolos valores de <math>r_i</math>.

== Algoritmu d'Euclides estendíu ==
L'algoritmu d'Euclides estendíu dexa, amás d'atopar un máximu común divisor de dos númberos enteros <math>a</math> y <math>b</math>, espresalo como la mínima combinación llinial d'esos númberos, esto ye, atopar númberos enteros <math>s</math> y <math>t</math> tales que <math>\mathrm{mcd}(a,b)=a s+b t</math>. Esto xeneralízase tamién escontra cualquier dominiu euclideano.

=== Fundamentos ===
Esisten delles maneres d'esplicar l'algoritmu d'Euclides estendíu, una de les más comunes consiste na siguiente:
# Usar l'algoritmu tradicional de Euclides. En cada pasu, en llugar de "<math>a</math> estremáu ente <math>b</math> ye <math>q</math> y de restu <math>r</math>" escríbese la ecuación <math>a=b q+r</math> (vease [[algoritmu de la división]]).
# Esténase'l restu de cada ecuación.
# Sustitúyese'l restu de la última ecuación na penúltima, y la penúltima na antepenúltima y asina socesivamente hasta llegar a la primer ecuación, y en tou pasu espresa cada restu como combinación llinial.

Sicasí, n'ares de la comprensión y memorización d'esti algoritmu, ye conveniente conocer la siguiente carauterización.
Pa multiplicar dos matrices de tamañu <math>2\times 2</math> úsase la siguiente fórmula (vease [[Productu de matrices]]):
{{Ecuación | <math>\begin{bmatrix}y&f\\g&h\end{bmatrix}\times\begin{bmatrix}a&b\\c&d\end{bmatrix}=\begin{bmatrix}y a+f c&y b+f d\\g a+h c&g b+h d\end{bmatrix}</math>|1}}
Supóngase que s'utiliza l'algoritmu d'Euclides tradicional pa calcular los valores <math>q_i</math> y <math>r_i</math> qu'ende se describen. Per cada valor <math>q_i</math> calculáu puede formase la matriz <math>\textstyle Q_i=\begin{bmatrix}0&1\\1&-q_i\end{bmatrix}</math>. Usando la ecuación {{Eqnref|1}} de manera repitida puede calculase el productu de les primeres <math>i</math> matrices d'esti tipu:
{{Ecuación | <math>\begin{bmatrix}s_i&t_i\\s_{i+1}&t_{i+1}\end{bmatrix}=\begin{bmatrix}0&1\\1&-q_i\end{bmatrix}\times \begin{bmatrix}0&1\\1&-q_{i-1}\end{bmatrix}\times\cdots\times \begin{bmatrix}0&1\\1&-q_1\end{bmatrix}</math>}}

Resulta ser que los valores <math>s_i</math> y <math>t_i</math> tienen la propiedá de que <math>r_i=a s_i+b t_i</math>, esto ye, espresen a <math>r_i</math> como una combinación llinial de <math>a</math> y <math>b</math>. Particularmente, como <math>\mathrm{mcd}(a,b)=r_{n+1}</math> entós tiense <math>\mathrm{mcd}(a,b)=a s_{n+1}+b t_{n+1}</math>, lo cual ye la solución del problema. Esta propiedá nun tendría de ser sorprendente, pos esta multiplicación de matrices equival al métodu antes descritu onde se substituye cada ecuación na anterior.<!--Pero nun voi asitiar la demostración nuna enciclopedia--> Ye importante calcular <math>Q_i\times\cdots\times Q_3\times Q_2\times Q_1</math> nesi mesmu orde. La matriz <math>Q_1</math> apaez nel estremu derechu y la matriz <math>Q_i</math> nel esquierdu.

Tornando al primer exemplu, la socesión de cocientes ye <math>q_1=8</math>, <math>q_2=1</math> y <math>q_3=2</math>. Entós puede calculase
{{Ecuación | <math>\begin{bmatrix}-1&9\\3&-26\end{bmatrix}=\begin{bmatrix}0&1\\1&-2\end{bmatrix}\times \begin{bmatrix}0&1\\1&-1\end{bmatrix}\times \begin{bmatrix}0&1\\1&-8\end{bmatrix}</math>}}
Utilizando'l primera renglón d'esta matriz puede lleese que <math>91=2366(-1)+273(9)</math>, esto ye, atopóse la manera d'espresar al máximu común divisor de 2366 y 273 como una combinación llinial.

=== Descripción formal ===
Pa espresar l'algoritmu d'Euclides estendíu ye conveniente notar la manera en que se calculen los valores <math>s_i</math> y <math>t_i</math> cola multiplicación de matrices:
{{Ecuación | <math>\begin{bmatrix}s_i&t_i\\s_{i+1}&t_{i+1}\end{bmatrix} =
\begin{bmatrix}s_i&t_i\\s_{i-1}-q_is_i&t_{i-1}-q_it_i\end{bmatrix} = \begin{bmatrix}0&1\\1&-q_i\end{bmatrix}\times\begin{bmatrix}s_{i-1}&t_{i-1}\\s_i&t_i\end{bmatrix}</math>}}
D'esta manera <math>s_{i+1} = s_{i-1}-q_is_i</math> y amás <math>t_{i+1} = t_{i-1}-q_it_i</math>. Polo tanto l'algoritmu en pseudocódigo puede espresase como sigue:
{{Algoritmu|de Euclides estendíu|
'''Entrada:''' Valores <math>a</math> y <math>b</math> pertenecientes a un dominiu euclídeo

'''Salida:''' Un máximu común divisor de <math>a</math> y <math>b</math>, y valores <math>s</math> y <math>t</math> tales que <math>\mathrm{mcd}(a,b)=as+bt</math>
# <math>r_0\gets a, r_1\gets b, s_0\gets 1, t_0\gets 0, s_1\gets 0, t_1\gets 1</math>
# <math>i\gets 1</math>
# '''Mientres''' <math>r_i\neq0</math> '''faiga lo siguiente:'''
## Estreme <math>r_{i-1} </math> ente <math>r_i </math> pa llograr el cociente <math>q_i </math> y la residuu <math>r_{i+1} </math>
## <math>s_{i+1}\gets s_{i-1}-q_is_i</math>
## <math>t_{i+1}\gets t_{i-1}-q_it_i</math>
## <math>i\gets i+1</math>
# '''La resultancia ye:''' <math>r_{i-1} </math> ye un máximu común divisor de <math>a </math> y <math>b </math> y esprésase <math>r_{i-1}=as_{i-1}+bt_{i-1} </math>
|2}}

== Aplicaciones ==

=== Simplificar fracciones ===
Al momentu de faer cálculos con fracciones, ye de gran importancia saber cómo simplificales. Por casu, la fracción <math>\textstyle\frac{65}{91}</math> ye equivalente con <math>\textstyle\frac 5 7</math> (vease [[Númberu racional]]). De manera más xeneral, <math>\textstyle\frac ab=\frac {ca}{cb}</math> siempres que <math>c\ne0</math>. P'amenorgar una fracción cualesquier <math>\textstyle\frac a b</math>, namái se precisa estremar <math>a</math> y <math>b</math> ente'l so máximu común divisor.

Por casu, si deseyar amenorgar <math>\textstyle\frac{166}{249}</math>, primero úsase l'algoritmu d'Euclides p'atopar <math>\mathrm{mcd}(166,249)=83</math>. Fáense les divisiones <math>\textstyle 166\div 83 = 2</math> y <math>\textstyle 249\div 83 = 3</math>. Depués entós conclúyese que <math>\textstyle\frac{166}{249}=\frac 2 3</math>.

=== Fracciones continues ===
La socesión de divisiones que s'efectúen al siguir algoritmu d'Euclides puede ser utilizada pa espresar una fracción cualesquier <math>\textstyle\frac a b</math> como [[fracción continua]]. Esto debe a que si <math>a = bq + r</math> y <math>r\neq 0</math>, entós {{ecuación|<math>\frac 
a b = q + \frac 1 {\frac b r}</math>|3}}

Por casu, p'atopar el máximu común divisor de <math>93164</math> y <math>5826</math> l'algoritmu xenera la siguiente secuencia de divisiones:
{| {{tablaguapa}}
!Pasu!!Operación!!Significáu
|-
|1||93164 estremáu ente 5826 ye 15 y sobren 5774||<math>93164=5826\times 15+5774</math>
|-
|2||5826 estremáu ente 5774 ye 1 y sobren 52||<math>5826=5774\times 1+52</math>
|-
|3||5774 estremáu ente 52 ye 111 y sobren 2||<math>5774=52\times 111+2</math>
|-
|4||52 estremáu ente 2 ye 26 y arrayadura 0||<math>52=2\times 26+0</math>
|}

Toes estes ecuaciones podemos facer asemeyaes a la ecuación {{eqnref | 3}}:
# <math>\textstyle\frac{93164}{5826}=15+ \frac 1 {\frac{5826}{5774}}</math>
# <math>\textstyle\frac{5826}{5774}=1+ \frac 1 {\frac{5774}{52}}</math>
# <math>\textstyle\frac{5774}{52}=111+ \frac 1 {\frac{52}{2}}</math>
# <math>\textstyle\frac{52}{2}=26</math>

Si sustitúi la segunda ecuación na primera, llógrase {{Ecuación|<math>\frac{93164}{5826}=15+ 
\frac 1 {1+ \frac 1 {\frac{5774}{52}}}</math>}}

Si repite esti procesu de sustitución entós llógrase la espresión deseyada:
{{Ecuación|<math>\frac{93164}{5826}=15+ \frac 1 {1+ \frac 1 {111+ \frac 1 {26}}}</math>}}

De manera más xeneral, la fracción continua atopada con esti algoritmu siempres ye de formar
{{Ecuación|<math>\frac{a}{b}=q_1+ \frac 1 {q_2+ \frac 1 {q_3+ \frac 1 {\ddots q_{n-1}+ \frac 1 {q_n}}}}</math>}}

<!-- Esto va na sección siguiente: Volviendo al casu <math>a</math> y <math>b</math> enteros, l'algoritmu d'Euclides dexa atopar los coeficientes enteros <math>o</math> y <math>v</math> de la [[identidá de Bézout]] <math>au+bv=\mathrm{mcd}(a, b)</math> de fundamental importancia na [[aritmética]]. -->

=== Inversos módulu ''m''=== 

{{AP|inversu multiplicativu (aritmética modular)}}
Dicimos que dos númberos enteros son ''congruentes módulu <math>m</math>'' (anque tamién puede xeneralizase pa cualesquier otru dominiu euclídeo) si al estremalos ente <math>m</math> llogramos la mesma residuu (vease [[Congruencia]]). Por casu, 7 ye congruente con 12 módulu 5 porque al estremar 7 ente 5 y 12 ente 5, en dambos casos llogramos la mesma residuu (que ye 2). Cuando <math>a</math> ye congruente con <math>b</math> módulu <math>m</math> escríbese <math>a\equiv b\pmod m</math>, nel exemplu anterior tiense <math>7\equiv 12\pmod 5</math>. Supóngase que se conocen los valores de <math>a</math>, <math>b</math> y <math>m</math>, pero que se desconoz el valor <math>x</math> na siguiente congruencia:
{{Ecuacion |<math>a x\equiv b\pmod m</math>|2}}
Basta atopar un valor <math>a^{-1}</math> que satisfaiga: <math>a^{-1} a\equiv 1\pmod m</math>, pos d'esta manera al multiplicar la ecuación {{eqnref|2}} por <math>a^{-1}</math> va tenese la solución deseyada:
{{Ecuacion | <math>x\equiv a^{-1} b\pmod m</math>}}
Al elementu <math>a^{-1}</math> llámase-y "inversu módulu <math>m</math>" de <math>a</math>. Desafortunadamente esti valor non siempres esiste. Por casu, con <math>a=4</math> y <math>m=6</math> nun esiste nengún númberu enteru <math>a^{-1}</math> tal que <math>a^{-1} 4\equiv 1\pmod 6</math>. De fechu esti valor esiste si y namái si <math>\mathrm{mcd}(a,m)=1</math> (la esistencia de soluciones depende de la condición <math>\mathrm{mcd}(a,m)|b </math>, ente que la unicidá depende de que'l <math>\mathrm{mcd}(a,m)=1</math>). Entá más, si al usar l'algoritmu d'Euclides estendíu (agora con <math>b=m</math>) llógrase <math>1=as+mt</math>, entós el valor <math>s</math> ye l'inversu módulu <math>m</math> de <math>a</math>. <!--LA DEMOSTRACIÓN NUN YE BONX ASITIALA NA ENCICLOPEDIA-->
Por casu, deseyar resolver la ecuación
{{Ecuacion |<math>5 x\equiv 2\pmod 9</math>}}
Entós col algoritmu d'Euclides estendíu llógrase que <math>\mathrm{mcd}(5,9)=1=5(2)+9(-1)</math>. Como <math>\mathrm{mcd}(5,9)=1</math> entós 5 tien un inversu módulu <math>9</math>. Entá más, como <math>1=5(2)+9(-1)</math>, entós esi inversu ye 2. Entós
{{Ecuacion |<math>x\equiv 2(2)\pmod 9</math>}}
Ye dicir que'l valor de <math>x</math> ye <math>4</math>.

== Complexidá del algoritmu ==
[[Ficheru:Euclidean algorithm running time X Y.png|thumb|230px|Gráfica del númberu de divisiones efectuaes nel algoritmu d'Euclides. El colloráu indica poques operaciones, ente que los colores eventualmente más azules representen mayor númberu d'operaciones.]]

El teorema de Lamé afirma que'l casu peor pa esti algoritmu ye cuando se-y pide calcular el máximu común divisor de dos númberos consecutivos de la [[socesión de Fibonacci]]. Por casu, si deseyar calcular el máximu común divisor de <math>f_{10}=55</math> y <math>f_{11}=89</math> llógrase la siguiente secuencia d'operaciones:

{| {{tablaguapa}}
!Pasu!!Operación!!Significáu
|-
|1||89 estremáu ente 55 ye 1 y sobren 34||<math>\mathrm{mcd}(89,55)=\mathrm{mcd}(55,34)</math>
|-
|2||55 estremáu ente 34 ye 1 y sobren 21||<math>\mathrm{mcd}(55,34)=\mathrm{mcd}(34,21)</math>
|-
|3||34 estremáu ente 21 ye 1 y sobren 13||<math>\mathrm{mcd}(34,21)=\mathrm{mcd}(21,13)</math>
|-
|4||21 estremáu ente 13 ye 1 y sobren 8||<math>\mathrm{mcd}(21,13)=\mathrm{mcd}(13,8)</math>
|-
|5||13 estremáu ente 8 ye 1 y sobren 5||<math>\mathrm{mcd}(13,8)=\mathrm{mcd}(8,5)</math>
|-
|6||8 estremáu ente 5 ye 1 y sobren 3||<math>\mathrm{mcd}(8,5)=\mathrm{mcd}(5,3)</math>
|-
|7||5 estremáu ente 3 ye 1 y sobren 2||<math>\mathrm{mcd}(5,3)=\mathrm{mcd}(3,2)</math>
|-
|8||3 estremáu ente 2 ye 1 y sobren 1||<math>\mathrm{mcd}(3,2)=\mathrm{mcd}(2,1)</math>
|-
|9||2 estremáu ente 1 ye 2 y arrayadura 0||<math>\mathrm{mcd}(2,1)=\mathrm{mcd}(1,0)</math>
|}

Nesti exemplu reparar que con estos dos númberos de dos díxitos decimales, precísase faer 9 divisiones. Polo xeneral, el númberu de divisiones efectuaes pol algoritmu nunca supera 5 vegaes el númberu de díxitos que tienen estos númberos. En términos de [[complexidá computacional]], esto significa que se riquir <math> O(\log n)</math> divisiones pa calcular el máximu común divisor de <math>n</math> y <math>m</math> onde <math>n>m</math>.

El númberu permediu de divisiones efectuaes pol algoritmu tuvo investigándose dende 1968, pero namái hasta apenes l'añu 2002, Brigitte Vallée demostró que si los dos númberos pueden representase con <math>n</math> bits, entós el númberu permediu de divisiones necesaries ye <math>\textstyle{\frac{\pi^2}{6}n}</math>.

Sicasí, nun basta con saber el númberu de divisiones. Hai que recordar que l'algoritmu d'Euclides funciona tantu pa polinomios como pa númberos enteros, y polo xeneral, cualquier dominiu Euclídeo. En cada casu, la complexidá del algoritmu depende del númberu de divisiones efectuaes y del costu de cada división. Nel casu de los polinomios, el númberu de divisiones ye <math>O(\log n)</math> onde <math>n</math> ye'l grau de los polinomios.

== Implementación en pseudocódigo ==
Polo xeneral, los algoritmos {{Algref|1}} y {{Algref|2}} nun son bien apoderaos pa implementase direutamente nun llinguaxe de programación, especialmente porque peracaben muncha memoria. Si nun se precisen los valores entemedios, y namái se desea calcular el máximu común divisor de dos númberos enteros, convien usar estes variantes:

{{Algoritmu|de Euclides tradicional implementáu de manera recurrente|
'''Función''' <math>\mathrm{mcd}(a,b)</math>''':'''
:'''Si''' <math>b=0 </math> '''entós:'''
::'''La resultancia ye''' <math>a </math>
:'''N'otru casu:'''
::'''La resultancia ye''' <math>\mathrm{mcd}(b,a\;\bmod \; b)</math>
}}
{{Algoritmu|de Euclides tradicional implementáu de manera iterativa|
'''Función''' <math>\mathrm{mcd}(a,b)</math>''':'''
:'''Mientres''' <math>b\ne0</math> '''faiga lo siguiente:'''
::<math>(a,b)\gets(b,a\;\bmod \; b)</math>
:'''La resultancia ye''' <math>a </math>
}}
{{Algoritmu|de Euclides estendíu implementáu de manera recurrente|
'''Función''' <math>{\rm Euclides}(a,b)</math>''':'''
:'''Si''' <math>b=0 </math> '''entós:'''
::'''La resultancia ye''' <math>(a,1,0)</math>
:'''N'otru casu:'''
::<math>(d,s,t)\gets{\rm Euclides}(b,a\;\bmod \; b)</math>
::'''La resultancia ye''' <math>(d,t,s-(a\div b) t)</math>
}}
{{Algoritmu|de Euclides estendíu implementáu de manera iterativa|
'''Función''' <math>{\rm Euclides}(a,b)</math>''':'''
:<math>(s,t,s^\prime,t^\prime)\gets(1,0,0,1)</math>
:'''Mientres''' <math>b\ne0</math> '''faiga lo siguiente:'''
::Estreme <math>a </math> ente <math>b </math> pa llograr un cociente <math>q </math> y una residuu <math>r </math>
::<math>(a,s,t,b,s^\prime,t^\prime)\gets(b,s^\prime,t^\prime,r,s-s^\prime q,t-t^\prime q)</math>
:'''La resultancia ye''' <math>(a,s,t)</math>
}}
{{Algoritmu|de Euclides estendíu implementáu de manera iterativa con matrices|
'''Función''' <math>{\rm Euclides}(a,b)</math>''':'''
:<math>Q\gets\begin{pmatrix}1&0\\0&1\end{pmatrix}</math>
:'''Mientres''' <math>b\ne0</math> '''faiga lo siguiente:'''
::Estreme <math>a </math> ente <math>b </math> pa llograr un cociente <math>q </math> y una residuu <math>r </math>
::<math>Q\gets\begin{pmatrix}0&1\\1&-q\end{pmatrix}\times Q</math>
::<math>(a,b)\gets(b,r)</math>
:'''La resultancia ye''' <math>(a,Q_{1 1},Q_{1 2})</math>
}}
Alrodiu de la notación emplegada:
* <math>x\gets y</math> significa "asigne a la variable <math>x</math> el valor actual de <math>y</math>". En llinguaxes como [[Llinguaxe C|C]], [[Llinguaxe de programación Java|Java]], [[C#]], [[Python]] y [[Visual Basic]] esto significa a cencielles <code>x = y</code>. N'otros llinguaxes como [[Llinguaxe de programación Pascal|Pascal]] traducir en <code>a := b</code>, en [[Maxima]] ye <code>a : b</code>, en [[R-project|R]], S y [[Ocaml]] ye <code>x <- y</code>, y inclusive utilízase la flecha <code>x ← y</code> como'l casu d'[[APL]].
* <math>(x,y,z)\gets(a,b,c)</math> significa que primero s'evalúen los valores <math>a,b,c</math> y depués asígnase <math>x\gets a,y\gets b,z\gets c</math>, etc. En llinguaxes como Python, [[Ruby]] o Maxima esta instrucción tien una estructura bien similar, como por casu en Python: <code>(x,y,z) = (a,b,c)</code>. N'otros llinguaxes ye necesariu l'usu de variables auxiliares, como por casu en llinguaxe C: <code>aux1 = b; aux2 = c; x = a; y = aux1; z = aux2;</code>.
* <math>a\div b</math> significa "el cociente d'estremar <math>a</math> ente <math>b</math>". A esta operación conózse-y tamién como la ''división truncada'' porque ataya la parte fraccionaria del númberu. En munchos llinguaxes de programación esto impleméntase a cencielles como <code>a/b</code>. Otres maneres son <code>a\b</code> (Visual Basic) , <code>a div b</code> (Pascal) o bien <code>a//b</code> (Python 3).
* <math>a\; \bmod \; b</math> significa "la residuu d'estremar <math>a</math> ente <math>b</math>". A esta operación conózse-y a cencielles como ''módulu''. En munchos llinguaxes de programación impleméntase como <code>a % b</code>, ente que n'otros ye <code>a mod b</code> (Visual Basic o Pascal) o bien <code>a rem b</code> (Ada).

== Ver tamién ==
* [[Discutiniu:Algoritmu d'Euclides|Implementaciones en llinguaxes na parte de discutiniu]]

== Referencies ==
{{llistaref}}

== Bibliografía ==
<!-- Encamiento revisalos nesti orde (asina influyeron na redacción del artículu)-->
* {{cita llibru |
autor = von zur Gathen, Joachim; Gerhard, Jürgen
| capítulu = The Euclidean Algorithm
| títulu = [http://math-www.uni-paderborn.de/mca/ Modern Computer Algebra]
| añu = 2003
| editorial = [[Cambridge University Press]]
| id = ISBN 0-521-82646-2
}}
* {{cita llibru |
autor = Shoup, Victor
| capítulu = Euclid's algorithm
| títulu = [http://www.shoup.net/ntb/ A Computational Introduction to Number Theory and Algebra]
| añu = 2008
| editorial = Cambridge University Press
| id = ISBN 978-0-521-85154-1
}}
* {{cita llibru |
autor = Johnsonbaugh, Richard
| capítulu = Introducción a la teoría de número |
títulu = Matemátiques Discretes
| añu = 2005
| editorial = Méxicu: PEARSON EDUCACIÓN
| id = ISBN 970-26-0637-3
}}
* {{cita llibru |
autor = Ralph P.
Grimaldi | capítulu = Propiedad de los númberos enteros: Inducción matemática |
títulu = Matemátiques Discreta y Combinatoria
| añu = 1998
| editorial = Méxicu: Addison Wesley Longman de Méxicu |
id = ISBN 968-444-324-2
}}
* {{cita llibru |
autor = Lipschutz, Seymour; Lipson, Marc
| capítulu = Propiedad de los enteros
| títulu = Matemátiques Discretes
| añu = 2009
| editorial = McGraw-Hill
| id = ISBN 978-970-10-7236-3
}}
* {{cita llibru |
autor = Brassard, Gilles; Bratley, Paul
| capítulu = Analís d'algoritmo |
títulu = Fundamentos de Algoritmia
| añu = 1997
| editorial = Madrid: PRENTICE HALL
| id = ISBN 84-89660-00-X
}}
* {{cita publicación
 |autor = Vallée, Brigitte
 |títulu = Dynamical Analysis of <math>\alpha</math>-Euclidean Algorithms
 |añu = 2002
 |publicación = Journal of Algorithms
 |volume = 44
 |númberu = 1
 |id = ISSN 0196-6774 , páxs. 246-285 <!-- Nun toi seguro del ISSN, favor de verificar-->
 |url = http://users.info.unicaen.fr/~brigitte/Publications/bourdon-daireaux-vallee.ps
 |urlarchivu = https://web.archive.org/web/20061002115832/http://users.info.unicaen.fr/~brigitte/Publications/bourdon-daireaux-vallee.ps
 |fechaarchivu = 2 d'ochobre de 2006
 |archiveurl = https://web.archive.org/web/20120206234711/http://users.info.unicaen.fr/~brigitte/Publications/bourdon-daireaux-vallee.ps
 |archivedate = 2012-02-06
 |fechaaccesu = 2018-06-10
 }}
* {{cita llibru |
autor = Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford
| capítulu = Number-Theoretic Algorithms
| títulu = Introduction to Algorithms
| añu = 2009
| editorial = The [[MIT Press]]
| id = ISBN 978-0-262-53305-8
}}
* {{cita llibru |nome=|enllaceautor=|
títulu = Introducción a la Teoría de Grupos
|url=http://www.pesmm.org.mx/Serie%20Testos_archivos/T4.pdf|fechaaccesu=2 de Julio 2017| añu = 2005
| editorial = Publicaciones Electróniques de la Sociedá Matemática Mexicana |isbn=|editor=|ubicación=|páxina=16-17|idioma=castellanu|
capítulo = Definiciones y resultaos xenerales
| id = ISBN 968-9161-02-4
| autor = Barrera Mora, Fernando }}

* {{cita llibru |
autor = Cárdenas, Humberto; Lluis, Emilio; Raggi, Francisco; Tomás, Francisco |
capítulu = Divisibilidad
| títulu = Álgebra Cimeru |
añu = 2004
| editorial = Méxicu: Tríes
| id = ISBN 968-24-3783-0
}}
* {{cita llibru |
autor = Pérez Siguí, María Luisa
| capítulu = Divisibilidad
| títulu = Teoría de Número |añu=2006
| editorial = Institutu de Matemátiques, UNAM
| id = ISBN 970-32-1170-0
}}
* {{cita llibru |
autor = Sánchez Velázquez, Jesús
| capítulu = Algoritmo pa númberos grandes
| títulu = Introducción al analís d'algoritmo |añu=1998
| editorial = Méxicu: Tríes
| id = ISBN 968-24-4341-5
}}
* {{cita llibru |
autor = Baldor, Aurelio |
capítulu = Máximu común divisor
| títulu = Álgebra |añu=2008
| editorial = Méxicu: Grupu Editorial Patria |
id = ISBN 978-970-817-000-0
}}

== Enllaces esternos ==
{{wikillibros
| nome = Implementación d'algoritmos de teoría de número/Algoritmo de Euclides
| etiqueta = Implementaciones del algoritmu d'Euclides
| oxeto = un llibru o manual sobre |
preposición = 
| idioma = 
}}
* [http://www.dma.fi.upm.es/java/matematicadiscreta/aritmeticamodular/divisibilidad.html Divisibilidad. L'algoritmu d'Euclides.]
* [https://web.archive.org/web/20040529013332/http://huitoto.udea.edu.co/SistemasDiscretos/contenido/alg_euclides.html Algoritmu d'Euclides.]
* {{MathWorld|EuclideanAlgorithm|Euclidean Algorithm}}

*Esplicación dinámica del máximu común divisor nesti videu de [[YouTube]]''[https://www.youtube.com/watch?v=WHUQSkaVXd4]''.

*En '''gaussianos'''''{{Enllaz rotu|1= |2=http://gaussianos.com/l%27algoritmu-de-euclides/ |date=August 2024 |bot=InternetArchiveBot }}'' pueden vese esplicaciones y exemplos un pocu más avanzaos d'esti algoritmu.
{{Tradubot|Algoritmo de Euclides}}

{{control d'autoridaes}}
[[Categoría:Teoría de númberos elemental]]