Algoritmo de la división. números primos. criba de eratóstenes. factorización. máximo común divisor y mínimo común múltiplo. euclides

INDICE.
ALGORITMO DE LA DIVISIÓN....................................................3
NUMEROS PRIMOS.....................................................................5
CRIBA DE ERATOSTENES.........................................................8
FACTORIZACION DE UN NUMERO.........................................10
MÁXIMO COMUNDIVISOR.......................................................11
MÁXIMO COMUN MÚLTIPLO...................................................12
ALGORITMO DE EUCLIDES.....................................................12
CONCLUSIONES.......................................................................14

ALGORITMO DE LA DIVISIÓN.
Comenzaremos esta sección estudiando el algoritmo de la división que establece el siguiente teorema:
Teorema 1.4. [Algoritmode la división] Si a y b son enteros con b > 0, existe un único par de enteros q y r tales que
[pic]
Demostración:
1. Existencia: Sea [pic]. Este conjunto de enteros contiene elementos no negativos (por ejemplo, para n = - | a | ), por lo que S*= S [pic]N es un subconjunto no vacío de N y, por tanto, de Z . El axioma de buena ordenación de los números enteros nos asegura laexistencia de un primer elemento de S* que será de la forma r = a - qb [pic]0 para algún entero q. Se tiene, por tanto, que a = qb+r con r [pic]0. Si r [pic]b, S* contendría al elemento no negativo a - (q+1)b = r - b < r que contradice el hecho de que r es el primer elemento del conjunto S*. Por tanto, r < b.
2. Unicidad: Supongamos que existen dos parejas de enteros (q, r) y (q', r') tales que[pic]
Se tiene entonces que
[pic]
lo que imposibilita el hecho de que | r - r' | < b. Por tanto, ha de ser q = q' y de ahí que también sea r = r', lo que prueba la unicidad.  
Definición 1.5. Con la notación del Teorema 1.4 el entero q recibe el nombre de cociente entero o simplemente cociente y el también entero r el de resto. Si dividimos por b obtenemos que a / b = q+r / b con 0[pic]r / b < 1 por lo que q viene dado por la parte entera por defecto o suelo de a / b (el mayor entero i con i[pic]a / b) y que denotaremos por [pic]. Esto facilita el cálculo de q. El de r se realiza posteriormente mediante la igualdad r = a - qb.
Si consideramos ahora el caso b < 0, dado que -b > 0, el Teorema 1.4 nos garantiza la existencia de los enteros q* y r tales que a = q*(-b) + r con 0 [pic]r < - b, y haciendo q* = - q se obtiene que a= qb+ r. La prueba de la unicidad es similar a la anterior.
 
Teniendo en cuenta este resultado y el del Teorema 1.4, podemos establecer el siguiente corolario:
Corolario 1.6. Si a y b son dos enteros con b [pic]0, existe un único par de enteros q y r tales que
[pic] 
Obsérvese que si b < 0 se tieneque a / b = q + r / b con 0 [pic]r / b > -1 por lo que en este caso q es la parte entera por exceso o techo del cociente a / b que denotaremos por [pic], es decir, el menor entero i tal que i [pic]a / b. 
Definición 1.7. Si a y b son enteros y a= qb para algún entero q, diremos que b divide a a, o bien que b es un factor o un divisor de a, o también que a es múltiplo de b.
Así, por ejemplo, losfactores de 6 son ±1, ±2, ±3 y ±6. Cuando b divide a a lo denotaremos por b | a. Para evitar errores obsérvese que cualquier entero divide a 0 (ya que 0 = 0 · b para cualquiera que sea el entero b), 1 divide a cualquier entero y cualquier entero se divide a si mismo. Debido a ello, dado un entero n, sólo los divisores de n distintos de 1 y del propio n se consideran divisores propios de dichonúmero.
Recordamos a continuación algunas propiedades simples pero útiles de la divisibilidad, probando dos de ellas y dejando la demostración de las otras a modo de ejercicios para el alumno.
Teorema 1.8. Se verifican las siguientes propiedades:
1. a | b y b | c [pic]a | c.
2. a | b y c | d [pic]ac | bd.
3. Si m [pic]0 [pic]a | b si, y sólo si, ma | mb....