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

editar

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

editar

Al dividir   entre   (números enteros), se obtiene un cociente   y un residuo  . Es posible demostrar que el máximo común divisor de   y   es el mismo que el de   y  . 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   y   es precisamente  . Para fines prácticos, la notación   significa máximo común divisor de   y  .

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  
2 273 dividido entre 182 es 1 y sobran 91  
3 182 dividido entre 91 es 2 y sobra 0  

La secuencia de igualdades   implican que  . Dado que  , entonces se concluye que  . 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   y  , se siguen las siguientes reglas:

  1. Si   entonces   y el algoritmo termina
  2. En otro caso,   donde   es el resto de dividir   entre  . Para calcular   se utilizan estas mismas reglas

Asuma que llamamos   y  . Aplicando estas tres reglas se obtiene la siguiente secuencia de operaciones:

Paso Operación Significado
1   dividido entre   es   y sobran    
2   dividido entre   es   y sobran    
3   dividido entre   es   y sobran    
     
    dividido entre   es   y sobran    
    dividido entre   es   y sobra    

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   (el último residuo que no es cero).

Generalización

editar

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   y   el algoritmo de Euclides sugiere la siguiente secuencia de operaciones:

Paso Operación Significado
1   dividido entre   es   y sobra    
2   dividido entre   es   y sobra    
3   dividido entre   es   y sobra 0  

De esta manera se concluye que  .

Descripción formal

editar

Se puede expresar este algoritmo de manera más formal usando pseudocódigo. En este caso la expresión " " significa "el residuo de dividir   entre  " (véase Aritmética modular).

Algoritmo 1 de Euclides

Entrada: Valores   y   pertenecientes a un dominio euclídeo

Salida: Un máximo común divisor de   y  

  1.  
  2.  
  3. Mientras   haga lo siguiente:
    1.  
    2.  
  4. El resultado es:  

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  .

Algoritmo de Euclides extendido

editar

El algoritmo de Euclides extendido permite, además de encontrar un máximo común divisor de dos números enteros   y  , expresarlo como una combinación lineal, es decir, encontrar números enteros   y   tales que  . Igualmente, esto se generaliza hacia cualquier dominio euclideano.

Fundamentos

editar

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

Es un hecho que dados los números enteros  ,  ,   y  , si   es una combinación lineal de   y   ( ), y si   es una combinación lineal de   y   ( ), entonces también   es una combinación lineal de   y   (porque entonces  ).

Suponiendo que se desea calcular el máximo común divisor de   y  , se pueden encontrar valores   y   tales que   en cada paso del algoritmo tradicional. Las reglas para calcular estos valores son las siguientes:

  1. Claramente   y  , esto significa que  ,  ,   y  
  2. Si  , entonces  ; por lo tanto   y  

Descripción formal

editar

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

Algoritmo 2 de Euclides extendido

Entrada: Valores   y   pertenecientes a un dominio euclídeo

Salida: Un máximo común divisor de   y  , y valores   y   tales que  

  1.  
  2.  
  3. Mientras   haga lo siguiente:
    1. Divida   entre   para obtener el cociente   y el residuo  
    2.  
    3.  
    4.  
  4. El resultado es:   es un máximo común divisor de   y   y además  

Uso de matrices

editar

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   y   que ahí se describen. Entonces por cada valor   calculado, se define la matriz:

 

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

 

Algoritmo de Euclides normalizado

editar

Implementación en pseudocódigo

editar

Análisis de costo

editar

Aplicaciones

editar

Aritmética modular

editar

Inversos modulares

editar

Ecuaciónes diofánticas lineales

editar

Fracciones continuas

editar

Calendarios

editar

Escalas musicales

editar

Que tengo que escribir aqui? Hola hola

Referencias

editar

Enlaces externos

editar