Algoritmo de Euclides

De Wikipedia, la enciclopedia libre

Uno o más wikipedistas están trabajando actualmente en extender este artículo.
Es posible que, a causa de ello, haya lagunas de contenido o deficiencias de formato. Por favor, antes de realizar correcciones mayores o reescrituras, contacta con ellos en su página de usuario o en la página de discusión del artículo para poder coordinar la redacción.

El algoritmo de Euclides es un método antiguo y eficaz para calcular el máximo común divisor (MCD) entre dos números enteros. Fue originalmente descrito por Euclides en la proposición 2 del libro VII de su libro Elementos. Tiene numerosas aplicaciones en teoría de números y ciencias de la computación.

[editar] Fundamentos del algoritmo

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.

De acuerdo con este fundamento, para calcular el máximo común divisor de $a$ y $b$ tan sólo es necesario calcular el máximo común divisor de $b$ y $r$ . Como $b$ y $r$ son números más pequeños, el número de operaciones se reduce. Además, para calcular el máximo común divisor de $b$ y $r$ se puede aplicar la misma regla recurrentemente. Por ejemplo, para calcular el máximo común divisor de 2366 y 273 se podría utilizar la siguiente secuencia de operaciones:

2366 entre 273 es 8 y sobran 182
273 entre 182 es 1 y sobran 91
182 entre 91 es 2 y sobra 0

Esta secuencia de operaciones se puede interpretar con el siguiente significado:

$mcd(2366,273) = mcd(273,182)$
$mcd(273,182) = mcd(182,91)$
$mcd(182,91) = mcd(91,0)$

De esta manera se concluye que el máximo común divisor de 2366 y 273 es 91 (porque $mcd(91,0) = 91$ ).

[editar] Descripción general

La expresión " $a$ entre $b$ es $q$ y sobra $r$ " se puede expresar matemáticamente como la siguiete ecuación:

$a=bq+r\quad 0\leq r<b$

Ambas expresiones son completamente equivalentes (véase Algoritmo de la división). Con base en esto, el algoritmo funciona para cualesquiera números enteros $a$ y $b$ mediante la sucesión de divisiones:

$\begin{array}{ll} a=bq+r_{1} & 0\leq r_{1}<b\\ b=r_{1}q_{1}+r_{2} & 0\leq r_{2}<r_{1}\\ r_{1}=r_{2}q_{2}+r_{3} & 0\leq r_{3}<r_{2}\\ \cdots & \cdots\\ r_{n-2}=r_{n-1}q_{n-1}+r_{n} & 0\leq r_{n}<r_{n-1}\\ r_{n-1}=r_{n}q_{n}+0 \end{array}$

El máximo común divisor de $a$ y $b$ es $r n$ , es decir, el último residuo distinto de 0. Esto siempre es cierto dado que en realidad sólo se está haciendo la siguiente secuencia de afirmaciones:

$\begin{array}{rcl} \mathrm{mcd}\left(a,b\right) & = & \mathrm{mcd}\left(b,r_{1}\right)\\ & = & \mathrm{mcd}\left(r_{1},r_{2}\right)\\ & \vdots\\ & = & \mathrm{mcd}\left(r_{n-1},r_{n}\right)\\ & = & \mathrm{mcd}\left(r_{n},0\right)\\ & = & r_{n}\end{array}$

De esta manera, el algoritmo puede enunciarse como sigue: "Para calcular el máximo común divisor de dos números naturales $a$ y $b$ , verifique si $b$ es cero; si es así, entonces $a$ es el máximo común divisor de $a$ y $b$ . En otro caso, repita el proceso usando (respectivamente) $b$ , y el resto de dividir $a$ entre $b$ ."

Este algoritmo puede ser usado en cualquier contexto donde la división con residuo sea posible. Esto incluye a los polinomios, los enteros de Gauss, y en general, en cualquier dominio euclídeo.

[editar] Ejemplos

Como primer ejemplo se muestra cómo calcular el máximo común divisor de 114569 y 180037:

$114569=180037\times0+114569$
$180037=114569\times1+65468$
$114569=65468\times1+49101$
$65468=49101\times1+16367$
$49101=16367\times3+0$

Entonces $mcd(114569,180037) = 16367$ . Como segundo ejemplo se muestra cómo calcular el máximo común divisor de $x 5 + 2 x 3 + x$ y $x 4 - 1$ (los paréntesis se han añadido para facilidad de lectura):

$\left(x^5+2x^3+x\right)=\left(x^4-1\right)\left(x\right)+\left(2x^3+2x\right)$
$\left(x^4-1\right)=\left(2x^3+2x\right)\left(\frac12x\right)+\left(-x^2-1\right)$
$\left(2x^3+2x\right)=\left(-x^2-1\right)\left(-2x\right)+\left(0\right)$

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

[editar] Descripción formal

El algoritmo de Euclides puede ser expresado en pseudocódigo de varias maneras. La notación aquí empleada hace uso del operador módulo, de manera que $a mod b$ representa el residuo de dividir $a$ entre $b$ . La manera más natural de expresar el algoritmo es utilizando recursión:

Algoritmo de Eulides recurrente
Función $\mathrm{mcd}(a,b)\,$ : Si $b=0\,$ entonces: El resultado es $a\,$ En otro caso: El resultado es $\mathrm{mcd}(b, a\,\mathrm{m\acute od}\,b)$

Sin embargo, para implementarlo en una computadora, es mejor considerar una versión iterativa:

Algoritmo de Eulides iterativo
Función $\mathrm{mcd}(a,b)\,$ Mientras $b>0\,$ haga lo siguiente: $(a,b)\gets(b,a\,\mathrm{m\acute od}\,b)$ Nota: Esto significa asignar a $a$ el valor de $b$ y a $b$ el resto de dividir $a$ entre $b$ El resultado es $a\,$

El algoritmo original descrito por Euclides trataba el problema de manera geométrica; usaba la sustracción repetida en lugar del residuo de la división. Esta versión es significativamente menos eficiente:

Algoritmo de Eulides original
Función $\mathrm{mcd}(a,b)\,$ : Mientras $b>0\,$ haga lo siguiente: Si $a>b\,$ entonces: $a\gets a-b$ En otro caso $b\gets b-a$ El resultado es $a\,$

[editar] Aplicaciones

[editar] Simplificar fracciones

Al momento de hacer cálculos con fracciones, es de gran importancia saber cómo simplificarlas. Por ejemplo, la fracción $\textstyle\frac{65}{91}$ es equivalente con $\textstyle\frac 5 7$ (véase Número racional). De manera más general, $\textstyle\frac ab=\frac {ca}{cb}$ siempre que $c\ne0$ . Para reducir una fracción cualquiera $\textstyle\frac a b$ , sólo se necesita dividir $a$ y $b$ entre su máximo común divisor.

Por ejemplo, si se desea reducir $\textstyle\frac{166}{249}$ , primero se usa el algoritmo de Euclides para encontrar $mcd(166,249) = 83$ . Se hacen las divisiones $\textstyle 166\div 83 = 2$ y $\textstyle 249\div 83 = 3$ . Luego entonces se concluye que $\textstyle\frac{166}{249}=\frac 2 3$ .

[editar] 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 $\textstyle\frac a b$ como fracción continua. Esto se debe a que si $a = b q + r$ y $r\neq 0$ , entonces

$\frac a b = q + \frac 1 {\frac b r}$

Por ejemplo, para encontrar el máximo común divisor de $93164$ y $5826$ el algoritmo genera la siguiente secuencia de divisiones:

$93164=5826\times 15+5774$
$5826=5774\times 1+52$
$5774=52\times 111+2$
$52=2\times 26+0$

Utilizando la fórmula anterior se convierte

$\textstyle\frac{93164}{5826}=15+ \frac 1 {\frac{5826}{5774}}$
$\textstyle\frac{5826}{5774}=1+ \frac 1 {\frac{5774}{52}}$
$\textstyle\frac{5774}{52}=111+ \frac 1 {\frac{52}{2}}$
$\textstyle\frac{52}{2}=26$

Si se substituye la segunda ecuación en la primera, se obtiene

$\frac{93164}{5826}=15+ \frac 1 {1+ \frac 1 {\frac{5774}{52}}}$

Si se repite este proceso de substitución entonces se obtiene la expresión deseada:

$\frac{93164}{5826}=15+ \frac 1 {1+ \frac 1 {111+ \frac 1 {26}}}$

De manera más general, la fracción continua encontrada con este algoritmo siempre es de la forma

$\frac{a}{b}=q_1+ \frac 1 {q_2+ \frac 1 {q_3+ \frac 1 {\ddots q_{n-1}+ \frac 1 {q_n}}}}$

[editar] Inversos modulares

[editar] Complejidad del algoritmo

Gráfica del tiempo de ejecución para

mcd(x, y)

. El rojo indica un cálculo rápido, mientras los puntos eventualmente azules indican tiempos de ejecución más grandes.

Si se considera que las operaciones aritméticas son operaciones elementales, sin pérdida de generalidad se supone que $b\geq a$ , entonces la complejidad del algoritmo está en el orden de $O(\log n)\,$ donde $n = b\,$ . Para ver esto, primero se considera que para cualesquiera dos enteros $a, b$ tales que $b\geq a$ , siempre se cumple

$b\,\bmod\, a < \frac{b}{2}$

Esto es porque:

Si $a>\frac{b}{2}$ , entonces $1\leq\frac{b}{a}<2$ , por lo tanto $b\div a = 1$ , lo cual implica que $b\,\bmod\,a=b-a\times(b\div a)=b-a<b-\frac{b}{2}=\frac{b}{2}$
Si $a\leq\frac{b}{2}$ entonces $b\,\bmod\,a<a\leq \frac{b}{2}$

Como se considera que las operaciones aritméticas son operaciones elementales, entonces la complejidad del algoritmo es del orden exacto del número de veces que se usa el ciclo mientras de la versión iterativa. Considérese a $a$ y $b$ después de pasar dos veces por el ciclo suponiendo que el algoritmo no se detiene antes. Sean $a 0$ y $b 0$ los valores de entrada al algoritmo. Después de la primera iteración $a=b_0\,\bmod\,a_0$ y seguidamente, en la segunda iteración $b$ toma ese valor.

De lo anterior, $b$ se ha vuelto más pequeño que $\frac{b_0}{2}$ . Es decir que $b$ se dividido al menos por dos después de dos pasadas por el ciclo. Además sigue siendo cierto que $b\geq a$ y por lo tanto se puede aplicar el mismo razonamiento. La conclusión es que a lo mucho, se pasará por el ciclo aproximadamente $2\log b\,$ veces.

Por lo tanto, la complejidad de $\mathrm{mcd}(m,n)\,$ con $n\geq m$ está en orden de $O(\log n)\,$ .

Sin embargo, si se considera que las operaciones aritméticas no son operaciones elementales, entonces el número de operaciones está acotado por $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.

[editar] Implementación

En lenguaje C (versión recursiva):

unsigned int mcd(unsigned int a, unsigned int b){
     return (b == 0)? a : mcd(b, a % b);
 }

En lenguaje Logo (versión recursiva):

para mcd :a :b
 si :b = 0 [
  devuelve :a
 ] sino [
  devuelve mcd :b resto :a :b
 ]
fin

En lenguaje C (versión iterativa):

unsigned int mcd(unsigned int a, unsigned int b){
     unsigned int aux;
     while (a > 0){
         aux = a;
         a = b % a;
         b = aux;
     }
     return b;
 }

En lenguaje Logo (versión iterativa):

para mcd :a :b
 mientras [:a > 0] [
  haz "t :a
  haz "a resto :b :a
  haz "b :t
 ]
 devuelve :b
fin

En lenguaje Visual Basic 8 (versión iterativa):

Public Function mcd(a As UInteger, b As UInteger) As UInteger
     Dim t As UInteger
     While a > 0
         t = a
         a = b Mod a
         b = t
     End While
     Return b
 End Function

En lenguaje Haskell (versión recursiva):

mcd::Int->Int->Int
mcd a 0 = a
mcd a b = mcd b (mod a b)

En lenguaje Pascal (versión iterativa):

function MCD(a , b:integer):integer;
 var
   t,result:integer;
 begin
   if b = 0 then
     result := a
   else
     while a > 0 do
     begin
       t := a;
       a := b mod a;
       b := t;
       result :=  b
     end;
   MCD:=result;
 end;

En lenguaje Java (versión iterativa): //Instalar drjava (http://www.drjava.org/download.shtml) // Uso (interactions pane): java mcd a b public class mcd {public static void main(String[] args) {if (args.length != 2) {System.out.println("Usage: java gcd arg1 arg2"); return;} int a = Integer.parseInt(args[0]); int b = Integer.parseInt(args[1]); System.out.println("gcd is " + gcd(a, b } public static int mcd(int a, int b) { while (a>0) {int t; t=a; a=b%a; b=t; } return +b; } } En lenguaje Python (versión recursiva):

def mcd(a, b):
    if b == 0:
        return a
    return mcd(b, a % b)

En lenguaje PHP (versión recursiva) :

function  mcd($a, $b){
     return ($b == 0)? $a : mcd($b, $a % $b);
 }

[editar] Referencias

Brassard, Gilles; Bratley, Paul: «Análisis de algoritmos», en Fundamentos de Algoritmia. Madrid: PRENTICE HALL, 1997. ISBN 84-89660-00-X

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

El contenido de esta página (o parte de ella) fue extraído de wikipedia y puede redistribuirse libremente bajo la licencia de documentación libre GNU

Esta página

Publicidad

Colabora

Teorema gráfico del día

Imágen espacio diaria