|
# '''El resultado es:''' <math>r_{i-1} </math> es un máximo común divisor de <math>a </math> y <math>b </math> y se expresa <math>r_{i-1}=as_{i-1}+bt_{i-1} </math>
|2}}
== Aplicaciones ==
=== Simplificar fracciones ===
Al momento de hacer cálculos con fracciones, es de gran importancia saber cómo simplificarlas. Por ejemplo, la fracción <math>\textstyle\frac{65}{91}</math> es equivalente con <math>\textstyle\frac 5 7</math> (véase [[Número racional]]). De manera más general, <math>\textstyle\frac ab=\frac {ca}{cb}</math> siempre que <math>c\ne0</math>. Para reducir una fracción cualquiera <math>\textstyle\frac a b</math>, sólo se necesita dividir <math>a</math> y <math>b</math> entre su máximo común divisor.
Por ejemplo, si se desea reducir <math>\textstyle\frac{166}{249}</math>, primero se usa el algoritmo de Euclides para encontrar <math>\mathrm{mcd}(166,249)=83</math>. Se hacen las divisiones <math>\textstyle 166\div 83 = 2</math> y <math>\textstyle 249\div 83 = 3</math>. Luego entonces se concluye que <math>\textstyle\frac{166}{249}=\frac 2 3</math>.
=== Fracciones continuas ===
La sucesión de divisiones que se efectúan al seguir algoritmo de Euclides puede ser utilizada para expresar una fracción cualquiera <math>\textstyle\frac a b</math> como [[fracción continua]]. Esto se debe a que si <math>a = bq + r</math> y <math>r\neq 0</math>, entonces
{{ecuación|<math>\frac a b = q + \frac 1 {\frac b r}</math>|3}}
Por ejemplo, para encontrar el máximo común divisor de <math>93164</math> y <math>5826</math> el algoritmo genera la siguiente secuencia de divisiones:
{| class="wikitable"
!Paso!!Operación!!Significado
|-
|1||93164 dividido entre 5826 es 15 y sobran 5774||<math>93164=5826\times 15+5774</math>
|-
|2||5826 dividido entre 5774 es 1 y sobran 52||<math>5826=5774\times 1+52</math>
|-
|3||5774 dividido entre 52 es 111 y sobran 2||<math>5774=52\times 111+2</math>
|-
|4||52 dividido entre 2 es 26 y sobra 0||<math>52=2\times 26+0</math>
|}
Todas estas ecuaciones las podemos hacer parecidas 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 se sustituye la segunda ecuación en la primera, se obtiene
{{Ecuación|<math>\frac{93164}{5826}=15+ \frac 1 {1+ \frac 1 {\frac{5774}{52}}}</math>}}
Si se repite este proceso de substitución entonces se obtiene la expresión deseada:
{{Ecuación|<math>\frac{93164}{5826}=15+ \frac 1 {1+ \frac 1 {111+ \frac 1 {26}}}</math>}}
De manera más general, la fracción continua encontrada con este algoritmo siempre es de la forma
{{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 en la sección siguiente: Volviendo al caso <math>a</math> y <math>b</math> enteros, el algoritmo de Euclides permite encontrar los coeficientes enteros <math>u</math> y <math>v</math> de la [[identidad de Bézout]] <math>au+bv=\mathrm{mcd}(a, b)</math> de fundamental importancia en la [[aritmética]]. -->
=== Inversos modulares ===
{{AP|inverso multiplicativo (aritmética modular)}}
Decimos que dos números enteros son ''congruentes módulo <math>m</math>'' (aunque también se puede generalizar para cualquier otro dominio euclídeo) si al dividirlos entre <math>m</math> obtenemos el mismo residuo (véase [[Congruencia]]). Por ejemplo, 7 es congruente con 12 módulo 5 porque al dividir 7 entre 5 y 12 entre 5, en ambos casos obtenemos el mismo residuo (que es 2). Cuando <math>a</math> es congruente con <math>b</math> módulo <math>m</math> se escribe <math>a\equiv b\pmod m</math>, en el ejemplo anterior se tiene <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 desconoce el valor <math>x</math> de la siguiente ecuación:
{{Ecuacion |<math>a x\equiv b\pmod m</math>|2}}
Basta con encontrar un valor <math>a^{-1}</math> que tenga la característica de que <math>a^{-1} a\equiv 1\pmod m</math>, pues de esta manera al multiplicar la ecuación {{eqnref|2}} por <math>a^{-1}</math> se tendría la solución deseada:
{{Ecuacion | <math>x\equiv a^{-1} b\pmod m</math>}}
Al valor <math>a^{-1}</math> se le llama ''inverso modular'' de <math>a</math> módulo <math>m</math>. Desafortunadamente este valor no siempre existe. Por ejemplo, con <math>a=4</math> y <math>m=6</math> no existe ningún número entero <math>a^{-1}</math> tal que <math>a^{-1} 4\equiv 1\pmod 6</math>. De hecho este valor existe si y sólo si <math>\mathrm{mcd}(a,m)=1</math> (la condición de existencia de soluciones depende de que <math>\mathrm{mcd}(a,m)|b </math>, mientras que la unicidad depende de que el <math>\mathrm{mcd}(a,m)=1</math>). Más aún, si al usar el algoritmo de Euclides extendido (ahora con <math>b=m</math>) se obtiene <math>1=as+mt</math>, entonces el valor <math>s</math> es el inverso modular de <math>a</math> módulo <math>m</math>. <!--LA DEMOSTRACIÓN NO ES BUENO COLOCARLA EN LA ENCICLOPEDIA-->
Por ejemplo, se desea resolver la ecuación
{{Ecuacion |<math>5 x\equiv 2\pmod 9</math>}}
Entonces con el algoritmo de Euclides extendido se calcula que <math>\mathrm{mcd}(5,9)=1=5(2)+9(-1)</math>. Como <math>\mathrm{mcd}(5,9)=1</math> entonces 5 tiene un inverso modular. Más aún, como <math>1=5(2)+9(-1)</math>, entonces ese inverso es 2. Entonces
{{Ecuacion |<math>x\equiv 2(2)\pmod 9</math>}}
Es decir que el valor de <math>x</math> es <math>4</math>.
== Complejidad del algoritmo ==
| 