ALGORITMO DE EUCLIDES - creado desde un Mapa Mental

Page 1

ALGORITMO ORIGINAL

Dos segmentos AB y CD son conmensurables cuando existe un tercer segmento PQ el cual cabe exactamente un número entero de veces en los primeros dos, es decir, PQ midea los segmentos AB y CD.

Dados dos segmentos AB y CD con AB>CD, restamos CD de AB tantas veces como sea posible. Si no hay residuo, entonces CD es la máxima medida común. Si se obtiene un residuo EA, éste es menor que CD y podemos repetir el proceso: restamos EA tantas veces como sea posible de CD. Si al final no queda un residuo, EA es la medida común..

ALGORITMO TRADICIONAL

Al dividir a entre b , 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 Sea c el máximo común divisor de a y b,.Como a=bq+r y c divide a a y a b divide también a r. Si existiera otro número mayor que c que divide a b y a r, también dividiría a a , por lo que c no sería el mcd de a y b, lo que contradice la hipótesis. Importante tener en cuenta que el máximo común divisor de cualquier número a y 0 es precisamente a.

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

Introduce el texto aquí

ALGORITMO 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 la mínima combinación lineal de esos números, es decir, encontrar números enteros s y t tales que mcd}(a,b)=a s+b t. Esto se generaliza también hacia cualquier dominio euclideano.

Usar el algoritmo tradicional de Euclides. En cada paso, en lugar de "a dividido entre b es q y de resto r" se escribe la ecuación a=b q+r . Se despeja el resto de cada ecuación. Se sustituye el resto de la última ecuación en la penúltima, y la penúltima en la antepenúltima y así sucesivamente hasta llegar a la primera ecuación, y en todo paso se expresa cada resto como combinación lineal.

ALGORITMO DE EUCLIDES