Clase 2

Vista previa del material en texto

Algoritmos y Estructuras de 
Datos
Departamento de Informática
LAS - TUP
Clase 2
Números Primos
Definición: Dado un entero p ∈ ℵ , p>1 , se dice que es un número primo si sus 
divisores son 1 y el propio número p.
Los números que no son primos son compuestos.
Métodos relacionados a números primos - Divisibilidad
Para todo m > 2 ∈ ℵ , m2 - m es compuesto
m2 - m = m x (m-1)
Algoritmo: Determinar si un número es primo o no.
Teorema
Todo número compuesto m ∈ ℵ tiene al menos un divisor primo.
Demostración: Sabemos que los divisores de un número son menores o iguales 
que el mismo. Por lo tanto dicha cantidad es finita. Vamos a probar que el menor 
de los divisores es primo.
Sea a el menor divisor de m. Este debería ser primo, si fuera compuesto entonces 
tendría un divisor a’ < a y dado que si a | m entonces a’ | m siendo esto un 
contradicción con la hipótesis ya que a es el menor divisor de m.
Entonces si a no puede ser compuesto, debe ser primo.
Teorema
Si m es un número compuesto, entonces tendrá un divisor primo menor o igual a √ m
Demostración: si m es compuesto entonces existe un divisor a con 1<a<m y m=a x b
m = √ m x √ m y m no puede ser mayor que a x b, por hipótesis.
Entonces, a <= √ m o b<=√ m , por lo tanto m tiene un divisor <= √ m
Ej. 47: maximo divisor ⎣√ 47⎦ = 6 => 2⤫47, 3⤫47, 4⤫47, 5⤫47, 6⤫47 => si es primo
Ej. 68: máximo divisor ⎣√ 68⎦ = 8 => 2/68 => no es primo
Teorema fundamental de la aritmética
Todo número compuesto m ∈ ℵ , m>1 , se puede expresar de manera única 
como el producto de factores primos: pi
ei
m = p1
e1 x p2
e2 x p3
e3 x...x pk
ek = ∏k i=1pi
ei
Donde p1, p2, …, pk son primos entre si y e1, e2, ek son naturales
Ejemplo: 12 = 2 x 2 x 3 = 22 x 3
Teorema fundamental de la aritmética
Lemas
Si p y q son primos y p|q, entonces p=q o p=-q
Si p es primo y p|(a*b), entonces p|a o p|b
Si n (entero) es compuesto, entonces existe un primo, p, que lo divide, es decir, 
p|n 
Teorema fundamental de la aritmética
Existencia:
Si m es compuesto entonces tiene un divisor que es primo: m = p1 x a 
Si a fuese primo queda demostrada la existencia de la factorización.
Si a es compuesto entonces a tiene un primo p2 tal que a = p2 x b. 
Reemplazando m = p1x p2 x b y así podemos repetir el procedimiento.
Se observa que a > b > c > … Se obtendrá un primo ph tal que m = p1x p2 x … x 
ph 
Como los p se pueden repetir => m = p1
e1 x p2
e2 x p3
e3 x...x pk
ek
Teorema fundamental de la aritmética
Unicidad:
Vamos a suponer que el teorema es falso => m tiene más de una factorización.
m = p1x p2 x … x pr = m = q1x q2 x … x qs
Algoritmo: Determinar los factores primos de un número compuesto.
Teorema: La sucesión de números primos es infinita
Se demuestra que dado un primo pk, existe otro primo mayor a él.
Sabemos que cualquier número m puede expresarse como:
m = p1
e1 x p2
e2 x p3
e3 x...x pk
ek +1
● si m es primo queda demostrado ya que obtuvimos un primo m > pk
● m no es primo...
La Criba de Eratóstenes
Método que permite obtener todos los primos entre 2 y un número entero dado.
● Empezamos en el número 2, dejamos el número 2 como primo pero 
tachamos todos los múltiplos de 2 (es decir, tachamos 4, 6, 8, etc.).
● Se continúa con el siguiente número no tachado en la tabla, en este caso el 
número 3, dejamos el número 3 como primo y tachamos todos los múltiplos 
de 3 (es decir tachamos 6, 9, 12, etc.).
● El siguiente número no tachado en la tabla es el 5, dejamos el número 5 
como primo y tachamos todos los múltiplos de 5 (es decir tachamos 10, 15, 
20, etc.).
● Este proceso se repite hasta que lleguemos al número N, habiendo 
previamente tachado todos los múltiplos de los números primos encontrados.
La Criba de Eratóstenes