TCOM 500 M6 Flip Book

Módulo 6: Teorías de Números

Contenido 6.1 División y Aritmética Modular Empecemos por definir el teorema de la división o teorema de Euclides: “Sean a, b ∈  con b ≠ 0. Existen q, r ∈  únicos tal que ������ = ������������ + ������ ������������������ 0 ≤ ������ < |������| Ejemplo: Calcule q y r, utilizando el teorema, conocidos los valores de a y b en cada caso. 1. a = 715 y b = 19 2. a = 331 y b = 45 Solucion: • Primero dividimos a/b = 715/19 = 37 • Segundo verificamos cuanto nos falta para obtener a: 715 = 19*37 + 12 • Tercero, por lo tanto, q = 37 y r = 12 Compruebe el resultado del segundo ejemplo. 6.1.1 Modulo (Mod) Sean a, b ∈  con b>0. Según el teorema de Euclides, Mod se definirá como a Mod b = r. Veamos los siguientes ejemplos de aplicación: 1. 41 Mod 7 = ___ 41/7 = 5 7 * 5 = 35 41 – 35 = 6 Por lo tanto, el resultado es 6. 2. – 37 Mod 5 = 3 Compruebe como se obtuvo el 3. 6.1.2 Divisor Común Sean a, b ∈ , se dice que un entero d es divisor común de a y de b si d | a y d | b. Ejemplo: los divisores comunes de 24 y 18 = 2, 3, 6 6.1.3 Máximo Común Divisor

Sean a, b ∈ , se dice que d ∈  es el Máximo Común Divisor y se denota como mcd de a y b si: • d es divisor común entre a y b • Si e es divisor común de a y b, entonces e ≤ d Ejemplo: Determine el mcd (18, 24) Solución: Como pudimos ver en la sección anterior, los divisores son 2, 3, 6 Por lo tanto, el 6 sería el mcd Veamos a continuación el siguiente teorema: Sean a, b ∈ , diferentes de cero, el entero positivo más pequeño de la forma ax + by, denominado min(ax + by) donde x, y ∈ , es el mcd(a, b). Ejemplo: Determine mcd(86, 46) y el mcd(45, 60) Solución: Existen dos maneras fáciles para resolver el mismo. La primera, construimos una tabla en Excel como esta: Pasos a b c 1 86 46 40 2 46 40 6 3 40 6 4 4642 5420 Esta tabla ya tiene la fórmula incluida y solo colocamos los números a los cuales deseamos calcular el mcd. Paso 1: 86 Mod 46 = 40 bajo la letra c en nuestra tabla insertamos la fórmula de mod =mod(86,46) Paso 2: 46 Mod 40 = 6 Paso 3: 40 Mod 6 = 4 Paso 4: 6 Mod 4 = 2 Paso 5: 4 Mod 2 = 0 Por lo tanto el mcd(86, 46) = 2 Nota importante: Repetimos los pasos hasta que se obtenga 0 como resultado. En este caso fueron 5 pasos. Determine el mcd(45, 60)

El otro método es simplemente buscar en Excel bajo formulas (Math & Trig) la función GCD. 6.1.4 Números Primos Relativos Sean a, b ∈ , diferentes de cero, se dice que a, b son primos relativos si y solo si hay una solución entera de ax + by = 1; es decir, mcd(a, b) = 1 Ejemplo: Determine cuales son números primos relativos. 1. 4, 6, 9: son primos relativos debido a que el mcd(4, 6, 9) = 1

2. 64, 38, 76: ¿Serán primos relativos? Se recomiendan los siguientes enlaces para comprender más a fondo el tema de las sucesiones: • Modulo y mcd o https://www.youtube.com/watch?v=x6qFMSRpgpM • Números Primos o https://www.youtube.com/watch?v=AoHnxo9Qr6A ---------------------------------------------------------------------------- 6.2 Algoritmo de Euclides El matemático griego Euclides desarrollo un método para evitar el realizar tantas divisiones a la hora de buscar el mcd de dos enteros positivos. Cada dos pasos reducen a menos de la mitad sus valores. 6.2.1 Teorema Algoritmo de Euclides Sean a, b ∈ + entonces el algoritmo es el siguiente: a = qb + r1 para 0 ≤ r1 < b b = q1r1 + r2 para 0 ≤ r2 < b r1 = q2r2 + r3 para 0 ≤ r3 < r2 r2 = q3r3 + r4 para 0 ≤ r4 < r3 … rK-3 = qK – 2 * rK – 2 + rK – 1 para 0 ≤ rK – 1 < rK – 2 rK-2 = qK – 1 * rK – 1 + rK para 0 ≤ rK < rK – 1 La aplicación más útil de este proceso es para verificar si dos números tienen divisor común. Si rK = 0 y asumiendo rk – 1 ∈ 0 entonces, rK – 1 es el divisor común de a y b. Pero si rK es 1 entonces son números primos relativos. Ejemplo: Usando el algoritmo de Euclides, determine si 1275 y 270 tienen un divisor común.

Solución: 1275 = 4*270 + 195 270 = 1*195 + 75 195 = 2*75 + 45 75 = 1*45 + 30 45 = 1*30 + 15 30 = 2*15 + 0 Por lo tanto, el máximo común divisor es 15. 6.2.2 El mcd y el algoritmo de Euclides Sean a, b ∈  y c = a Mod b, entonces mcd(a, b) = mcd(b, c) ó mcd(a, b) = mcd(b, a Mod b). Según el teorema anterior, si rK = 0 y se asume rK – 1 ∈ 0 entonces, rK – 1 = mcd(a, b). Por lo tanto, es de gran beneficio para cuando se determina el mcd para dos o más números. Ejemplo: Calcule el mcd(1275, 270) utilizando el algoritmo de Euclides con la operación de modulo. Solución: 1275 Mod 270 = 195 270 Mod 195 = 75 195 Mod 75 = 45 75 Mod 45 = 30 45 Mod 30 = 15 30 Mod 15 = 0 Así que el mcd(1275, 270) = 15 6.2.3 Conjunto Zn Sea n ∈ +; el conjunto de los enteros no negativos menores que n, se denota Zn y se expresa: Zn = {0, 1, 2, 3, … n – 1} Ejemplo: Determine Z9 y Z41 Solución: Z9 = {0, 1, 2, 3, 4, 5, 6, 7, 8} Z41 = ¿?

6.2.4 Operaciones Modulares Sea n ∈ + y a, b ∈ ������. Las operaciones modulares + y * se conocen como suma modular y multiplicación modular respectivamente. Estarían expresadas así: a + b = (a + b) Mod n a * b = (a * b) Mod n Ejemplo: Determine para Z10 las operaciones indicadas 1. 5 + 5 = (5 + 5) Mod 10 = 0 2. 9 + 8 = _______________ 3. 5 * 4 = (5 * 4) Mod 10 = 0 4. 6 * 8 = _______________ En adición a la suma y multiplicación modular tenemos la división modular. Para poder entender la división modular veamos lo que es el Inverso Modular. Para calcular el inverso de a ∈ ������������ debe determinarse primero si existe. En efecto, podemos utilizar el algoritmo de Euclides definiendo que mcd(n, a) = 1. Veamos el procedimiento: Paso 1: Se aplica el algoritmo de Euclides, hasta que ri = 1. Si no obtenemos 1, no existe el inverso en Zn y ahí termina el proceso. Paso 2: Sustituimos varias veces los valores de ri obtenidos al lado derecho de la implicación en el paso anterior. Realice hasta que obtenga la expresión de la forma nx + ay = 1 para x, y ∈ ������������. Ejemplo: Halle el inverso de 8 en Z45. Solución: 45 = 5*8 + 5 → ������ = ������������ − ������ ∗ ������ 8 = 1*5 + 3 → ������ = ������ − ������ ∗ ������ 5 = 1*3 + 2 → ������ = ������ − ������ ∗ ������ 3 = 1*2 + 1 (8-1 existe, ya que terminamos en 1) → ������ = ������ − ������ ∗ ������ Entonces podemos expresar como 45x + 8y = 1. Por último, procedemos a sustituir en la última expresión obtenida al lado derecho, para determinar el valor entero positivo de x o de y. 1 = 3 – 1*2

= 3 – 1 (5 – 1 *3) ley de sustitución = - 1*5 + 2*3 ley distributiva y reducción de términos = - 1*5 + 2 (8 – 1*5) ley de sustitución = 2*8 – 3*5 ley distributiva y reducción de términos = 2*8 – 3(45 – 5*8) ley de sustitución = 45(- 3) + 8*17 ley distributiva y reducción de términos Con esto podemos ver que esta expresión tiene la forma 45x + 8y = 1, donde y = 17. Por lo tanto, 17 = 8-1 en Z45. Ahora podemos proceder con la división modular. Sea ������ ∈ ������ + y ������ ∈ ������������ un elemento invertible. Sea ������ ∈ ������������, podemos definir la división modular como a b-1 y se denota como Ø. Por lo tanto, la división modular existe en Zn siempre que exista b-1 en Zn. Ejemplo: Determine 18Ø5-1 en Z21 Solución: Primer paso: Verificar que 21 y 5 son números primos relativos. En efecto lo son. Segundo paso: Establecer la ecuación para determinar x e y 21x + 5y = 1 21(1) + 5(-4) = 1; pero -4 no es parte de Z21 Pero podemos usarlo para calcular el inverso: - 4 Mod 21 = 17 Por lo tanto, 5 – 1 = 17 en Z21 Así que, 18*17(Mod 21) = 12 6.2.5 Raíz Cuadrada en Zn Sea a ∈ ������������; se dice que la raíz cuadrada de a existe en Zn si existe un numero x ∈ ������������ tal que x2 = x*x = a. A diferencia del cálculo de la raíz cuadrada de un número entero, para un Zn es totalmente distinto y puede ser muy tedioso el procedimiento. Por lo tanto, trabajaremos con una función predeterminada en el programado MS Excel.

La función residuo nos dará la raíz para un Zn. Ejemplo: Determine para Z12 √9 6.2.6 Congruencia de Números Sean a, b ∈ ������ y n >0, podemos establecer: a ≡ b(Mod n) a Mod n = b Mod n Esto significa que “a es congruente con b módulo n si y solo si el módulo n es igual b módulo n.” Ejemplo: Determine si 25 y 16 son congruentes. Solución: 25 ≡ 16(Mod 9), debido a que 25(Mod 9) = 16(Mod 9) = 7 Por lo tanto, son congruentes. Teorema raíces cuadradas en Zn: Este teorema establece que podemos determinar las raíces cuadradas conociendo si hay congruencia. Veamos, sea n un numero primo tal que n ≡ 3(Mod 4). Si ������ ∈ ������n es un residuo cuadrático, entonces las raíces cuadradas de x en Zn son (±������(������+1)/4)������������������ ������ Ejemplo: Determine las raíces cuadradas de 9 en Z11 Solución: Como n = 11 es primo y 11 ≡ 3(Mod 4); en Z11 se obtiene (±9(11+1)/4 ������������������ 11) = ±9 ������������������ 11 = ±3

Por lo tanto, las raíces cuadradas de 9 en Z11 son +3 y -3; pero -3 no es elemento de Z11, entonces se complementa a 11; es decir, -3 + 11 = 8. Por consiguiente, las raíces cuadradas de 9 en Z11 son 3 y 8. 6.3 Conceptos de Criptografía La palabra Criptografía proviene del griego \"kryptos\" que significa oculto, y \"graphia\", que significa escritura, y su definición según el diccionario es \"Arte de escribir con clave secreta o de un modo enigmático\". La Criptografía es un conjunto de técnicas, que originalmente tratan sobre la protección o el ocultamiento de la información frente a observadores no autorizados. El ejemplo clásico de su uso fue por Julio Cesar (100 – 44 A.C.), enviaba mensajes secretos con clave en las que se cambiaban las letras por otra letra equivalente. Veamos: Recuperado de: https://daviticblog.wordpress.com/2017/03/14/cifrado-cesar/#jp-carousel-282 Este proceso se conoce como encriptación. De otra parte, el proceso llevado a cabo para descifrar el mensaje se conoce como desencriptación. La encriptación de Julio Cesar estaba representada por la función f que asignaba un entero no negativo x menor o igual que 25, es decir, f(x) = (x + 3) Mod 26. La función para descifrar o desencriptar esta basada en f-1(x) = (x – 3) Mod 26. En general un mensaje escrito solamente con letras se encripta con: f(x) = (x + a) Mod 26 y se desencripta con: f(x) = (x – a) Mod 26. Sea f(x) = (ax + b) Mod n con mcd (n, a) = 1. Entonces, g(y) = a-1(y – b) Mod n, donde a-1 es el invertible de a Mod n. Ejemplo: Encripta el mensaje “MEET YOU IN THE PARK” Solución: Usando el alfabeto de 26 letras:

ABCDE FGH I J K LMNOPQR S TUVWXY Z 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 12 4 4 19 24 14 20 8 13 19 7 4 15 0 17 10 Reemplazar cada numero en f(x) = (x + 3) Mod 26 15 7 7 22 1 17 23 11 16 22 10 7 18 3 20 13 Convertimos estos números en letras “PHHW BRX LQ WKH SDUN” Exploren que otros métodos se usan para encriptar y asegurar mensajes y claves.