Algoritmo De Euclides Mcd Polinomios 2q2218

Algoritmo de Euclides tradicional Al dividir

entre

divisor de

y

(números enteros), se obtiene un cociente es el mismo que el de

y

y un residuo

. Es posible demostrar que el máximo común

(Sea c el máximo común divisor de

y

,.Como a=bq+r y c divide a

ya

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

y

, lo que contradice la hipótesis). Éste es el fundamento principal del algoritmo. También es importante tener en

cuenta que el máximo común divisor de cualquier número notación

y

significa máximo común divisor de

es precisamente y

. Para fines prácticos, la

.

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 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

Significado

La secuencia de igualdades

implican

que

. Dado que

que

, entonces se concluye

. 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 1.Si

entonces

y

, se siguen las siguientes reglas:

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

Paso

y

. Aplicando estas reglas se obtiene la siguiente secuencia de operaciones:

1

Operación dividido entre es y sobran

2

dividido entre

es

y sobran

3

dividido entre

es

y sobran

dividido entre dividido entre

es es

Significado

y sobran y sobra

Como la sucesión de residuos va disminuyendo, al final 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 con coeficientes racionales 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 1

Operación entre sobra

Significado

dividido es y dividido

2

3

entre sobra entre sobra 0

es

y

dividido es

y

De esta manera se concluye que su máximo común divisor es

.

Descripción formal 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 1. , 2. 3. Mientras haga lo siguiente: 1. 2. 4. El resultado es:

y

"