Story Transcript
ÁLGEBRA: MATEMÁTICA DISCRETA Parte 2ª: Teoría de Números
Profesor: José-Miguel Pacheco Castelao Curso 2011-2012 ESCUELA DE INGENIERÍA INFORMÁTICA DE LA ULPGC
1
Los conjuntos numéricos de la Aritmética La Aritmética es la parte de las Matemáticas que estudia las propiedades y operaciones con números, en especial los Naturales y los Enteros:
` = {0,1, 2,3, 4,...} Z = {..., −4, −3, −2, −1, 0,1, 2,3, 4,...} Las operaciones aritméticas elementales posibles con los Naturales y los Enteros se recogen en la tabla siguiente. Cuando decimos que una operación no es posible queremos decir que en algún caso el resultado de la misma se halla fuera del conjunto en que trabajemos. La propiedad distributiva es la igualdad a(b+c) = ab+ac que relaciona el producto con la suma, Suma conmutativa
Resta
Producto conmutativo
División
Distributiva
`
Sí
No
Sí
No
Sí
Z
Sí
Sí
Sí
No
Sí
2
La ordenación de los Naturales y los Enteros Los números naturales poseen una ordenación intuitiva, de menor a mayor en el sentido ordinario de la frase. Dicha ordenación se prolonga a los números enteros de forma completamente natural:
` = {0 < 2 < 3 < 4 < ...} Z = {... < −4 < −3 < −2 < −1 < 0 < 2 < 3 < 4 < ...} Ambos órdenes son totales (dados dos números cualesquiera, siempre es posible decidir cuál es el mayor de ellos). Además, el orden de los números Naturales es bueno (cualquier familia de números naturales tiene un primer elemento). Sin embargo, el orden de los Enteros NO es bueno: p. ej., el conjunto de los números menores que -3 no tiene primer elemento, aunque sí tiene último. El tipo de orden de los Naturales se llama como −ω + ω (que no es igual á 0)
ω (omega pequeño), y el de los Enteros se escribe
Nótese que la suma de tipos ordinales no sigue las leyes habituales de la Aritmética. Los tipos ordinales son casos particulares de números transfinitos.
3
La “regla de los signos” La conocida regla de los signos puede obtenerse a partir de las operaciones realizables con los números enteros. En general, cualquier conjunto con dos operaciones asimilables a las de los números enteros se llama “anillo”, y esta regla es cierta en todo anillo.
Dado un elemento a ∈ ], el elemento − a se llamará "opuesto de a", y es aquel elemento que sumado con a da 0. La habitual expresión a − b es simplemente una abreviatura de a + (−b) [esto es, restar es "sumar el opuesto"]. Probemos primero que a × 0 = 0, cualquiera que sea a. En efecto. Como 0+0=0, podemos poner a × (0 + 0) = a × 0. Usando la propiedad distributiva tendremos que a × (0 + 0) = a × 0 + a × 0 será igual á a × 0, luego es obligado que a × 0 = 0. Regla de los signos: a × (−b) = −(a × b) Demostración: Escribimos 0 = a × 0 = a × (b + (−b)), cualquiera que sea b. Por tanto, a × b + a × (−b) = 0, luego a × (−b) es el opuesto de a × b. En otras palabras, a × (−b) = −(a × b). 4
Múltiplos y divisores Si n ∈ ], el conjunto de todos los números de la forma n × m, donde m ∈ Z, se llama "conjunto de los múltiplos de n". Se suele escribir n, ó n]. Cuando p ∈ nZ, diremos que n es divisor de p. El conjunto de los múltiplos de n es siempre infinito (excepto si n = 0), pero el de los divisores de n siempre es finito. Un número entero que no tenga divisores, a excepción del 1 y de él mismo, es un número primo. Los primeros primos son 2, 3, 5, 7,... y los primeros no primos -que se dicen "compuestos"-, son 4 , 6, 8, 9,.... Notemos que el único primo par es el 2. Hay dos resultados fundamentales acerca de los números primos: a) "El conjunto de los números primos es infinito" b) "Todo número entero se puede escribir como producto de un número finito de números primos" El resultado b) se conoce como "Teorema Fundamental de la Aritmética" 5
La “división con resto” Dados dos enteros positivos m y n, con m > n, entonces, o bien m es múltiplo de n, o no lo es. En el primer caso existirá otro entero p tal que m = n × p, mientras que en el segundo caso el número m se encontrará entre dos múltiplos consecutivos de n, esto es, habrá un número q tal que n × q < m < n × (q + 1). Este q recibe el nombre de cociente por defecto de la división de m por n, y r = m − n × q es el resto de la división. Es evidente, por su propia construcción, que 0 ≤ r < n : Se cumple la igualdad 0 = r cuando m es múltiplo de n. Por tanto ambos casos se pueden expresar en la forma siguiente:
Algoritmo de la división con resto (ejercicio: programarlo) Para cualquier par de números enteros m y n tales que m > n, es posible hallar otros dos enteros q y r tales que: 1) m = n × q + r 2) 0 ≤ r < n Además, q y r están determinados de manera única. 6
Hay infinitos números primos Este resultado es uno de los Teoremas más antiguos de las Matemáticas, y se conocen muchas demostraciones de él. Aparece en los “Elementos” de Euclides (Libro IX, Prop. 20), hacia 300 AC, cuya demostración presentaremos aquí. Se trata de una demostración constructiva: La idea consiste en probar que dado un número cualquiera de números primos, siempre es posible construir uno más.
Supongamos conocidos k números primos p1 , p2 , p3 , ..., pk . Construyamos el producto de todos ellos y añadámosle 1, con lo que obtendremos un número P: P = p1 × p2 × p3 × ... × pk + 1. Pues bien, este número, mayor que todos los anteriores, es también primo. Ello es cierto, pues da resto 1 al dividirlo por cualquiera de los primos originales, luego no tiene divisores. Observación: El número P no es el siguiente primo al último que tengamos. Por ejemplo, de 2, 3, 5 obtendríamos P = 31, mientras que el primo siguiente á 5 es 7.
7
Más sobre números primos La observación anterior nos muestra la dificultad de hallar números primos: No existe un método que permita el cálculo sistemático (p. ej. una ley de recurrencia o algo similar) de tales números, salvo el “cribado” de Eratóstenes: 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 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 …
El cribado consiste en ir eliminando los múltiplos de los sucesivos números, primos o no. Primero se borran los pares (gris) excepto el 2, luego los múltiplos de 3, que fue el primero no borrado, después los de 5 (el primer “superviviente” tras eliminar los de 3), los de 7 y así sucesivamente… En la figura se ve la tabla de números primos hasta el 100 (hay 25 de ellos, 26 si contamos el 1). La criba puede formalizarse fácilmente en un algoritmo para hallar los primos menores que cualquier entero dado n. 8
El Teorema Fundamental de la Aritmética (1) Este resultado muestra que los números primos son los elementos básicos para construir cualquier número entero. Podemos enunciarlo así: “Todo número entero puede escribirse como producto de números primos, que pueden repetirse, y esa descomposición es única, salvo el orden del producto, que puede ser cualquiera” Hay varias demostraciones disponibles, y vamos a presentar dos sobre la existencia de la descomposición. La parte de unicidad se deja como ejercicio. Demostración 1ª (bastante informal, pero rigurosa). Consideremos un entero cualquiera. Si es primo, ya está probado el teorema. Si no es primo, se podrá escribir como producto de dos números, divisores suyos. Si el primer divisor no fuera primo, hallaríamos dos divisores suyos. Si no, pasamos al segundo, sobre el cual repetimos el proceso, etc. etc. Este procedimiento se continuará hasta que termina obligatoriamente, pues el número original es finito. Por tanto, el teorema es cierto. Esta demostración puede implementarse como un algoritmo: Ejercicio.
9
El Teorema Fundamental de la Aritmética (2) (C. F. Gauss (1777-1855), Disquisitiones Arithmeticae ,1801) Demostración 2ª (por contradicción) Supongamos que hay algunos enteros positivos que NO se pueden descomponer en producto de primos. Entonces, debido a la buena ordenación de los números naturales, habrá uno que será el menor de todos ellos, llamémosle p. Éste no puede ser primo, pues entonces sería descomponible en producto de primos (con sólo un elemento, claro), lo que contradiría el ser el menor con la propiedad de no descomposición en producto de primos, así que es compuesto. Por tanto, tiene divisores. Éstos no pueden ser primos, pues en tal caso p no sería el menor de los números no descomponibles. Pero tampoco pueden ser descomponibles en primos, pues en tal caso lo sería también p. Por ello, la existencia de p es imposible, y el Teorema queda demostrado.
Observación importante sobre el “estilo” matemático: La “demostración por contradicción” se basa en la idea de que es imposible que algo tenga y no tenga simultáneamente una propiedad cualquiera. En el caso anterior, la propiedad es “ser el menor entero positivo tal que…”. De ahí obtendríamos que la hipótesis inicial de que NO ocurre algo debe ser desechada, de donde se sigue que lo contrario es cierto. Veremos al final del curso, en la parte de Lógica, más acerca de esta clase de demostraciones. 10
Aritmética “útil”: MCM y MCD a) Consideremos dos enteros positivos m y n, y sus respectivos conjuntos de múltiplos, nZ y m]. El conjunto n` ∩ m` ⊆ `, como subconjunto del conjunto bien ordenado `, tiene un primer elemento M (n, m). Éste es múltiplo de m y n y es el MENOR con esa propiedad: Es el "mínimo común múltiplo" (MCM) de n y m.
b) Consideremos los dos enteros positivos anteriores m y n, y sus respectivos conjuntos de divisores D(n) y D( m). El conjunto D(n) ∩ D(m) ⊆ ` es finito, luego tiene un último elemento d (n, m). Éste es divisor de m y n y es el MAYOR con esa propiedad: Es el "máximo común divisor" (MCD) de n y m.
c) Consideremos los dos enteros positivos anteriores m y n, y sus respectivos MCM y MCD, M ( n, m) y d ( n, m). Es fácil probar que M ( n, m) × d ( n, m) = n × m.
11
Cálculo del MCD y el MCM a partir del Teorema Fundamental Vamos a ilustrarlo con un ejemplo. Hallemos el MCD de 336 y 136: Número
Divisores
Número
Divisores
336
2
136
2
168
2
68
2
84
2
34
2
42
2
17
17
21
3
1
7
7
Descomponemos los números en factores primos. Para el MCD nos quedamos sólo con los factores comunes (en el menor número posible) y los multiplicamos. Para el MCM, los comunes (en el mayor número posible), y los no comunes, y los multiplicamos.
1
336
2
2
2
2
136
2
2
2
17
336
2
2
2
2
136
2
2
2
17
3
3
7
7
Términos comunes: tres veces 2, luego MCD (336, 136) = 8 Términos comunes (3 veces 2) y no comunes: (2, 3, 7, 17), luego MCM (336, 136) = 5712
12
El Algoritmo de Euclides (1) Este algoritmo provee un método sistemático para hallar el MCD de dos enteros sin necesidad de usar el Teorema Fundamental:
Sean dos números enteros positivos a > b. Usemos el algoritmo de la división para obtener q1 y r1 tales que a = bq1 + r1 con 0 ≤ r1 < b. Si r1 = 0 el algoritmo acaba, y el MCD de a y b es b. En caso contrario, apliquemos el algoritmo de la división á b y r1 , para hallar q2 y r2 tales que b = r1q2 + r2 con 0 ≤ r2 < r1. Si r2 = 0 el algoritmo acaba, y el MCD de a y b es r1 : En efecto, si r2 = 0, entonces a = bq1 + r1 = (r1q2 + r2 )r1 + r1 = r1 (q2 q1 + 1), esto es, r1 es divisor de a y de b y desde luego es el mayor posible. En caso contrario, continuemos el algoritmo de la división con r1 y r2 , para hallar q3 y r3 tales que r1 = r2 q3 + r3 con 0 ≤ r3 < r2 , etc, etc... El proceso acaba forzosamente con una división exacta, pues los números iniciales son enteros positivos y los que van apareciendo sucesivamente también lo son, cada vez menores. Por tanto, el último resto no nulo es el MCD de a y b. 13
El Algoritmo de Euclides (2)
a: cocientes restos
b
r1
r2
q1
q2
q3
r1
r2
r3
… … …
rn
rn +1
MCD
qn +1 qn + 2 rn +1
0
La ley de recurrencia para el Algoritmo de Euclides es:
rk = rk +1qk +2 + rk +2 r−1 = a r0 = b 14
El Teorema de Bézout (1) TEOREMA: "Sean dos enteros a y b, y sea d su MCD. Entonces existen otros dos enteros, r y s, tales que d = ar + bs". DEMOSTRACIÓN: Consideramos el conjunto K de todos los números enteros del tipo ax + by. Nos quedamos sólo con los positivos. Por la buena ordenación de `, existe uno que es el menor de todos ellos, llamémosle d * = ax * +by *. Vamos a ver que d * = MCD(a, b) : Si aplicamos el algoritmo de la división (p. ej. á a y d *), tendremos que : a = d * q + r , con r < d *, y operando sale que r = a − d * q = a − (ax * +by*)q = = a[(1 − x*)q ] + b(− y * q) = ax ** + by **. Esto nos dice que r ∈ K , pero como r < d *, y éste era el menor elemento de K , la única posibilidad es que r = 0. Luego d * es un divisor de a (y de b, claro). Sólo queda ver que es el mayor de los divisores comunes: Esto es fácil, pues si D fuera otro divisor común, entonces también dividiría a cualquier combinación del tipo ax + by, y en particular á d *. Luego D ≤ d *. Nota: Es claro que r = x * y s = y *. 15
El Teorema de Bézout (2) Los números concretos r y s que aparecen en el Teorema de Bézout se obtienen invirtiendo el Algoritmo de Euclides. Veámoslo con un ejemplo: Supongamos que el MCD(a, b) es r2 : Para este caso ⎧ a = bq1 + r1 ⎪ el algoritmo de Euclides será ⎨b = r1q2 + r2 ⎪r = r q +0 ⎩ 1 2 3 Despejemos r2 en la segunda ecuación: r2 = b − r1q2 , y sustituyamos en esta expresión el valor de r1 despejado de la primera ecuación: r2 = b − (a − bq1 )q2 . Así se llega a: r2 = − q2 a + (1 + q1q2 )b. Esto es: r = − q2 , s = 1 + q1q2 . Cuando el MCD de dos enteros es 1 (o sea, no tienen divisores comunes excepto el 1), decimos que tales enteros son primos entre sí. Aplicando el Teorema de Bézout a este caso se tiene la siguiente propiedad:
"Si a y b son primos entre sí, existen dos enteros r y s tales que ar + bs = 1" 16
Ecuaciones diofánticas elementales Se llama ecuaciones diofánticas a aquéllas cuyos coeficientes son enteros, tienen más de una incógnita y además se buscan soluciones enteras.
Ejemplos: 2x + 5 y = 32 es una ecuación diofántica lineal en dos variables, x 2 + y 2 − z 2 = 0 es una ecuación diofántica de segundo grado en tres variables. Las soluciones de una ecuación diofántica, si existen, son n-uplas de números enteros, siendo n el número de incógnitas. En la ecuación lineal del ejemplo anterior se ve fácilmente una solución, el par (1,6), pero tiene infinitas más. La ecuación de segundo grado del ejemplo también tiene infinitas soluciones, una es la terna (3,4,5). [Las soluciones de esta ecuación se llaman triples pitagóricos y representan las dimensiones de triángulos rectángulos con lados enteros]. Para resolver ecuaciones diofánticas lineales utilizaremos una combinación del Teorema de Bézout y del Algoritmo de Euclides.
17
La ecuación diofántica lineal en dos variables (1) Re solución: Partimos de ax + by = c. Lo primero es calcular el MCD de a y b, llamémosle d . A continuación, comprobemos si d es divisor del término independiente c. En caso negativo no hay solución. Supongamos que sí es divisor. Entonces podremos dividir toda la ecuación por d , y nos quedará Ax + By = C , donde A y B son primos entre sí, de forma que existen (Bézout) dos números enteros r y s tales que Ar + Bs = 1. Multiplicamos esta ecuación por C , y tendremos ACr + BCs = C. Multipliquemos de nuevo todo por d y recordando que dA = a, dB = b y dC = c: c c c c dACr + dBCs = dC ⇔ a ( r ) + b( s ) = c, de modo que x = r , y = s forman d d d d una solución de la ecuación diofántica. De hecho hay infinitas más, el ⎧ c b c a ⎫ conjunto ⎨( r + k , s − k ) ⎬ . En efecto: d g d g ⎩ ⎭ g∈{divisores comunes de a y b}, k∈Z c b c a b a a( r + k ) + b( s − k ) = c + a k − bk = c. d g d g g g 18
La ecuación diofántica lineal en dos variables (2): Un ejemplo Sea la ecuación 10 x + 15 y = 35. 1. El MCD de 10 y 15 es d = 5, que sí divide á 35. Luego hay soluciones. 2. Dividir todo por el MCD: 2 x + 3 y = 7. 3. Según Bézout: 2r + 3s = 1 ⇔ r = −1, s = 1, luego 2(−1) + 3(1) = 1. 4. Multiplicar todo por 7 y luego por d = 5: 10(−7) + 15(7) = 35. 5. Una solución particular será (−7, 7). ⎧ 15 10 ⎫ 6. Todas las soluciones: ⎨(−7 + k , 7 − k ) ⎬ g g ⎭ g∈{1,5}, k∈Z ⎩
k
…
-2
-1
0
1
2
3
…
Si g=5
…
(-13,11)
(-10,9)
(-7,7)
(-4,5)
(-1,3)
(2,1)
…
Si g=1
…
(-37,27) (-22,17)
(8,-3)
(23,-13) (38,-23
… 19
Aritmética Modular (1) Motivación Todos conocemos la aritmética modular en la vida diaria: Contamos las horas de 12 en 12 (a veces de 24 en 24). P.ej. a las 10 de la mañana decimos: Dentro de cuatro horas serán las 2, y nos parece natural que la suma de 10 y 4 sea 2. Así, sin darnos cuenta, estamos usando aritmética en módulo 12. Consideremos el conjunto de los números enteros positivos, y sea p un entero positivo cualquiera. Al aplicar el algoritmo de la división con p como divisor se pueden obtener p restos diferentes: {0,1,2,…,p-1}. Esto nos permite clasificar todos los números enteros de acuerdo con el resto que dejan al dividir por p. Si efectuamos operaciones permitidas con los enteros, como sumar y multiplicar, las operaciones se trasladan a los correspondientes restos, definiendo una aritmética de restos, de la siguiente manera:
Si a = pqa + ra y b = pqb + rb , entonces el resto de la suma de a y b al dividir por p es: ra + rb si esta cantidad es menor que p, y el resto de dividirla por p en caso de ser mayor. Lo mismo vale para el producto, cambiando suma por multiplicación. 20
Aritmética Modular (2) La aritmética módulo p queda totalmente determinada por las tablas de sumar y multiplicar para los p restos posibles {0,1,2,…,p-1}. Lo ilustramos con un ejemplo: La aritmética módulo 5 tiene las siguientes tablas: +
0
1
2
3
4
0
0
1
2
3
4
1
1
2
3
4
0
2
2
3
4
0
1
3
3
4
0
1
2
4
4
0
1
2
3
x
1
2
3
4
1
1
2
3
4
2
2
4
1
3
3
3
1
4
2
4
4
3
2
1
x
-x
1/x
0
0
---
1
4
1
2
3
3
3
2
2
4
1
4
En la tabla de sumar vemos que todo elemento x tiene su opuesto –x, entendiendo por opuesto aquel elemento que sumado con él dé 0. En la de multiplicar vemos que todo elemento x distinto de 0 tiene su inverso 1/x, entendiendo por inverso aquel elemento que multiplicado con él da 1. En otras palabras, en la aritmética módulo 5 son posibles las cuatro operaciones elementales de la Aritmética. Se dice que tenemos un cuerpo numérico. 21
Aritmética Modular (3)
Notación: En lugar de la expresión "en la aritmética módulo p", diremos simplemente "en ] p ".
En aritmética modular son posibles las operaciones de sumar y restar, cualquiera que sea el módulo p. Lo mismo es cierto para el producto, pero no para la división. Consideremos el módulo 6 y construyamos la tabla de multiplicar, apuntando los inversos: x
1
2
3
4
5
x
1/x
1
1
2
3
4
5
1
1
2
2
4
0
2
4
2
---
3
3
0
3
0
3
3
---
4
4
2
0
4
2
4
---
5
5
4
3
2
1
5
5
Observamos que en la aritmética módulo 6 existen elementos que no poseen inverso: Son el 2, 3 y 4. Estos números (en módulo 6, claro está) se llaman “divisores de 0”. Si nos fijamos, o son divisores del módulo (2 y 3) o contienen alguno de sus divisores (el 4). Por tanto, si el módulo no es primo siempre habrá divisores de cero, que no tienen inverso, y la operación de dividir no será posible. 22
Aritmética Modular (4) Si del conjunto {0,1,2,…,p-1} eliminamos los divisores de 0, obtendremos el llamado conjunto reducido de restos módulo p . Por ejemplo, para p = 6 el conjunto reducido es el {1,5}. Observamos que está formado por los elementos de {0,1,2,…,p-1} que son primos con 6. Esta situación es válida para cualquier módulo p.
El cardinal del conjunto reducido de restos módulo p se escribe ϕ ( p), y se conoce como el indicador (o la función) de Euler. Cuando p es primo, ϕ ( p ) = p − 1. DEFINICIONES Y NOTACIÓN Cuando dos números enteros a y b dan el mismo resto al dividir por el módulo p se les llama "congruentes módulo p", y lo escribimos a ≡ b ( p). Esta expresión es una "congruencia módulo p". Dadas dos congruencias a ≡ b ( p) y c ≡ d ( p),se pueden sumar, restar o multiplicar término a término para obtener las nuevas congruencias (a ± c) ≡ (b ± d ) ( p ) y ac ≡ bd ( p ). La división es posible sólo si no hay divisores de 0.
En realidad, las congruencias y las operaciones con ellas son exactamente lo mismo que las tablas definidoras de la aritmética módulo p. 23
Resultados matemáticos sobre congruencias (Teorema “pequeño” de Fermat) Supongamos que p es primo. Entonces en ] p se cumple que: "si a j denota los elementos del conjunto {1,2,3,...,p − 1} , entonces, si ak es uno cualquiera de ellos, todos los productos ak a j son distintos entre sí" En efecto, si hubiera dos productos iguales, ak a j y ak ai , su diferencia ak (a j − ai ) sería 0. De ahí deducimos que necesariamente es a j = ai , pues en caso contrario ak y (a j − ai ) serían divisores de 0, lo cual es imposible por ser p primo. Una consecuencia directa, cuya demostración se verá en la página siguiente, es que la potencia (p − 1)-ésima de cualquier a ∈ ] p es 1. Si escribimos este resultado en forma de congruencia tendremos:
a p −1 ≡ 1( p) Se conoce este resultado como "Teorema pequeño de Fermat"
24
La demostración citada en la página anterior Veamos un resultado previo: "Si p es primo, la factorial ( p − 1)! es congruente con − 1 módulo p ". En efecto, ( p − 1)! = 1× 2 × 3 × ... × ( p − 1). Si pasamos este producto a módulo p, observamos que 1 es inverso de sí mismo, y p − 1 también lo es. Por tanto, los números entre 2 y p − 2 se cancelan entre sí dos á dos. Luego ( p − 1)! ≡ p − 1 ≡ −1 ( p ). Sea ahora un elemento cualquiera a ∈ ] p y formemos el producto siguiente: (1× a) × (2 × a ) × (3 × a ) × ... × (( p − 1)a ). Por un lado, este producto vale a p −1 ( p − 1)!, y por otro es congruente con ( p − 1)! Esto último es fácil de ver, pues los productos de a por los demás elementos de Z p son, de nuevo, los mismos elementos de Z p en otro orden, según lo visto en la página anterior. Por tanto, a p −1 ( p − 1)! ≡ (p − 1)! ( p). Multiplicando esta congruencia por p − 1 obtenemos la congruencia de Fermat, a p −1 ≡ 1 ( p ). NOTA 1: (p − 1) es inverso de sí mismo en ] p , pues (p − 1)(p − 1) = p( p − 2) + 1 ≡ 1 ( p ). NOTA 2: La expresión ( p − 1)! ≡ −1 ( p) se llama "congruencia de Wilson". 25
Resultados matemáticos sobre congruencias (Teorema de Euler)
Supongamos ahora que p no es primo. Entonces en ] p se tiene la siguiente propiedad: "Denotemos por a j los elementos del conjunto reducido de restos módulo p. Su número es ϕ ( p ). Si ak es uno cualquiera, todos los productos ak a j son distintos entre sí" En efecto, si hubiera dos productos iguales, ak a j y ak ai , su diferencia ak (a j − ai ) sería 0. De ahí deducimos que necesariamente es a j = ai , pues en caso contrario ak sería divisor de 0, lo cual es imposible por pertenecer al conjunto reducido (obsérvese que a j − ai no tiene por qué pertenecer al conjunto reducido). Una consecuencia directa, análoga a la congruencia de Fermat es que se tiene aϕ ( p ) = 1. En forma de congruencia queda:
aϕ ( p ) ≡ 1( p) Se conoce este resultado como "Teorema de Euler"
26
Resultados matemáticos sobre congruencias (Teorema chino del resto)
Supongamos el problema de "hallar todas las soluciones del siguiente sistema de congruencias cuyos módulos son primos entre sí dos á dos: x ≡ r1 ( p1 ), x ≡ r2 ( p2 ), ...., x ≡ rk ( pk ); MCD( pi , p j ) = 1 para todo par i, j ". Si construimos el producto P = p1 p2 ... pk y lo vamos dividiendo por los sucesivos p j obtendremos una familia de números Pj tales que MCD(p j ,Pj ) =1 para todo j. Ello significa que, en la aritmética módulo p j , Pj tiene inverso multiplicativo, k
llamémosle I j . Ahora, consideremos el número entero X = ∑ rj Pj I j y pasémoslo j =1
a ] P . El número x así hallado es una solución del sistema. En efecto, por el algoritmo de la división sabemos que existen números Q y x k
tales que x = X − PQ = ∑ rj Pj I j − PQ. Si dividimos esta expresión por los sucesivos j =1
p j obtenemos exactamente los restos rj . EJEMPLO: x ≡ 5 (7), x ≡ 3 (11), x ≡ 8 (13); 7 × 11 × 130 = P = 1001; P1 = 1001/ 7 = 143, P2 = 1001/11 = 91, P3 = 1001/13 = 77; P1 = 143 ≡ 3 (7) ⇒ I1 = 5, P2 = 91 ≡ 4 (11) ⇒ I 2 = 3, P3 = 77 ≡ 12 (13) ⇒ I 3 = 12; 3
X = ∑ rj Pj I j = 5 × (143 × 5) + 3 × (91× 4) + 8 × (77 × 12) = 12059; j =1
x = Resto de dividir 12059 entre 1001 = 47 (una solución particular) Todas las soluciones: Todos los números congruentes con 47 módulo 1001.
27
Aplicaciones (I) Cuando p es primo, se pueden estudiar y resolver sistemas de ecuaciones lineales con varias incógnitas igual que en el caso habitual estudiado en cursos anteriores. Véamoslo con un ejemplo: ⎧3 x + 4 y = 5 Estudiar y resolver en ] 7 , si fuera posible, el sistema ⎨ ⎩ 2x + 5 y = 1 Como 7 es primo, podemos proceder por cualquier método. El determinante de la matriz de coeficientes es 3 × 5 − 4 × 2 = 7 ≡ 0 (7), luego su rango es 1. Añadiendo la columna de términos independientes vemos que también la ampliada es de rango 1. Por tanto a) hay soluciones (rangos iguales), y b) hay más de una (rango < nº incógnitas). Si nos quedamos con la 1ª ecuación, despejamos x, consideramos y como parámetro, 5 − 4y tenemos las posibles soluciones (sólo son 7, no infinitas): x = = 5(5 − 4 y ) : 3
y
0
1
2
3
4
5
6
x
4
5
6
0
1
2
3
NOTA: Aunque p no sea primo, hay casos en que también pueden resolverse sistemas… 28
Aplicaciones (II) Dígitos de control En la actualidad, cualquier objeto suele estar codificado mediante una serie de números que reflejan algunas propiedades, p. ej, fabricante, modelo, precio… Es fácil cometer errores al transcribir una y otra vez los códigos, y por ello se introducen a veces unos números suplementarios llamados “dígitos de control”, para comprobar que la copia no tiene errores. Estos números se calculan mediante algoritmos sencillos de aritmética modular aplicados al código original. Para ilustrarlo consideremos algunos ejemplos. En España el DNI es un código de 8 cifras, y el dígito de control es una letra mayúscula, distinta de I,Ñ,O,U. Por tanto, hay 23 letras disponibles. El algoritmo de cálculo de la letra es una combinación del algoritmo de la división y una permutación fija de los restos. Es así: Se obtiene el resto de la división del número del DNI por 23, y se toma la letra de acuerdo con la siguiente tabla: resto
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
letra
T
R
W
A
G
M
Y
F
P
D
X
B
N
J
Z
S
Q
V
H
L
C
K
E
Desde luego, ahora habrá que probar algún TEOREMA para ver que hemos hecho algo positivo… 29
Aplicaciones (III)
Algunos teoremas sobre dígitos de control.
Al conjunto DNI+letra se le llama NIF. Tenemos un primer resultado interesante: “Dados dos NIFs que tengan la misma letra, es imposible que sólo difieran en uno de los números”. Dicho de otro modo, si equivocamos una cifra, saltará el aviso de error porque la letra también cambiará. 7
7
En efecto, escribamos los números en la forma ∑ An × 10 y ∑ Bn × 10n , y sea k el lugar en n
n=0
n=0
que difieren ambos. Como los dos llevan la misma letra, su diferencia ha de ser múltiplo de 23. Pero si los restamos, lo que queda es ( Ak − Bk )10k , que nunca puede ser múltiplo de 23, pues 23 no divide a ninguna potencia de 10 y tampoco a la diferencia de números entre 0 y 9. Luego han de diferir en más de un número.
Otro resultado que justifica la existencia del dígito de control: “Si al teclear el DNI se permutan dos cifras, la letra variará (y tendremos un aviso de error)” Sean i y j las dos posiciones cambiadas al teclear, siendo i > j el orden correcto. Si no cambiara la letra, la diferencia entre el número correcto y el equivocado sería múltiplo de 23. Pero la diferencia es ( Ai − Aj )10i + ( Aj − Ai )10 j , que por el mismo argumento del teorema anterior no es divisible por 23. 30
Aplicaciones (IV)
Otro ejemplo de dígito de control
El European Article Number (EAN-13) es un código de 13 cifras usado habitualmente para identificar productos de cualquier clase, que suele presentarse en forma de código de barras para su lectura automática. Las doce primeras son el código en sí, y la última es el dígito de control. El algoritmo es diferente al del DNI, por tanto los teoremas correspondientes han de ser probados de nuevo: ejercicio. En este caso, el algoritmo comienza sumando los números del código a partir de la izquierda, pero multiplicando los de posición par por 3. Tras ello, la última cifra b del número obtenido define el código de control así:
10 − b. Si b = 0, éste es el dígito. Código:
3
0
3
4
3
2
5
2
0
0
2
9
D.C.:
3
Multiplicar por
1
3
1
3
1
3
1
3
1
3
1
3
SUMA:
57
31
Aplicaciones (V) Criterios de divisibilidad Al descomponer un número entero en factores primos se plantea si existirán criterios rápidos para comprobar si es divisible por los sucesivos primos. Aunque éste es un problema de poco interés práctico, es interesante ver que existe una manera sistemática de obtener todos los criterios de divisibilidad: r
Sea m un número entero positivo cualquiera escrito en la forma ∑ An × 10n , y sea n=0
p un número primo. El resto de la división de m por p se halla fácilmente, pues basta con calcular los restos de las divisiones de cada An × 10n , y tras sumarlos pasar a Z p . Pero el resto de An ×10n es el producto del resto de An por el de 10n , que pasaremos á ] p . Esto es, m es divisible por p equivale a decir que: r
∑ [(resto de A ) × (resto de 10 )] ≡ 0 ( p) n
n=0
n
Los restos de las potencias 10n se llaman "restos potenciales módulo p"
Nota: para p>10, los restos de los coeficientes son ellos mismos…
32
Aplicaciones (VI) Obtención de criterios de divisibilidad… r
∑ A ×10 . Todos los restos potenciales son nulos, excepto para n = 0,
Sea p = 2, y sea m
n
n
n =0
r
que vale 1. Así pues ,
∑ [(resto de A ) × (resto de 10 )] ≡ 0 (2) se reduce a que n
n
n=0
A0 ≡ 0 (2), que es la conocida regla "m es divisible por 2 si acaba en 0 ó cifra par". Cuando p = 3, los restos potenciales son todos 1, luego la regla para dividir por 3 r
es
r
∑ [(resto de A ) × (resto de 10 )] = ∑ (resto de A ) ≡ 0 (3), o sea, "si sumamos n
n =0
n
n=0
n
los
números representativos de las cifras (o sus restos módulo 3) y sale múltiplo de 3..." El caso p = 5 presenta todos los restos potenciales nulos excepto para n = 0, luego la suma se reduce á A0 ≡ 0 (5), que da la conocida regla "m es divisible por 5 si acaba en 0 ó 5" El caso p = 7 es más complicado, pues los restos son (en orden creciente de n): 1,3, 2, 6, 4,5,1,3, 2, 6, 4,5,..., ó también 1,3, 2, −1, −3, −2,1,3, 2, −1, −3, −2,... si lo ponemos en Z 7 . En este caso la regla dirá: "El número de las unidades, más el triple del de las decenas, más el doble del de las centenas, menos el de los millares, menos el triple del de las decenas de millar, etc etc, ha de ser múltiplo de 7" 33
Aplicaciones (VII) Algo sobre mensajes cifrados El Código de César es el método más simple de enviar un mensaje cifrado. Para ello, una vez escrito el mensaje, se sustituye cada letra por la que ocupe k lugares más allá en el alfabeto, que supondremos de 26 letras. Cuando se sobrepase la letra Z, se vuelve a la letra A. Por tanto, el cifrado consiste en sumar k módulo 26. El descifrado, por tanto, será restar k módulo 26. Ejemplo: Con k=2, la frase hoy compro zapatos se cifra como jqae qort qbcr cvqu (habitualmente se omiten los espacios y luego se distribuyen las letras cifradas en grupos iguales, en este caso, de cuatro elementos). Si el receptor conoce la clave secreta k=2, el descifrado es sencillo. Si no, deberá emplear un tiempo en hallarla antes de poder leer el mensaje. La idea básica de todo cifrado consiste en hacer que un hipotético receptor no autorizado, p. ej. un espía, no pueda “desencriptarlo” o “romperlo” en un tiempo razonable. El código de César era difícil de romper cuando casi nadie sabía leer y escribir y la Aritmética era una ciencia al alcance de muy pocos. Hoy día es una curiosidad históricomatemática. Por supuesto, hay una enorme cantidad de métodos de cifrado, y la ciencia que los estudia se llama Criptografía. 34
Aplicaciones (VIII) Más sobre mensajes cifrados El Código RSA es el método más utilizado actualmente para el tráfico de información. También se basa en propiedades de la aritmética modular, pero además se diferencia del sistema de César en que es un sistema de clave pública, no secreta. Ello significa que cualquiera puede enviar un mensaje cifrado al receptor, pues éste hace público cómo cifrarlo. Sin embargo, sólo él sabe cómo descifrarlo. Veamos cómo funciona: El receptor elige dos números primos grandes, P y Q, construye su producto n = PQ, y hace público este número. Calcula la función de Euler ϕ ( N ) = ϕ ( PQ ) = ( P − 1)(Q − 1) y elige un número e en Zϕ (N) , siendo e un elemento del conjunto reducido. También hace público este número, de modo que el par ( N , e) es la "clave pública" de cifrado. Como e pertenece al conjunto reducido, posee un inverso d en Zϕ (N) , que será la "clave privada" de descifrado, que sólo conoce el receptor. Para mandar un mensaje x al receptor, el emisor calcula x e módulo N , y envía el resultado al receptor. Una vez recibido, el mensaje x e se descifra haciendo ( x e ) = x ed = x en ] N . El resultado se deduce d
de que ed ≡ 1 (ϕ ( N )), por aplicación del Teorema de Euler.
NOTA: RSA se considera seguro porque aunque se conozca N, la obtención de P y Q, a pesar de ser teóricamente posible, consume tal cantidad de tiempo de ordenador que carece de sentido su cálculo: P y Q tienen cada uno más de cien cifras en su expresión en base 10… 35
Apéndice: Sobre el tiempo de ejecución de un algoritmo Hemos visto que el objetivo de la Criptografía es dificultar el descifrado de mensajes, y que la dificultad se mide mediante el tiempo necesario para encontrar la clave. Si ésta se busca mediante algoritmos informáticos, se hará necesario estudiar cuánto tiempo tarda un algoritmo en ejecutarse. El tiempo de ejecución de un algoritmo depende de varios factores, pero esencialmente del tamaño de los datos de entrada. Por ejemplo, para sumar n números hay que hacer n operaciones (sumas). Se trata de un algoritmo lineal. Para ordenar n números desordenados es necesario efectuar (en el peor de los casos, claro) nxn comparaciones, y algunas operaciones más (colocar y/o intercambiar): Se trata de un algoritmo cuadrático. Imaginemos un ordenador que funciona a 1megaflop/s (1 millón de instrucciones por segundo). Entonces, para un millón de datos numéricos tendríamos esta tabla: Operación
Nº de instrucciones
Tiempo de ejecución
Sumarlos
1.000.000
1 segundo
Ordenarlos
1.000.000.000.000
unos 11 días
NOTA: Si se trabaja con números de 100 cifras, o más, se entiende la seguridad de RSA… 36