Usuario:Kn/Zona de pruebas personal

El 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 la proposición 2 del libro VII de su obra Elementos. El algoritmo extendido de Euclides 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 este algoritmo suele ser utilizado en computadoras electrónicas debido a su gran eficiencia.

Algoritmo original de Euclides

Eulides abordó el problema de encontrar el máximo común divisor desde un punto de vista geométrico. En la proposición 2 del libro VII de Elementos puede leerse "Dados dos números que no son números primos entre sí, encontrar su máxima común medida". Bajo este contexto, dados dos segmentos de recta con medidas diferentes, Euclides quería encontrar otro segmento de recta que sirviera para medir ambos segmentos de manera exacta. El algoritmo es básicamente el mismo que se usa hoy en día con la única diferencia de que en lugar de utilizar la división, se utilizan restas repetidas.

Algoritmo de Euclides tradicional

Al dividir $a$ entre $b$ (números enteros), se obtiene un cociente $q$ y un residuo $r$. Es posible demostrar que el máximo común divisor de $a$ y $b$ es el mismo que el de $b$ y $r$. Este es el fundamento principal del algoritmo. También es importante tener en cuenta que el máximo común divisor de cualquier número $a$ y $0$ es precisamente $a$. Para fines prácticos, la notación $\mathrm {mcd} (a,b)$ significa máximo común divisor de $a$ y $b$.

Según lo antes mencionado, para calcular el máximo común divisor de 2366 y 273 se puede proseguir de la siguiente manera:

Paso	Operación	Significado
1	2366 dividido entre 273 es 8 y sobran 182	$\mathrm {mcd} (2366,273)=\mathrm {mcd} (273,182)$
2	273 dividido entre 182 es 1 y sobran 91	$\mathrm {mcd} (273,182)=\mathrm {mcd} (182,91)$
3	182 dividido entre 91 es 2 y sobra 0	$\mathrm {mcd} (182,91)=\mathrm {mcd} (91,0)$

La secuencia de igualdades $\mathrm {mcd} (2366,273)=\mathrm {mcd} (273,182)=\mathrm {mcd} (182,91)=\mathrm {mcd} (91,0)$ implican que $\mathrm {mcd} (2366,273)=\mathrm {mcd} (91,0)$. Dado que $\mathrm {mcd} (91,0)=91$, entonces se concluye que $\mathrm {mcd} (2366,273)=91$. Este mismo procedimiento se puede aplicar a cualesquiera dos números naturales. En general, si se desea encontrar el máximo común divisor de dos números naturales $a$ y $b$, se siguen las siguientes reglas:

1. Si $b=0$ entonces $\mathrm {mcd} (a,b)=a$ y el algoritmo termina
2. En otro caso, $\mathrm {mcd} (a,b)=\mathrm {mcd} (b,r)$ donde $r$ es el resto de dividir $a$ entre $b$. Para calcular $\mathrm {mcd} (b,r)$ se utilizan estas mismas reglas

Asuma que llamamos $a=r_{0}$ y $b=r_{1}$. Aplicando estas tres reglas se obtiene la siguiente secuencia de operaciones:

Paso	Operación	Significado
1	$r_{0}$ dividido entre $r_{1}$ es $q_{1}$ y sobran $r_{2}$	$\mathrm {mcd} (r_{0},r_{1})=\mathrm {mcd} (r_{1},r_{2})$
2	$r_{1}$ dividido entre $r_{2}$ es $q_{2}$ y sobran $r_{3}$	$\mathrm {mcd} (r_{1},r_{2})=\mathrm {mcd} (r_{2},r_{3})$
3	$r_{2}$ dividido entre $r_{3}$ es $q_{3}$ y sobran $r_{4}$	$\mathrm {mcd} (r_{2},r_{3})=\mathrm {mcd} (r_{3},r_{4})$
$\vdots$	$\vdots$	$\vdots$
$n$	$r_{n-1}$ dividido entre $r_{n}$ es $q_{n}$ y sobran $r_{n+1}$	$\mathrm {mcd} (r_{n-1},r_{n})=\mathrm {mcd} (r_{n},r_{n+1})$
$n+1$	$r_{n}$ dividido entre $r_{n+1}$ es $q_{n+1}$ y sobra $0$	$\mathrm {mcd} (r_{n},r_{n+1})=\mathrm {mcd} (r_{n+1},0)$

Como la sucesión de residuos va disminuyendo, eventualmente un residuo tiene que ser cero y es en ese momento cuando el algoritmo termina. El máximo común divisor es precisamente $r_{n+1}$ (el último residuo que no es cero).

Generalización

En realidad el algoritmo de Euclides funciona no sólo para los números naturales, sino para cualesquiera elementos donde exista una "división con residuo". A este tipo de divisiones se les llama divisiones euclidianas y a los conjuntos donde se puede definir dicha división se les llama dominios euclídeos. Por ejemplo, el conjunto de los números enteros y el de los polinomios son dominios euclídeos porque podemos definir una división con residuo (véase División polinomial). De esta manera, se puede calcular el máximo común divisor de dos números enteros o de dos polinomios.

Por ejemplo, para calcular el máximo común divisor de los polinomios $P(x)=x^{5}+2x^{3}+x$ y $Q(x)=x^{4}-1$ el algoritmo de Euclides sugiere la siguiente secuencia de operaciones:

Paso	Operación	Significado
1	$x^{5}+2x^{3}+x$ dividido entre $x^{4}-1$ es $x$ y sobra $2x^{3}+2x$	$\mathrm {mcd} (x^{5}+2x^{3}+x,x^{4}-1)=\mathrm {mcd} (x^{4}-1,2x^{3}+2x)$
2	$x^{4}-1$ dividido entre $2x^{3}+2x$ es $\textstyle {{\frac {1}{2}}x}$ y sobra $-x^{2}-1$	$\mathrm {mcd} (x^{4}-1,2x^{3}+2x)=\mathrm {mcd} (2x^{3}+2x,-x^{2}-1)$
3	$2x^{3}+2x$ dividido entre $-x^{2}-1$ es $-2x$ y sobra 0	$\mathrm {mcd} (2x^{3}+2x,-x^{2}-1)=\mathrm {mcd} (-x^{2}-1,0)$

De esta manera se concluye que $\mathrm {mcd} (x^{5}+2x^{3}+x,x^{4}-1)=-x^{2}-1$.

Descripción formal

Se puede expresar este algoritmo de manera más formal usando pseudocódigo. En este caso la expresión "$x\operatorname {\,m{\acute {o}}d\,} y$" significa "el residuo de dividir $x$ entre $y$" (véase Aritmética modular).

Algoritmo 1 de Euclides

Entrada: Valores $a$ y $b$ pertenecientes a un dominio euclídeo Salida: Un máximo común divisor de $a$ y $b$ $r_{0}\gets a,\quad r_{1}\gets b$ $i\gets 1$ Mientras $r_{i}\neq 0$ haga lo siguiente: $r_{i+1}\gets r_{i-1}\operatorname {\,m{\acute {o}}d\,} r_{i}$ $i\gets i+1$ El resultado es: $r_{i-1}\,$

Vale la pena notar que este algoritmo no es eficiente ser implementado directamente en una computadora, ya que requeriría memorizar todos los valores de $r_{i}$.

Algoritmo de Euclides extendido

El algoritmo de Euclides extendido permite, además de encontrar un máximo común divisor de dos números enteros $a$ y $b$, expresarlo como una combinación lineal, es decir, encontrar números enteros $m$ y $n$ tales que $\mathrm {mcd} (a,b)=ma+nb$. Igualmente, esto se generaliza hacia cualquier dominio euclideano.

Fundamentos

Para enternder el algoritmo de Euclides extendido es preciso comprender que la frase "$a$ dividido entre $b$ es $q$ y sobra $r$" se puede representar matemáticamente como la ecuación $a=bq+r$ (véase Algoritmo de la división).

Es un hecho que dados los números enteros $a$, $b$, $c$ y $d$, si $c$ es una combinación lineal de $a$ y $b$ ($c=as+bt$), y si $d$ es una combinación lineal de $b$ y $c$ ($d=bs'+ct'$), entonces también $d$ es una combinación lineal de $a$ y $b$ (porque entonces $d=a(st')+b(s'+tt')$).

Suponiendo que se desea calcular el máximo común divisor de $a$ y $b$, se pueden encontrar valores $s_{i}$ y $t_{i}$ tales que $as_{i}+bt_{i}=r_{i}$ en cada paso del algoritmo tradicional. Las reglas para calcular estos valores son las siguientes:

1. Claramente $a(1)+b(0)=r_{0}$ y $a(0)+b(1)=r_{1}$, esto significa que $s_{0}=1$, $t_{0}=0$, $s_{1}=0$ y $t_{1}=1$
2. Si $as_{i}+bt_{i}=r_{i}$, entonces $a(s_{i-1}-q_{i}s_{i})+b(t_{i-1}-q_{i}t_{i})=r_{i+1}$; por lo tanto $s_{i+1}=s_{i-1}-q_{i}s_{i}$ y $t_{i+1}=t_{i-1}-q_{i}t_{i}$

Descripción formal

Para tener una visión completa del algoritmo, es mejor describirlo de manera formal utilizando pseudocódigo.

Algoritmo 2 de Euclides extendido

Entrada: Valores $a$ y $b$ pertenecientes a un dominio euclídeo Salida: Un máximo común divisor de $a$ y $b$, y valores $s$ y $t$ tales que $\mathrm {mcd} (a,b)=as+bt$ $\left(r_{0},r_{1},s_{0},t_{0},s_{1},t_{1}\right)\gets \left(a,b,1,0,0,1\right)$ $i\gets 1$ Mientras $r_{i}\neq 0$ haga lo siguiente: Divida $r_{i-1}\,$ entre $r_{i}\,$ para obtener el cociente $q_{i}\,$ y el residuo $r_{i+1}\,$ $s_{i+1}\gets s_{i-1}-q_{i}s_{i}$ $t_{i+1}\gets t_{i-1}-q_{i}t_{i}$ $i\gets i+1$ El resultado es: $r_{i-1}\,$ es un máximo común divisor de $a\,$ y $b\,$ y además $r_{i-1}=as_{i-1}+bt_{i-1}\,$

Uso de matrices

Para facilitar la comprensión y memorización del algoritmo de Euclides Extendido, es conveniente observar la siguiente caracterización.

Supóngase que se utiliza el algoritmo de Euclides tradicional para calcular los valores $q_{i}$ y $r_{i}$ que ahí se describen. Entonces por cada valor $q_{i}$ calculado, se define la matriz:

$Q_{i}={\begin{pmatrix}0&1\\1&-q_{i}\end{pmatrix}}$

Resulta ser que el algoritmo de Euclides extendido equivale a multiplicar estas matrices:

${\begin{pmatrix}s_{i}&t_{i}\\s_{i+1}&t_{i+1}\end{pmatrix}}=Q_{i}\times Q_{i-1}\times \cdots \times Q_{1}$

Aplicaciones

Escalas musicales

Que tengo que escribir aqui? Hola hola