Algoritmo de Euclides

De Wikipedia, la enciclopedia libre

Tienes mensajes nuevos (Dif. entre las dos últimas versiones).

El algoritmo de Euclides es un método eficaz para calcular el máximo común divisor (mcd) entre dos números enteros.
El algoritmo consiste en varias divisiones euclidianas sucesivas. En la primera división, se toma como dividendo el mayor de los números y como divisor el otro (se ahorra así un paso). Luego, el divisor y el resto sirven respectivamente de dividendo y divisor de la siguiente división. El proceso termina cuando se obtiene un resto nulo. El mcd es entonces el penúltimo resto del algoritmo.

[editar] Definición

Formalmente, si llamamos a, b a los enteros iniciales, r₁, r₂ ... r_n-1 y r_n = 0 a los restos sucesivos obtenidos mediante el algoritmo de la división, entonces:

mcd (a, b) = mcd (b, r₁), con r₁ = a - ( b·q) (q es el cociente de a por b)

En efecto, los divisores comunes de a y b son los de a - b·q y b: $\left. \begin{matrix} \mbox{q / a} \\ \mbox{q / b} \end{matrix} \right \} \Leftrightarrow \left \{ \begin{matrix} \mbox{q / a} \\ \mbox{q / (a - bq)}\end{matrix} \right.$

porque si q divide a y b, obviamente divide a - (b·q) que es una combinación lineal de ambos, y recíprocamente a = (a - b·q) + b·q es una combinación lineal de b y a - b·q. Luego el menor de los divisores comunes es el mismo, y repitiendo la operación:

mcd (b, r₁) = mcd (r₁, r₂) = mcd (r₂, r₃) = ... = mcd (r_n-1, r_n) = mcd (r_n-1, 0) = r_n-1.

Esto permite detallar el algoritmo efectivo:

datos de entrada a y b - si hace falta, cambiarlos a positivos
el algoritmo:

mientras b ≠ 0 repetir las tres instrucciones siguientes:

r ← resto de a entre b (dar a r el valor del resto de a por b)

a ← b (el nuevo valor de a es el antiguo valor de b)

b ← r (el nuevo valor de b es el valor de r)

el resultado es a (su último valor).

Este algoritmo da como resultado 0 si a y b son nulos, mientras que en matemáticas, el mayor divisor de cero no existe.

[editar] Ejemplos

Implementación en Winpseudo V1.4

INICIO  Programa26 - "MCD - Algoritmo de Euclides - Usando RESTO"
   VAR 

      NUMERICO A
      NUMERICO B
      NUMERICO R
      STRING   PTR

   FIN-VAR

   LEER (A)
   LEER (B)

   R = 1
   MIENTRAS (R # 0)

      PTR = UNIR(NL,"   MCD(", A, ", ", B, ") = ")
      IMPRIMIR (PTR)

      R = A % B
      A = B
      B = R
      
   FIN-MIENTRAS

   IMPRIMIR ENTERO(A)

FINAL

INICIO  Programa26 - "MCD - Algoritmo de Euclides - Usando RESTAS SUCESIVAS"
   VAR 

      NUMERICO A
      NUMERICO B

   FIN-VAR

   LEER (A)
   LEER (B)


   MIENTRAS (A # B)

      IMPRIMIR NL, "   MCD("
      IMPRIMIR ENTERO(A)
      IMPRIMIR ", "
      IMPRIMIR ENTERO(B)
      IMPRIMIR ") = "

      SI (A < B)
         INTERCAMBIAR (A, B)
      FIN-SI    

      A = A - B

   
   FIN-MIENTRAS

   IMPRIMIR NL, "   MCD = "
   IMPRIMIR ENTERO(B)

FINAL

Se busca el máximo común divisor de a = 945 y b = 651, números escogidos al azar:

945 = 1×651 + 294
651 = 2×294 + 63
294 = 4×63 + 42
63 = 1×42 + 21
42 = 2×21 + 0 entonces mcd(945; 651) = 21 (el último resto no nulo).

Como segundo ejemplo, tomemos números de tamaños parecidos a los anteriores: a = 987 y b = 610:

987 = 1×610 + 377
610 = 1×377 + 233
377 = 1×233 + 144
233 = 1×144 + 89
144 = 1×89 + 55
89 = 1×55 + 34
55 = 1×34 + 21
34 = 1×21 + 13
21 = 1×13 + 8
13 = 1×8 + 5
  8 = 1×5 + 3
  5 = 1×3 + 2
  3 = 1×2 + 1
  2 = 2×1 + 0        entonces mcd(987; 610) = 1 (el último resto no nulo).

El segundo ejemplo es sustancialmente más largo que el primero, y esto se debe a que todos los cocientes valen 1. Aquí a y b no fueron escogidos al azar: son dos términos consecutivos de la sucesión de Fibonacci; es el peor de los casos para este algoritmo. Sin embargo, el número de pasos elementales es en O $(n 2)$ - inferior a $A n 2$ con A una constante - donde n es el número de cifras del más pequeño entre a y b.

==Algoritmo en c.==

   int r,a,b;
   
   printf ("\n Introduce un numerador: ");
   scanf ("%d",&a);
   
   printf ("\n Introduce un denominador: ");
   scanf ("%d",&b);
   
   if (a<0)a=a*-1;
   if (b<0)b=b*-1;
   
   while (b!=0)
   {
             r=a%b;
             a=b;
             b=r;
   }
   printf ("\n El resultado es %d",a);
   return a;|

[editar] Número de pasos elementales

Para ver la demostración en la que se postula que el número de pasos elementales que hay que hacer en el algoritmo de Euclides es una función logarítmica en base a la Divina Proporción sobre el menor de los números sobre los cuales queremos conocer el máximo común divisor:

cliquea aquí

[editar] Fracciones continuas

Las divisiones euclidianas del algoritmo son idénticas a las que permiten hallar la expresión en fracción continua de $\frac a b$
.

En efecto, $a = b q 1 + r 1$ se puede escribir $\frac a b = q_1 + \frac {r_1} b$ . Del mismo modo, $b = r_1 q_2 + r_2 \,$ se escribe $\frac b {r_1} = q_2 + \frac {r_2} {r_1}$ y si lo inyectamos en la igualdad anterior obtenemos $\frac a b = q_1 + \frac 1 {q_2 + \frac {r_2} {r_1}}$ y el proceso se repite hasta utilizar todas las divisiones euclidianas, y da lugar a fracciones con muchos "pisos". Los dos ejemplos numéricos del párrafo anterior dan:

$\frac {945} {651} = 1 + \frac 1 {2 + \frac 1 {4 + \frac 1 {1 + \frac 1 2 }} } \quad \quad y \quad \quad \frac {987} {610} = 1 + \frac 1 {1 + \frac 1 {1 + \frac 1 {1 + \frac 1 {1 + \frac 1 {1 + \frac 1 {1 + \frac 1 {1 + \frac 1 {1 + \frac 1 {1 + \frac 1 {1 + \frac 1 2 }}}}}}}} }}$

Este proceso funciona también con valores irracionales de a/b (con a y b reales). en tal caso, el algoritmo no se para, lo que da una fracción continua infinita. Son de especial interés estas fracciones, como en los casos de π y e.

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.

[editar] Generalización a los polinomios

Este algoritmo sólo precisa de la división euclidiana, y por consiguiente se extiende a todos los dominios donde existe tal división: es el caso de las álgebras de polinomios, como Q[X] o R[X], (polinomios con coeficientes racionales o reales). Obviamente, los cálculos se vuelven mucho más largos.
Un ejemplo no demasiado complicado, pero tampoco trivial:

Sea $P=X^3-6X^2-63X+392 \quad$ un polinomio que se cree que tiene una raíz doble.

como resolver una ecuación de tercer grado no es evidente, para hallar la raíz múltiple empleamos la propiedad que dice las raíces múltiples son las en común entre el polinomio y su polinomio derivado.

Para simplificar las divisiones, nos permitimos multiplicarlos por factores constantes no nulos, en fin de cuentas el mcd de dos polinomios está definido módulo un factor multiplicativo, así que esta manipulación no altera el resultado.

El polinomio derivado de P es $P' = 3X^2 - 12X - 63 \quad$ que se puede simplificar por 3, según lo dicho anteriormente.

Tomemos entonces $Q = \frac {P'} 3 = X^2 - 4X - 21$ y efectuemos el algoritmo con P y Q.

$P = (X-2)Q -50X + 350 \quad$ . El resto se factoriza en $\quad -50(X - 7)$ : tomemos entonces $\quad R = X - 7$

$Q = (X+3)R + 0 \quad$ lo que implica que el mcd buscado es $X-7 \quad$ entonces 7 es la raíz doble de P.

En efecto: $P = (X - 7)^2(X + 8 ) \quad$ y de paso $P' = 3(X - 7)(X + 3) \quad$

El contenido de este artículo incorpora material de una entrada de la Enciclopedia Libre Universal, publicada en castellano bajo la licencia GFDL.

Obtenido de "http://es.wikipedia.org../../../a/l/g/Algoritmo_de_Euclides_a568.html"

Categorías: Teoría de números | Algoritmos | EL