Download factorizacion unica

FACTORIZACION UNICA
El teorema fundamental de la
Aritmética o teorema de factorización
única afirma que todo entero positivo se
puede representar de forma única como
producto de factores primos.
Euclides
Filosofo y matemático griego que nació alrededor del año
325 a. de C. Su obra más importante de Euclides, y de las
matemáticas, sea “Elementos”, que es un extenso tratado
de matemáticas sobre materia tales como: geometría
plana, proporciones en general, propiedades de los
números, magnitudes inconmensurables y geometría del
espacio.
Johann Carl Friedrich Gauss (1777-1855)
Matemático, astrónomo y físico alemán que contribuyó
significativamente en muchos campos, incluida la teoría
de números, el análisis matemático, la geometría
diferencial, la geodesia, el magnetismo y la óptica.
Considerado "el príncipe de las matemáticas" y "el
matemático más grande desde la antigüedad", Gauss ha
tenido una influencia notable en muchos campos de la
matemática y de la ciencia, y es considerado uno de los
matemáticos que más influencia ha tenido en la historia.
Fue de los primeros en extender el concepto de
divisibilidad a otros conjuntos.
Mersenne
Es recordado principalmente gracias a los números que
llevan su nombre: los números primos de Mersenne.
Mersenne los introdujo en su Cognitata physicomathematica en 1641, donde conjeturó algunas
propiedades sobre ellos, algunas de las cuales sólo
pudieron ser comprobadas o refutadas ya en el siglo XX.
También es cierto que tradujo y comentó las obras de
Euclides, Arquímedes y otros matemáticos griegos.
Mn = 2n − 1.
Euclides habla de la conexión entre los números
perfectos y los primeros de Mersenne, da una
demostración sobre la infinito de los números
primos, estudia la divisibilitat, trata el lema de
Euclides de factorización que trae al teorema
fundamental de la aritmética sobre la
factorización única en números primos, y da el
algoritmo de Euclides para encontrar el máximo
común divisor de dos números, que es lo más
rápido que existe.
"Todo entero mayor que 1 y que no sea un
número primo es igual al producto de un y sólo
un conjunto de números primos".
Este teorema fue demostrado por primera vez
por el matemático alemán Carl Friedrich Gauss.

Divisores.

Teorema fundamental.

Implicaciones.

El máximo común divisor (abreviado
mcd o m.c.d.) de dos o más números
enteros es el mayor número que los divide
sin dejar resto.
DESCOMPOSICIÓN EN FACTORES PRIMOS
El máximo común divisor de dos números puede calcularse
determinando la descomposición en factores primos de los dos
números y tomando los factores comunes elevados a la menor
potencia, el producto de los cuales será el MCD. Por ejemplo, para
calcular el máximo común divisor de 48 y de 60 obtenemos la
factorización en factores primos.
De las factorizaciones de 48 y 60:
48
24
12
6
3
1
48 = 24 3
2
2
2
2
3
60
30
15
5
1
2
2
3
5
60 = 22 3 5
El MCD son los factores comunes con su menor exponente, esto es:
MCD (48, 60) 22 3 = 12
ALGORITMO DE EUCLIDES
Siendo a y b dos enteros positivos tales que a>b,
comenzamos dividiendo a/b, con lo que obtendremos un
resto r1 y un cociente q1. Hacemos la operación q1=a/b,
utilizando la división entera, sin decimales.... pero realmente
no sólo nos interesa el resultado o cociente de la división,
sino que nos interesa también el resto, así que la operación
la vamos a reescribir de otra forma. Es importante que
llamemos "a" al mayor de los dos números. Debemos
dividir a entre b y obtener un cociente (al que llamaremos
q1) y un resto (al que llamaremos r1).
a=q1·b+r1
en la segunda iteración, dividiríamos b/r1 obteniendo un resto r2
(hacemos la operación de división para obtener el cociente, al que
llamamos q2 y la de obtener el resto, al que llamamos r2), de tal
manera que se cumpla lo siguiente:
b=q2·r1+r2
En la tercera iteración, dividimos r1/r2 obteniendo un resto r3
r1=q3·r2+r3
Y se continúa así hasta obtener un resto 0. El último resto rk
distinto de cero es el mcd.
rk-2=qk·rk-1+rk
Ejemplo:
Halle M.C.D.(12 378, 3 054).
12 378 = 12 378 3 054 + 162 = 4´3 054 + 162
3 054
3 054 = 3 054 162 + 138 = 18´162 + 138
162
162 = 162 138 + 24 = 1´138 + 24
138
138 = 138 24 + 18 = 5´24 + 18
24
24 = 24 18 + 6 = 1´18 + 6
18
18 = 18 6 + 0 = 3´6 + 0
6
Luego M.C.D.(12 378, 3 054) = 6 que es el último residuo no
cero.
Conceptos matemáticos
• Factorización
• Factorización prima
• Árbol de factores
FACTORIZACIÓN
Factorizar un número o una expresión
algebraica, es encontrar los factores que,
al multiplicarlos, den un producto igual al
número o a la expresión
Factorización prima
• Te proponemos memorizar estos números primos:
{2, 3, 5, 7, 11}, te servirán para muchos cálculos
importantes.
• Factorización prima es una forma original de escribir
cualquier número compuesto.
Consiste en descomponer el número en un par de sus
factores, luego revisamos si cada uno de ellos es primo
y, si no lo es, lo volvemos a descomponer.
TEOREMA FUNDAMENTAL DE LA
ARITMÉTICA.
Cualquier número entero, distinto de cero,
puede ser representado en forma del
producto de números primos, siendo la
descomposición en factores única.
Ejemplo Árbol de Factores
• Para comprenderlo mejor veamos este ejemplo:
• 36 = 12 · 3 (3 es primo y 12 es compuesto, por
lo tanto, lo descomponemos en 3 · 4. De estos
dos números, 3 es primo y 4 compuesto, por lo
que volvemos a descomponer en 2 · 2).
• Si tomamos todos los números primos tenemos:
2 · 2 · 3 · 3. A esta forma se le conoce como
árbol de factores.
Hallar la facturación prima del numero
36
9
x
x
x
16
x
4
x
4
x
x
x
100
x
x
4
x
x
144
12
12
ENCUENTRA EL MAXIMO COMUN DIVISOR

16, 24, 40

28, 42, 56, 70

137, 2603

144, 520

212, 1431
ENCUENTRA EL MCD POR EL ALGORITMO DE EUCLIDES

252, 168

850, 345

47190, 19578

1560, 1176

2550, 850
1.
2.
3.
4.
5.
ENCUENTRA LA FACTORIZACIÓN UNICA POR
ARBOL DE FACTORES
850
744
518
1260
2738
Algoritmos de factorización
De propósito general
El tiempo de ejecución de un algoritmo de factorización de propósito
general depende solamente del tamaño del entero a factorizar. Éste es el
tipo de algoritmo usado para factorizar números RSA. La mayoría de
algoritmos de factorización de propósito general están basados en el
método de congruencia de cuadrados. A continuación se listan algunos de
los algoritmos de propósito general más conocidos:





Algoritmo de Dixon
Factorización con fracciones continuas
Criba cuadrática
Algoritmo general de criba del cuerpo de números
Factorización de formas cuadradas de Shanks







De propósito específico
El tiempo de ejecución de un algoritmo de factorización
de propósito específico depende de las propiedades de
sus factores desconocidos: tamaño, forma especial, etc.
Dichos factores cambian de un algoritmo a otro.
División por tentativa
Algoritmo rho de Pollard
Algoritmo p-1 de Pollard
Algoritmo p+1 de Williams
Factorización de curva elíptica de Lenstra
Método de factorización de Fermat
Algoritmo especial de criba del cuerpo de números
Números compuestos
• Un número natural es compuesto si tiene más de dos divisores
distintos.
• También lo podemos definir como aquel número natural que es
mayor que 1 y no es primo. Todo número compuesto puedo
descomponerse de forma única como producto de números
primos.
• Los 20 primeros números compuestos son: 4, 6, 8, 9, 10, 12, 14,
15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30 y 32.
• Una característica de los números compuestos es que pueden
escribirse como producto de dos enteros positivos menores
que él. Así, el número 20 es compuesto porque puede
expresarse como 4 x 5; y también el 87 ya que se expresa como
3 x 29. Sin embargo, no es posible hacer lo mismo con el 17 ó
el 23 porque son números primos.
• El número compuesto más pequeño es el 4 y no hay ninguno
que sea mayor que todos los demás; hay infinitos números
compuestos.