Algebra

UniversalClase 2

Teoría de Números:

- Es la rama de la matemática relacionada con las

propiedades de los números en general y los

números enteros en particular.

- De acuerdo a los métodos usados, la teoría de

números se divide en diversos campos de estudio.

- Cientos de personas trabajan con problemas de la

Teoría de Números en la Internet.

- Ejercicio: Aplicaciones de la Criptografía?

Los números mas importantes para la criptografía, son los enteros

positivos, en especial:

LOS NÚMEROS PRIMOS

Fueron estudiados hace 2500 años por los griegos.

Pierre Fermat Leonhard Euler

Números Primos:Un número primo es un número natural mayor que 1 que tiene

únicamente dos divisores distintos, el mismo y el 1.

Se contraponen así a los compuestos, que son aquellos que tienen

algún divisor natural, a parte de sí mismos y del 1..

El número 1, por convenio, no se considera ni compuesto ni primo.

Los números primos menores que 100 son:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79,

83, 89 y 97.

Existen infinitos números primos.

Durante el siglo XX se ha desarrollado muchas técnicas para el estudio de

los números primos.

El desarrollo moderno de la Teoría de Números fue posible gracias a Carl

F. Gauss.

Desarrollo de las congruencias:

Dados números compuestos, un problema clave es obtener o

verificar la existencia de números primos.

Test de primalidad (Primality test)

Factorizar un entero positivo en primos es otro problema central

en la Teoría de Números.

La factorización se puede hacer usando el método División Trial

(Trial Division).Existen otros métodos mas eficientes (que descubrieron Fermat,

Euler y otros matemáticos)

La dicotomía entre el tiempo requerido para hallar primos grandes

y el tiempo requerido para factorizar enteros grandes, son

principios fundamentales de grandes sistemas de encriptación,

como

RSA.

Otra parte importante de la teoría de números es la búsqueda de

soluciones enteras.

• Ecuaciones de Diofanto.

• Ecuación de Fermat.

• Ejercicio: Soluciones???

En su último teorema Fermat dijo: Si n es un entero con n>2, la ecuación

no tiene solución, para x, y, z enteros.

Los enteros, funciones

Números enteros:Z = {…, -3, -2, -1, 0, 1, 2, 3, …}

Funciones:- Floor function.

- Ceil function.

- Round function.

Divisibilidad

Definición:Sean a,b enteros con b ≠ 0. Decimos que b divide a a si existe un entero

c tal que a = bc. Si b divide a a, escribimos b|a.

Ejemplos: -13|182, -3|33, 6 ł 44

Algoritmo de la División

Un número es divisible por otro, cuando la división es exacta, es

decir, el residuo es cero.

Criterios de divisibilidad:

Criterios de divisibilidad:

Criterios de divisibilidad:

Existen otros criterios de divisibilidad (por 4, 6, 8, 9, 10, 25, 125).

Números Primos

Un entero p > 1, se dice primo si sus únicos divisores son 1 y p. Si

p no es primo, se dice compuesto.

Los números primos menores que 100 son:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,

73, 79, 83, 89 y 97.

¿Cómo saber si un número es primo?El problema de decidir si un número es primo no es en general

fácil. Si n es un número muy grande, nos llevaría a hacer,

demasiados cálculos.

¿Cómo Saber si es Primo?• Dividir el número entre todos los menores a el, y que solo tenga 2

divisores (1 y el mismo).

• Dividir el número entre los primos inferiores a su raíz cuadrada (√𝑛).

Y cómo se cuales son los primos menores a dicha raíz?

• Ejemplos:

103 es primo? = √103 ≈ 10.1, los primos inferiores a 10 son 2, 3, 5, 7 y

ninguno de ellos divide a 103, por lo tanto 103 es primo.

2311 es primo? …

¿Cuántos primos hay?

Hay un número infinito de primos (Euclides).

¿Cómo Colar números primos? (Criba de Eratóstenes)

Cómo vimos anteriormente, se requiere conocer una lista de primos

para saber si un número es primo. Este método para determinar la

primalidad se conoce como ensayo y error o trial división.

Es efectivo para números pequeños, pero no para números muy

grandes.

La manera más eficiente de colar primos pequeños es “La Criba de

Eratóstenes”.

Permite colar todos los primos menores que un número natural n,

eliminando los números compuestos de la lista {2, …, n}. Es simple y

razonablemente eficiente mientras no haya almacenamiento (este

es su punto débil).

¿Cómo Colar números primos?

Primero tomamos una lista de números {2, 3, …, n} y eliminamos de la

lista los múltiplos de 2. Luego tomamos el primer entero después de 2

que no fue borrado (3) y eliminamos la lista de sus múltiplos, y así

sucesivamente.

¿Cómo Colar números primos?

• Primer refinamiento: Descartar solo los pares, excepto el 2, los

pares no son primos, así que podríamos continuar tachando

solamente sobre la lista de impares.

• Segundo refinamiento; Continuar tachando de p2k en adelante.

En el paso k-esimo hay que tachar los múltiplos del primo pk desde

p2k en adelante. Por ejemplo cuando nos toca tachar los múltiplos

del primo 7 ya se han eliminado los múltiplos de 2, 3 y 5 es decir 2 x

7, 3 x 7, 5 x 7 y 6 x 7. Por eso iniciamos en 72.

¿Cómo Colar números primos?

• Tercer refinamiento: Tachar mientras p2k <= n. En el paso k-esimo

hay que tachar los múltiplos del primo pk solo si p2k <= n, en otro

caso, nos detenemos ahí. Porque en el paso k-esimo tachamos los

múltiplos del primo pk desde p2k en adelante, asi que si p2

k > n, ya

no hay nada que tachar.

Hay variaciones de la criba de Eratóstenes, que son muy eficientes.

También podemos hacer uso de MATLAB ya que trae muchas

funciones matemáticas que además, son muy eficientes.

Tarea: Implementar la Criba de Eratóstenes, en el lenguaje de su

preferencia.

Teorema Fundamental de la Aritmética

Ejemplo:

Ejercicio:

Máximo Común Divisor

Si a, b son enteros no nulos, entonces d es un divisor común de a y b si

d|a y d|b.

Denotamos con Da al conjunto de divisores de a y con Db al conjunto

de divisores de b.

El máximo común divisor de a y b es el más grande entero positivo

común entre los divisores de a y los divisores de b (Da ∩ Db).

*Primos entre sí.

Máximo Común Divisor

Revisemos algunas propiedades útiles:

Ejemplo: mcd (3, 6, 12) = mcd(3, mcd(6, 12)) = mcd(3, 6) = 3

De ejemplos aplicando las propiedades.

Máximo Común Divisor

El Algoritmo de Euclides:

Algoritmo de Euclides

Algoritmo de Euclides Extendido

El algoritmo de Euclides puede ser extendido, donde el mcd d es

expresado como la combinación lineal de dos enteros.

d = ax + by