jueves, 12 de junio de 2008

descomposicion en factores primos

Descomposición de un número natural en producto de factores primos Explicación y ayuda para descomponer correctamente cualquier número natural en producto de sus factores primos.
Los números naturales pueden ser primos o compuestos.Los números compuestos se llaman así porque se pueden descomponer en producto de números (factores) primos.Este proceso de descomposición es muy importante para muchos procesos numérico/matemáticos.Las reglas de divisibilidad nos ayudan en esta tarea.Primero vemos (con la regla de divisibilidad) si el número es divisible por ese primo. luego, hacemos la división y convertimos el número (dividendo) en el producto de divisor por cociente.
Si el número es pequeño podemos intentar hacerlo "de cabeza". El proceso podría ser:1.- Buscamos una pareja de números cualesquiera que multiplicados den el número inicial.2.- Si esta pareja de números son primos, ya hemos acabado.3.- En caso de que alguno de los factores no sea primo, se vuelve a descomponer en producto de otros dos...4.- Repitiendo los pasos anteriores hasta que todos los factores sean primos.5.- Una vez encontrados los factores primos, se ordenan de menor a mayor (es un convenio presentarlo de esta forma).6.- Posteriormente, si hay varios factores iguales, se presenta en forma de potencia. (Nosotros, de momento, no lo vamos a presentar en forma de potencia).Ejemplo:Supongamos que tengo que descomponer el 36.La primera pareja de números que se me ocurre que multiplicados dan 36 es nueve por cuatro:36 = 9 x 4Como ni nueve ni cuatro son primos, los vuelvo a descomponer:36 = (3 x 3) x (2 x 2)Y ordeno los factores de menor a mayor:36 = 2 x 2 x 3 x 3Puedes practicar intentando descomponer en producto de factores primos, los primeros números compuestos. Ten en cuenta que el orden es fundamental y que el programa no va a considerar como correcto un producto que no esté correctamente ordenado de menor a mayor:

minimo comun multiplo

Mínimo común múltiplo
El mínimo común múltiplo («m.c.m.» o «mcm») de dos o más números naturales es el menor número natural (distinto de cero) que es múltiplo de todos ellos. Para el cálculo del mínimo común múltiplo de dos o más números se descompondrán los números en factores primos y se tomarán los factores comunes y no comunes con su mayor exponente.
Por ejemplo, de las factorizaciones de 6936 y 1200,
6936 = 23 · 3 · 172
1200 = 24 · 3 · 52
podemos inferir que su m.c.m. es 24 · 3 · 52 · 172 = 346 800.
Conociendo el máximo común divisor de dos números, se puede calcular el mínimo común múltiplo de ellos, que será el producto de ambos dividido entre su máximo común divisor.

El m.c.m. se emplea para sumar o restar fracciones de distinto denominador, por ejemplo,

Cálculo del m.c.m.
Descomponer los números en factores primos.
Para cada factor común, elegir entre todas las descomposiciones aquel factor con mayor exponente.
Multiplicar todos los factores elegidos.

maximo comun divisor

Máximo común divisor
El máximo común divisor («m.c.d.» o «mcd») de dos o más números naturales es el mayor divisor posible de todos ellos.

Propiedades
El máximo común divisor de dos números resulta ser el producto de sus factores primos comunes elevados al menor exponente.
Geométricamente, el máximo común divisor de a y b es el número de puntos de coordenadas enteras que hay en el segmento que une los puntos (0,0) y (a,b), excluyendo el (0,0).
En palabras más simples, el máximo común divisor de dos o más números es el número, más grande posible, que permite dividir a esos números.

Cálculo del mcd
Los dos métodos más utilizados para el cálculo del máximo común divisor de dos números son:
Se descompondrán los números en factores primos y se tomarán los factores comunes con su menor exponente, el producto de los cuales será el m.c.d.
Si el número es muy grande este método no es operativo porque no conocemos los posibles factores. En ese caso tenemos que utilizar el mucho más rápido algoritmo de Euclides.
El m.c.d. de tres números se puede calcular como sigue: mcd(a,b,c) = mcd(a, mcd(b,c)).

Ejemplos
mcd(48, 60). Podemos comprobar que los divisores de 48 y 60 son:
48 = {1,2,3,4,6,8,12,16,24,48};
60 = {1,2,3,4,5,6,10,12,15,20,30,60}
por lo que el máximo común divisor de ambos es 12. Véamoslo utilizando los dos métodos descritos anteriormente:
De las factorizaciones de 48 y 60, (48 = 24.3 y 60=22.3.5) podemos inferir que su m.c.d. es 22.3 = 12 o comúnmente expresado como mcd(60,48)=12.
Como puede verse hemos necesitado calcular los factorización de 48 y 60 en factores primos (En torno a 10 divisiones siendo los factores sencillos).
Si en cambio utilizamos el algoritmo de Euclides:
Calculamos el resto de dividir 60 por 48, 12 (En este caso es igual a restar 48 a 60).
Calculamos el resto de dividir 48 por 12: 0. Por tanto, el mcd de 48 y 60 es 12.
Como puede verse utilizando el algoritmo de Euclides hemos necesitado:
Una resta
Una división
otro ejemplo:
(6936,1200) = 23 · 3 = 24.
un último ejemplo, mcd(7000000, 7000002).
Tras un sencillo cálculo obtenemos los factores de ambos números:
7000000 = 26 . 56 . 7
7000002 = 21 . 32 . 157 . 2477
por lo que su mcd es 2 (Se trata del único factor común elevado al mínimo exponente, 1).
Si utilizamos el algoritmo de Euclides llegamos al mismo resultado (haciendo dos divisiones). 239