652607
Description
Mind Map by alejo_sali, updated more than 1 year ago
|
Created by alejo_sali
about 10 years ago
|
|
ALGORITMO DE EUCLIDES
- 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..
- 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..
- 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.
- 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
- 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
- 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.
- 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.
- 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.
- 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.
Want to create your own Mind Maps for free with GoConqr? Learn more.