Download Document

ÁLGEBRA:
MATEMÁTICA DISCRETA
Parte 2ª: Teoría de Números
Profesor: José-Miguel Pacheco Castelao
Curso 2012-2013
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.
Nótese que la otra posible distributiva, a+(bc) = (a+b)(a+c), no es válida en general.
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 , esto es, 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 , o
sea, cualquier conjunto de números naturales posee 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]. 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 (excepto si n = 0).
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 primo siguiente al último que tomamos. Por
ejemplo, de 2, 3 y 5 obtendríamos P = 31, mientras que el primo siguiente al 5 es el 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, o Aritmética Modular, 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 o bien ra + rb si esta cantidad es menor que p, o 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 bien son divisores del módulo (2 y 3) o contienen a 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 en general.
22
Aritmética Modular (4)
Si del conjunto {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 lo componen los elementos de {1,2,…,p-1} que son primos con 6.
Si el módulo fuera primo, el conjunto reducido coincide con {1,2,…,p-1}.
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 un 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:
"sean a j denota los elementos del conjunto {1,2,3,...,p − 1} y sea ak uno
cualquiera de ellos fijo. Entonces, los productos ak a j son todos distintos"
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, en el `producto inidcado 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 sobre congruencias: el “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 a dicho conjunto).
Una consecuencia directa, análoga a la congruencia de Fermat es que aϕ ( p ) = 1.
En forma de congruencia queda:
aϕ ( p ) ≡ 1( p)
Se conoce este resultado como "Teorema de Euler"
26
Resultados sobre congruencias: el “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 ( p 2 ), ...., x ≡ rk ( p k ); M CD ( p i , p j ) = 1 para todo par i , j ".
Si construimos el producto P = p1 p 2 ... p k y lo vamos dividiendo por los sucesivos
p j obtendremos una familia de números Pj tales que M CD( p j ,Pj ) =1 para todo j .
Ello significa que, en la aritmética módulo p j , Pj tiene inverso multiplicativo,
llamémosle I j . Ahora, consideremos el número entero X =
k
∑r PI
j =1
j
j
j
y pasémoslo
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
tales que x = X − PQ =
k
∑r PI
j =1
j
j
j
− PQ . Si dividimos esta expresión por los sucesivos
p j obtenemos exactamente los restos r j .
EJEM PLO:
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) ⇒ I 1 = 5, P2 = 91 ≡ 4 (11) ⇒ I 2 = 3, P3 = 77 ≡ 12 (13) ⇒ I 3 = 12;
X =
3
∑r PI
j =1
j
j
j
= 5 × (143 × 5) + 3 × (91 × 4) + 8 × (77 × 12) = 12059;
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 como 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, 1
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 de 10, 10n , se llaman "restos potenciales módulo p"
Nota: para p>10, los restos de los coeficientes son ellos mismos…
32
Aplicaciones (VI) Criterios de divisibilidad, 2
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