Academia Virtual 5

Hacia la CENTRO 2010 Teoría de números: Wilson, Fermat y Euler 27 de febrero de 2010 Arturo PortnoyTeorema de Wilson Si p es primo entonces (p-1)!≡-1 (mod p).Pequeño teorema de Fermat Si p es primo y a es entero, entonces a^p≡a (mod p).Función de Euler Sea φ(n) la cantidad de números naturales menores o iguales que n que son primos relativos con n.Teorema de Euler Sea n un entero positivo y sea a un entero primo relativo con n. Entonces a^(φ(n))≡1 (mod n).Ejercicio Encontrar el último dígito decimal de 7^222.Ejercicio Encontrar el entero positivo mas pequeño tal que 7x^25-10 es divisible entre 83.Ejercicio Calcular el residuo de la división entre 13 del número 7^44.Ejercicio Demostrar que 2^70 + 3^70 es divisible por 13.Ejercicio Si p es un número primo mayor que 5, demostrar que p^4-1 es divisible por 240.Ejercicio Demostrar que los posibles residuos de la división entre 7 de un cubo perfecto son 0, 1 ó 6.Ejercicio Calcular el residuo de la división de 2^98 entre 101.Ejercicio Si m es primo y a,b son dos números enteros positivos menores que m, demostrar que a^(m−2)+a^(m−3)b+a^(m−4)b^2 +...+b^(m−2) es múltiplo de m.Encripción RSA  p y q son dos primos grandes y N=pq  N puede hacerse público sin revelar p y q (factorización es difícil)  Sea T=(p-1)(q-1)=φ(N) y sea e primo relativo con T y 0square root of 323 is a little less than 18, so they would have to try a maximum of 7 divisors before they would be guaranteed to break the modulus into the original primes that were used to find the public and private keys. Using a computer, this would not be difficult, so real RSA encryption uses numbers that are sufficiently large so that even the fastest computers would take longer than a human lifespan to factor them. It is upon this foundation, the difficulty of factoring products of two large prime numbers, that modern data encryption rests.