Algoritmos


Algoritmo de Euclides
El algoritmo de Euclides encuentra el máximo común divisor de dos enteros. Este algoritmo usa
divisiones y restas y está basado principalmente en las identidades.
PasoOperación
Significado
1
89 dividido entre 55 es 1 y sobran 34
mcd(89,55) = mcd(55,34)
2
55 dividido entre 34 es 1 y sobran 21
mcd(55,34) = mcd(34,21)
3
34 dividido entre 21 es 1 y sobran 13mcd(34,21) = mcd(21,13)
4
21 dividido entre 13 es 1 y sobran 8
mcd(21,13) = mcd(13,8)
5
13 dividido entre 8 es 1 y sobran 5
mcd(13,8) = mcd(8,5)
6
8 dividido entre 5 es 1 y sobran 3
mcd(8,5) =mcd(5,3)
7
5 dividido entre 3 es 1 y sobran 2
mcd(5,3) = mcd(3,2)
8
3 dividido entre 2 es 1 y sobran 1
mcd(3,2) = mcd(2,1)
9
2 dividido entre 1 es 2 y sobra 0
mcd(2,1) = mcd(1,0)
EJEMPLO # 2Paso
Operación
Significado
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

La secuencia deigualdades  implican que . Dado que , entonces se concluye que . 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úmerosnaturales  y , se siguen las siguientes reglas:
1. Si  entonces  y el algoritmo termina
2. En otro caso,  donde  es el resto de dividir  entre . Para calcular  se utilizan estas mismas reglasTEOREMA DEL RESIDUO
Teorema que establece que si un polinomio de x, f(x), se divide entre (x-a), donde a es cualquier numero real o complejo, entonces el residuo es f(a).
El teorema del residuosirve para encontrar de forma mas rapida el residuo de una division entre polinomios.
Tambien sirve para encontrar factores de dicho polinomio.

EJEMPLO

Hallar el residuo que resulta de dividirx2+x-2 / x-1
X-1=0 ( se iguala el divisor a cero )
X=1 al residuop se le llama p(-2)
Se sustituye p(x) por P(-2)
Residuo =(1)2+(1)2-2
= 1+1-2
= 0
Factores del polinomio
(x-1) (x+2)...