Algoritmo de Euclides - Historial de revisiones

Midel: /* Referencias */

2012-01-19T19:12:32Z

‎Referencias

Niurka jc.cmg en 19:34 29 mar 2011

2011-03-29T19:34:54Z

Alina idict en 14:10 28 may 2010

2010-05-28T14:10:59Z

Alina idict en 13:42 28 may 2010

2010-05-28T13:42:31Z

Alina idict en 13:39 28 may 2010

2010-05-28T13:39:04Z

Mostrar los cambios

Alina idict en 13:31 28 may 2010

2010-05-28T13:31:25Z

Carmen ciget.gra en 14:19 27 may 2010

2010-05-27T14:19:03Z

Asanto uci en 21:36 14 may 2010

2010-05-14T21:36:32Z

Asanto uci en 21:31 14 may 2010

2010-05-14T21:31:07Z

Asanto uci en 21:21 14 may 2010

2010-05-14T21:21:12Z

@@ Línea 412: / Línea 412: @@
 *''a'' div ''b'' significa "el cociente de dividir ''a'' entre ''b''". A esta operación se le conoce también como la ''división truncada'' porque trunca la parte fraccionaria del número. En muchos lenguajes de programación esto se implementa simplemente como <code>a/b</code>. Otras maneras son <code>a\b</code> (Visual Basic) , <code>a div b</code> (Pascal) o bien <code>a//b</code> (Python 3).
 *''a'' mod ''b'' significa "el residuo de dividir ''a ''entre ''b''". A esta operación se le conoce simplemente como ''módulo''. En muchos lenguajes de programación se implementa como <code>a&nbsp;% b</code>, mientras que en otros es <code>a mod b</code> (Visual Basic o Pascal) o bien <code>a rem b</code> (Ada).
 == Referencias  ==

← Revisión anterior		Revisión del 19:34 29 mar 2011
Línea 1:		Línea 1:
−	{{Definición\|Nombre=Algoritmo de Euclides\|imagen=401px-Algoritmo_de_Euclides_geométrico.svg.png\|concepto=Método antiguo y eficaz para calcular el máximo común divisor (MCD)}}'''Algoritmo de Euclides''':Es un método antiguo y eficaz para calcular el máximo común divisor (MCD). Fue originalmente descrito por Euclides en su obra Elementos. El algoritmo de Euclides extendido es una ligera modificación que permite además expresar al máximo común divisor como una combinación lineal. Este algoritmo tiene aplicaciones en diversas áreas como álgebra, teoría de números y ciencias de la computación entre otras. Con unas ligeras modificaciones suele ser utilizado en computadoras electrónicas debido a su gran eficiencia.	+	{{Definición\|Nombre=Algoritmo de Euclides\|imagen=401px-Algoritmo_de_Euclides_geométrico.svg.png\|concepto=Método antiguo y eficaz para calcular el máximo común divisor (MCD)}}'''Algoritmo de Euclides''':Es un método antiguo y eficaz para calcular el máximo común divisor (MCD). Fue originalmente descrito por [[Euclides]] en su obra Elementos. El algoritmo de Euclides extendido es una ligera modificación que permite además expresar al máximo común divisor como una combinación lineal. Este algoritmo tiene aplicaciones en diversas áreas como álgebra, teoría de números y ciencias de la computación entre otras. Con unas ligeras modificaciones suele ser utilizado en computadoras electrónicas debido a su gran eficiencia.

	== Algoritmo original de Euclides ==		== Algoritmo original de Euclides ==

@@ Línea 417: / Línea 417: @@
 *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 Numbrer Theory and Algebra. Cambridge
-<br>
+*University Press. ISBN 978-0-521-85154-1.
 *Johnsonbaugh, Richard (2005). «Introdució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.
@@ Línea 438: / Línea 431: @@
 *&nbsp;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
+*Baldor, Aurelio (2008). «Máximo común divisor», Álgebra. México
-:Grupo Editorial Patria. ISBN 978-970-817-000-0.
+*Grupo Editorial Patria. ISBN 978-970-817-000-0.
 [[Category:Algoritmos]]

← Revisión anterior		Revisión del 13:42 28 may 2010
Línea 1:		Línea 1:
−	{{Definición\|Nombre=Algoritmo de Euclides\|imagen=\|concepto=Método antiguo y eficaz para calcular el máximo común divisor (MCD)}}'''Algoritmo de Euclides''':Es un método antiguo y eficaz para calcular el máximo común divisor (MCD). Fue originalmente descrito por Euclides en su obra Elementos. El algoritmo de Euclides extendido es una ligera modificación que permite además expresar al máximo común divisor como una combinación lineal. Este algoritmo tiene aplicaciones en diversas áreas como álgebra, teoría de números y ciencias de la computación entre otras. Con unas ligeras modificaciones suele ser utilizado en computadoras electrónicas debido a su gran eficiencia.	+	{{Definición\|Nombre=Algoritmo de Euclides\|imagen=401px-Algoritmo_de_Euclides_geométrico.svg.png\|concepto=Método antiguo y eficaz para calcular el máximo común divisor (MCD)}}'''Algoritmo de Euclides''':Es un método antiguo y eficaz para calcular el máximo común divisor (MCD). Fue originalmente descrito por Euclides en su obra Elementos. El algoritmo de Euclides extendido es una ligera modificación que permite además expresar al máximo común divisor como una combinación lineal. Este algoritmo tiene aplicaciones en diversas áreas como álgebra, teoría de números y ciencias de la computación entre otras. Con unas ligeras modificaciones suele ser utilizado en computadoras electrónicas debido a su gran eficiencia.

	== Algoritmo original de Euclides ==		== Algoritmo original de Euclides ==

@@ Línea 1: / Línea 1: @@
-{{Mejorar|faltan las fuentes}} '''Algoritmo de Euclides:''' Es un método antiguo y eficaz para calcular el máximo común divisor (MCD). Fue originalmente descrito por Euclides en su obra Elementos. El algoritmo de Euclides extendido es una ligera modificación que permite además expresar al máximo común divisor como una combinación lineal. Este algoritmo tiene aplicaciones en diversas áreas como álgebra, teoría de números y ciencias de la computación entre otras. Con unas ligeras modificaciones suele ser utilizado en computadoras electrónicas debido a su gran eficiencia.
+'''Algoritmo de Euclides:''' Es un método antiguo y eficaz para calcular el máximo común divisor (MCD). Fue originalmente descrito por Euclides en su obra Elementos. El algoritmo de Euclides extendido es una ligera modificación que permite además expresar al máximo común divisor como una combinación lineal. Este algoritmo tiene aplicaciones en diversas áreas como álgebra, teoría de números y ciencias de la computación entre otras. Con unas ligeras modificaciones suele ser utilizado en computadoras electrónicas debido a su gran eficiencia.
 == Algoritmo original de Euclides  ==
@@ Línea 7: / Línea 7: @@
 No cualquier par de segmentos es conmensurable, como encontraron los pitagóricos cuando establecen que&nbsp; no es un número racional, pero en el caso de dos segmentos conmensurables se desea hallar la mayor medida común posible.
-Euclides describe en la proposición VII.2 de sus [[Elementos de Euclides|Elementos]] un método que permite hallar la mayor medida común posible de dos números (segmentos) que no sean primos entre sí, aunque de acuerdo a la época tal método se explica en términos geométricos, lo que se ilustra en la siguiente transcripción.<br>
+Euclides describe en la proposición VII.2 de sus [[Elementos de Euclides|Elementos]] un método que permite hallar la mayor medida común posible de dos números (segmentos) que no sean primos entre sí, aunque de acuerdo a la época tal método se explica en términos geométricos, lo que se ilustra en la siguiente transcripción.
-<pre>    '''''Para encontrar la máxima medida común de dos números que no sean primos entre sí.
-Euclides VII-2.svg'''''
+Para encontrar la máxima medida común de dos números que no sean primos entre sí.
-''Sean AB y CD los dos números que no son primos uno al otro. Se necesita entonces encontrar la máxima medida común de AB y CD.''
+Sean AB y CD los dos números que no son primos uno al otro. Se necesita entonces encontrar la máxima medida común de AB y CD.
-''Si CD mide AB entonces es una medida común puesto que CD se mide a sí mismo. Y es manifiesto que también es la mayor medida pues nada mayor a CD puede medir a CD. Pero si CD no mide a AB entonces algún número quedará de AB y CD, el menor siendo continuamente restado del mayor y que medirá al número que le precede. Porque una unidad no quedará pues si no es así, AB y CD serán primos uno del otro [Prop. VII.1], lo cual es lo contrario de lo que se supuso.''
+Si CD mide AB entonces es una medida común puesto que CD se mide a sí mismo. Y es manifiesto que también es la mayor medida pues nada mayor a CD puede medir a CD. Pero si CD no mide a AB entonces algún número quedará de AB y CD, el menor siendo continuamente restado del mayor y que medirá al número que le precede. Porque una unidad no quedará pues si no es así, AB y CD serán primos uno del otro [Prop. VII.1], lo cual es lo contrario de lo que se supuso.
-''Por tanto, algún número queda que medirá el número que le precede. Y sea CD midiendo BE dejando EA menor que sí mismo y sea EA midiendo DF dejando FC menor que sí mismo y sea FC medida de AE. Entonces, como FC mide AE y AE mide DF, FC será entonces medida de DF. Y también se mide a sí mismo. Por tanto también medirá todo CD. Y CD mide a BE. Entonces CF mide a BE y también mide a EA. Así mide a todo BA y también mide a CD. Esto es, CF mide tanto a AB y CD por lo que es una medida común de AB y CD.''
+Por tanto, algún número queda que medirá el número que le precede. Y sea CD midiendo BE dejando EA menor que sí mismo y sea EA midiendo DF dejando FC menor que sí mismo y sea FC medida de AE. Entonces, como FC mide AE y AE mide DF, FC será entonces medida de DF. Y también se mide a sí mismo.
-''Afirmo que también es la mayor medida común posible porque si no lo fuera, entonces un número mayor que CF mide a los números AB y CD, sea éste G. Dado que G mide a CD y CD mide a BE, G también mide a BE. Además, mide a todo BA por lo que mide también al residuo AE. Y AE mide a DF por lo que G también mide a DF. Mide también a todo DC por lo que mide también al residuo CF, es decir el mayor mide al menor, lo cual es imposible.
+Por tanto también medirá todo CD. Y CD mide a BE. Entonces CF mide a BE y también mide a EA. Así mide a todo BA y también mide a CD. Esto es, CF mide tanto a AB y CD por lo que es una medida común de AB y CD.
 Por tanto, ningún número mayor a CF puede medir a los números AB y CD. Entonces CF es la mayor medida común de AB y CD, lo cual se quería demostrar.
 Euclides. Elementos VII.2''</pre>
@@ Línea 250: / Línea 253: @@
 |}
-<br>
 Todas estas ecuaciones las podemos hacer parecidas a la ecuación&nbsp;:
@@ Línea 342: / Línea 345: @@
 |-
 | '''Función''' mcd(a,b):
-&nbsp;&nbsp;&nbsp;'''Si''' b = 0 '''entonces''':
+'''Si''' b = 0 '''entonces''':
-&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'''El resultado es''' a
+'''El resultado es''' a
-&nbsp;&nbsp; '''En otro caso''':
+'''En otro caso''':
-&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; '''El resultado es''' mcd(b,amod b)
+'''El resultado es''' mcd(b,amod b)
 |}
-&nbsp;
 {| cellspacing="1" cellpadding="1" border="1" style="width: 432px; height: 89px;"
@@ Línea 371: / Línea 374: @@
 |-
 | '''Función''' Euclides(a,b):
-&nbsp; '''Si''' b = 0 '''entonces''':
+'''Si''' b = 0 '''entonces''':
-&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; '''El resultado es '''(a,1,0)
+'''El resultado es '''(a,1,0)
-&nbsp; '''En otro caso''':<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; '''El resultado es'''<br>
+'''En otro caso''':
 |}
 {| cellspacing="1" cellpadding="1" border="1" style="width: 430px; height: 48px;"
@@ Línea 386: / Línea 389: @@
 |-
 | '''Función''' Euclides(a,b):
-&nbsp;&nbsp; '''Mientras haga lo siguiente''':
+'''Mientras haga lo siguiente''':
-&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Divida ''a ''entre ''b'' para obtener un cociente ''q'' y un residuo''r''
+Divida ''a ''entre ''b'' para obtener un cociente ''q'' y un residuo''r''
-&nbsp;&nbsp; '''El resultado es '''(a,s,t) <br>
+'''El resultado es '''(a,s,t)
 |}
-<br>
 {| cellspacing="1" cellpadding="1" border="1" style="width: 428px; height: 51px;"
@@ Línea 401: / Línea 404: @@
 |-
 | '''Función '''Euclides(a,b):
-&nbsp;&nbsp;&nbsp; '''Mientras haga lo siguiente''':
+'''Mientras haga lo siguiente''':
 Divida ''a'' entre ''b'' para obtener un cociente ''q'' y un residuo ''r''
-&nbsp;&nbsp;&nbsp; '''El resultado es''' (a,Q<sub>11</sub>,Q<sub>12</sub>) <br>
+'''El resultado es''' (a,Q<sub>11</sub>,Q<sub>12</sub>)
 |}
 Acerca de la notación empleada:
@@ Línea 437: / Línea 438: @@
 *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&nbsp;968-9161-02-4.
-*&nbsp; Cárdenas, Humberto; Lluis, Emilio; Raggi, Francisco; Tomás, Francisco (2004).&nbsp;«Divisibilidad», Álgebra Superior. México: Trillas. ISBN 968-24-3783-0.
+*Cárdenas, Humberto; Lluis, Emilio; Raggi, Francisco; Tomás, Francisco (2004).&nbsp;«Divisibilidad», Álgebra Superior. México: Trillas. ISBN 968-24-3783-0.
 *&nbsp;Pérez Segui, María Luisa (2006). «Divisibilidad», Teoría de Números. Instituto de Matemáticas, UNAM. ISBN 970-32-1170-0.
 *&nbsp;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.

@@ Línea 1: / Línea 1: @@
-{{Mejorar|faltan las fuentes}} '''Algoritmo de Euclides:'''
+{{Mejorar|faltan las fuentes}} '''Algoritmo de Euclides:''' Es un método antiguo y eficaz para calcular el máximo común divisor (MCD). Fue originalmente descrito por Euclides en su obra Elementos. El algoritmo de Euclides extendido es una ligera modificación que permite además expresar al máximo común divisor como una combinación lineal. Este algoritmo tiene aplicaciones en diversas áreas como álgebra, teoría de números y ciencias de la computación entre otras. Con unas ligeras modificaciones suele ser utilizado en computadoras electrónicas debido a su gran eficiencia.
 == Algoritmo original de Euclides  ==
@@ Línea 305: / Línea 303: @@
 ! scope="row" | 4<br>
 | 21 dividido entre 13 es 1 y sobran 8<br>
-| mcd(21,13) = mcd(13,8)<br>
+| mcd(21,13) = mcd(13,8)
 |-
 ! scope="row" | 5<br>
 | 13 dividido entre 8 es 1 y sobran 5<br>
-| mcd(13,8) = mcd(8,5)<br>
+| mcd(13,8) = mcd(8,5)
 |-
-! scope="row" | 6<br>
+! scope="row" | 6
 | 8 dividido entre 5 es 1 y sobran 3<br>
-| mcd(8,5) = mcd(5,3)<br>
+| mcd(8,5) = mcd(5,3)
 |-
-! scope="row" | 7<br>
+! scope="row" | 7
 | 5 dividido entre 3 es 1 y sobran 2<br>
 | mcd(5,3) = mcd(3,2)<br>
 |-
-! scope="row" | 8<br>
+! scope="row" | 8
-| 3 dividido entre 2 es 1 y sobran 1<br>
+| 3 dividido entre 2 es 1 y sobran 1
-| mcd(3,2) = mcd(2,1)<br>
+| mcd(3,2) = mcd(2,1)
 |-
-! scope="row" | 9<br>
+! scope="row" | 9
-| 2 dividido entre 1 es 2 y sobra 0<br>
+| 2 dividido entre 1 es 2 y sobra 0
-| mcd(2,1) = mcd(1,0)<br>
+| mcd(2,1) = mcd(1,0)
 |}
 En este ejemplo se observa que con estos dos números de dos dígitos decimales, se necesita hacer 9 divisiones. En general, el número de divisiones efectuadas por el algoritmo nunca supera 5 veces el número de dígitos que tienen estos números. En términos de [[Complejidad computacional]], esto significa que se requieren O(log n) divisiones para calcular el máximo común divisor de ''n'' y ''m'' donde ''n&gt;m''.
@@ Línea 351: / Línea 348: @@
 &nbsp;&nbsp; '''En otro caso''':
-&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; '''El resultado es''' mcd(b,amod b)<br>
+&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; '''El resultado es''' mcd(b,amod b)
 |}
-&nbsp;<br>
+&nbsp;
 {| cellspacing="1" cellpadding="1" border="1" style="width: 432px; height: 89px;"
@@ Línea 364: / Línea 361: @@
 '''&nbsp;&nbsp;&nbsp; Mientras haga lo siguiente''':
-'''&nbsp;&nbsp;&nbsp; El resultado es''' a <br>
+'''&nbsp;&nbsp;&nbsp; El resultado es''' a
 |}
 {| cellspacing="1" cellpadding="1" border="1" style="width: 434px; height: 133px;"
@@ Línea 424: / Línea 420: @@
 == Referencias  ==
-*Von Zur Gathen, Joachim; Gerhard, Jürgen (2003). «The Euclidean Algorithm», Modern Computer Algebra. Cambridge<br>
+*Von Zur Gathen, Joachim; Gerhard, Jürgen (2003). «The Euclidean Algorithm», Modern Computer Algebra. Cambridge
-<br>
+*University Press. ISBN 0-521-82646-2.
-&nbsp;&nbsp;&nbsp; University Press. ISBN 978-0-521-85154-1.<br>
+*Shoup, Victor (2008). «Euclid´s algorithm», A Computational Introduction to Numbrer Theory and Algebra. Cambridge
-<br>
+*University Press. ISBN 978-0-521-85154-1.
-<br>
+*Johnsonbaugh, Richard (2005). «Introdución a la teoría de números», Matemáticas Discretas. México: PEARSON EDUCACIÓN. ISBN 970-26-0637-3.
 [[Category:Algoritmos]]

@@ Línea 217: / Línea 217: @@
 === 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.
+Al momento de hacer cálculos con fracciones, es de gran importancia saber cómo simplificarlas. Por ejemplo, la fracción frac{65}{91} es equivalente con frac 5 7 (véase [[Número racional]]). De manera más general, frac ab=\frac {ca}{cb} siempre que c\ne0. Para reducir una fracción cualquiera frac a b, sólo se necesita dividir ''a ''y ''b'' 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>.
+Por ejemplo, si se desea reducir frac{166}{249}, primero se usa el algoritmo de Euclides para encontrar mcd(166,249)=83. Se hacen las divisiones 166\div 83 = 2 y 249\div 83 = 3. Luego entonces se concluye que frac{166}{249}=\frac 2 3.
 === 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 como [[Fracción continua]]. <br>
 Esto se debe a que si ''a = bq + r ''y r neq 0, entonces&nbsp;
@@ Línea 231: / Línea 231: @@
 {| cellspacing="1" cellpadding="1" border="1" style="width: 397px; height: 123px;"
 |-
 ! scope="col" | Paso<br>
 ! scope="col" | Operación <br>
 ! scope="col" | Significado<br>
 |-
 ! scope="row" | 1<br>
 | 93164 dividido entre 5826 es 15 y sobran 5774<br>
 | <br>
 |-
 ! scope="row" | 2<br>
 | 5826 dividido entre 5774 es 1 y sobran 52<br>
 | <br>
 |-
 ! scope="row" | 3<br>
 | 5774 dividido entre 52 es 111 y sobran 2<br>
 | <br>
 |-
 ! scope="row" | 4<br>
 | 52 dividido entre 2 es 26 y sobra 0<br>
 | <br>
 |}
 <br>
-Todas estas ecuaciones las podemos hacer parecidas a la ecuación :
+Todas estas ecuaciones las podemos hacer parecidas a la ecuación&nbsp;:
 #frac{93164}{5826}=15+ \frac 1 {\frac{5826}{5774}}

@@ Línea 223: / Línea 223: @@
 === 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}}
+La sucesión de divisiones que se efectúan al seguir algoritmo de Euclides puede ser utilizada para expresar una fracción cualquiera como [[Fracción continua]]. <br>
-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:
+Esto se debe a que si ''a = bq + r ''y r neq 0, entonces&nbsp;
-{|
+Por ejemplo, para encontrar el máximo común divisor de93164 y 5826 el algoritmo genera la siguiente secuencia de divisiones:
 |-
-| –
+! scope="row" | 3<br>
-! Paso
+| 5774 dividido entre 52 es 111 y sobran 2<br>
-! Operación
+| <br>
-! Significado
+|-
-| –
+! scope="row" | 4<br>
-| 1
+| 52 dividido entre 2 es 26 y sobra 0<br>
-| 93164 dividido entre 5826 es 15 y sobran 5774
+| <br>
 |}
-Todas estas ecuaciones las podemos hacer parecidas a la ecuación {{eqnref | 3}}:
+<br>
-#<math>\textstyle\frac{93164}{5826}=15+ \frac 1 {\frac{5826}{5774}}</math>
+#frac{93164}{5826}=15+ \frac 1 {\frac{5826}{5774}}
-#<math>\textstyle\frac{5826}{5774}=1+ \frac 1 {\frac{5774}{52}}</math>
+#frac{5826}{5774}=1+ \frac 1 {\frac{5774}{52}}
-#<math>\textstyle\frac{5774}{52}=111+ \frac 1 {\frac{52}{2}}</math>
+#frac{5774}{52}=111+ \frac 1 {\frac{52}{2}}
-#<math>\textstyle\frac{52}{2}=26</math>
+#frac{52}{2}=26
-Si se substituye 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 substituye la segunda ecuación en la primera, se obtiene
-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>}}
+Si se repite este proceso de substitución entonces se obtiene la expresión deseada:&nbsp;
-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>}} &lt;!–– 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]]. ––&gt;
+De manera más general, la fracción continua encontrada con este algoritmo siempre es de la forma &lt;!–– Esto va en la sección siguiente: Volviendo al caso ''a ''y ''b'' enteros, el algoritmo de Euclides permite encontrar los coeficientes enteros ''u'' y ''v'' de la [[Identidad de Bézout]] au+bv={mcd}(a, b) de fundamental importancia en la [[Aritmética]]. ––&gt;
 === Inversos modulares  ===
 Decimos que dos números enteros son ''congruentes módulo m'' (aunque también se puede generalizar para cualquier otro dominio euclídeo) si al dividirlos entre ''m ''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''a'' es congruente con ''b'' módulo ''m'' se escribe, en el ejemplo anterior se tiene 7 equiv 12 p mod 5. Supóngase que se conocen los valores de ''a'', ''b'' y ''m'', pero que se desconoce el valor ''x'' de la siguiente ecuación:<br>
 Basta con encontrar un valor ''a''<sup>-1</sup> que tenga la característica de que, pues de esta manera al multiplicar la ecuación por ''a''<sup>-1</sup> se tendría la solución deseada: <br>
 Al valor ''a''<sup>-1</sup> se le llama ''inverso modular'' de ''a'' módulo ''m''. Desafortunadamente este valor no siempre existe. Por ejemplo, con ''a''=4 y''m''=6 no existe ningún número entero entero ''a''<sup>-1</sup> tal que. De hecho este valor existe si y sólo si mcd(''a,m'')=1. Más aún, si al usar el algoritmo de Euclides extendido (ahora con''b=m'') se obtiene 1 =''as + mt'', entonces el valor ''s'' es el inverso modular de ''a'' módulo ''m''. Por ejemplo, se desea resolver la ecuación <br>
 Entonces con el algoritmo de Euclides extendido se calcula que mcd(5,9) = 1 = 5(2) + 9( − 1). Como mcd(5,9) = 1 entonces 5 tiene un inverso modular. Más aún, como 1 = 5(2) + 9( − 1), entonces ese inverso es 2. Entonces <br>
 Es decir que el valor de ''x'' es 4.