Matemática Discreta: Tema 4 Teoría de Números. Aritmética Finita y Modular
Matemática Discreta: Tema 4 Teoría de Números. Aritmética Finita y Modular
Matemática Discreta: Tema 4 Teoría de Números. Aritmética Finita y Modular
TEMA 4
Teoría de números. Aritmética finita y modular
Objetivos
Introducción.
1 División entera y divisibilidad.
2 Algoritmo de la numeración.
3 Números primos.
4 Máximo común divisor y mínimo común múltiplo.
5 Congruencia. Aritmética modular.
6 Aplicaciones de la teoría de números.
𝐛𝐛
Dicho c = 𝐚𝐚
si existe, es único.
Ejercicio:
Demuestra que cada una de las partes del teorema 1 son verdaderas.
-3d -2d -d 0 d 2d 3d
c = a/d → cd = a
r = a – cd r’ = (c + 1) d – a = cd + d – a = d - r
Ejercicios:
1. ¿Divide 17 a los números 68, 84, 357, 1001?
2. Demuestra que si a|b y b|a, donde a y b son enteros, entonces
a = b o a = -b.
3. Demuestra que si a, b y c son enteros tales que ac|bc y c ≠ 0,
entonces a|b.
Ejemplos:
• En base 2 (binario): (101011111)2.
• En base 8 (octal): (537)8.
• En base 10 (decimal): (351)10.
• En base 16 (hexadecimal): (15F)16.
(101011111)2 = 1·28 + 0·27 + 1·26 + 0·25 + 1·24 + 1·23 + 1·22 + 1·21 + 1·20 = 351
109 / 2 = 54 r0 = 1 109 = 2 ∗ 54 + 1 20
54 / 2 = 27 r1 = 0 54 = 2 ∗ 27 + 0 21
27 / 2 = 13 r2 = 1 27 = 2 ∗ 13 + 1 22
13 / 2 = 6 r3 = 1 13 = 2 ∗ 6 + 1 23
6 /2= 3 r4 = 0 6 = 2∗ 3 +0 24
3 /2= 1 r5 = 1 3 = 2∗ 1 +1 25
1 /2= 0 r6 = 1 1 = 2∗ 0 +1 26
(109)10 = (1101101)2
Las conversiones entre expresiones binarias y hexadecimales son muy
sencillas porque cada dígito hexadecimal corresponde a un bloque de cuatro
dígitos binarios. Así, añadiendo un cero por la izquierda para completar el
segundo bloque, tenemos que: (1101101)2 = (0110 1101)2 = (6D)16 = 109.
Tema 4. Teoría de números. Aritmética finita y modular 24
2. Algoritmo de la numeración
Ejercicios:
1. Convierte los siguientes enteros de notación decimal a notación
binaria y viceversa:
a) 231 a) 11100111
b) 4532 b) 1 0001 1011 0100
c) 11 111 c) 31
d) 10 0000 0001 d) 513
2. Convierte los siguientes enteros de notación hexadecimal a
notación binaria y viceversa:
a) 80E a) 1000 0000 1110
b) 135AB b) 1 0011 0101 1010 1011
c) ABBA c) 1010 1011 1011 1010
d) DEFACED d) 1101 1110 1111 1010 1100 1110 1101
e) 1011 0111 1011 e) (B7B)16
Los primeros números primos 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, 97, …
Ejemplos:
7000
7000 = 23 · 53 · 7
6936
6936 = 23 · 3 · 172
Ejercicios:
1. Obtén la descomposición en factores primos de cada uno de estos
enteros:
a) 88 a) 23 · 11
b) 126 b) 2 · 32 · 7
c) 729 c) 36
2. Demuestra que log 2 3 es un número irracional. Recuerda que un
número irracional es un número real que no se puede escribir
como el cociente de dos enteros.
3. Determina si los enteros de cada uno de estos conjuntos son
primos relativos dos a dos:
a) 11, 15, 19 a) Sí.
b) 14, 17, 85 b) No.
c) 12, 17, 31, 37 c) Sí.
d) 7, 8, 9, 11 d) Sí.
Tema 4. Teoría de números. Aritmética finita y modular 29
4. Máximo común divisor y mínimo común múltiplo
126 = 2 · 32 · 7
108 = 22 · 33
Ejercicios:
1. ¿Cuál es el mcd y el mcm de cada uno de estos pares de enteros?
a) 22 · 33 · 55 , 25 · 33 · 52
b) 17 , 1717
c) 41 · 43 · 53 , 41 · 43 · 53
a) mcd = 22 · 33 · 52 mcm = 25 · 33 · 55
b) mcd = 17 mcm = 1717
c) mcd = 41 · 43 · 53 mcm = 41 · 43 · 53
2. Comprueba que ab = mcd (a, b) · mcm (a, b) en los ejemplos
anteriores?
3. Si el producto de dos enteros es 273852711 y su máximo común
divisor es 23345, ¿cuál es su mínimo común múltiplo?
ab = mcd (a, b) · mcm (a, b) → mcm = 24 34 5 711
Tema 4. Teoría de números. Aritmética finita y modular 33
4.1 Algoritmo de Euclides
El algoritmo de Euclides es un método para el cálculo del mcd de dos
números. Fue desarrollado por el matemático de la Grecia clásica,
Euclides. Se basa en el siguiente resultado sobre el máximo común
divisor y el algoritmo de la división entera:
Ejercicios:
1. Usa el algoritmo de Euclides para calcular:
a) mcd (12, 18) a) 6
b) mcd (111, 201) b) 3
c) mcd (1001, 1331) c) 11
d) mcd (12345, 54321) d) 3
e) mcd (1000, 5040) e) 40
f) mcd (9888, 6060) f) 12
2. Expresa el máximo común divisor de cada uno de estos pares de enteros
como combinación lineal de ellos (teorema de Bézout):
a) 10, 11 a) 1 = (-1) · 10 + 1 · 11
b) 21, 44 b) 1 = 21 · 21 + (-10) · 44
c) 36, 48 c) 12 = (-1) · 36 + 1 · 48
d) 34, 55 d) 1 = (-21) · 34 + 13 · 55
e) 213, 117 e) 3 = 11 · 213 + (-20) · 117
f) 0, 223 f) 223 = 1 · 0 + 1 · 223
Si dividimos 25 entre 7:
25 = 7·3 + 4
Ejemplo:
𝐚𝐚−𝐛𝐛
También podemos expresarlo como: 𝐦𝐦 = k, siendo k un número entero.
Ejemplos:
x = a + mk, con k ∈ Z
Si k = -1, entonces x = 6 Si k = 0, x = 11
Si k = -2, entonces x = 1 Si k = 1, x = 16
Si k = -3, entonces x = -4 Si k = 2, x = 21
Ejercicios:
1. Sea m un entero positivo. Demuestra que a ≡ b (mod m) si
a mod m = b mod m.
2. Evalúa las siguientes expresiones:
a) 13 mod 3 a) 1
b) -97 mod 11 b) 2
c) 155 mod 19 c) 3
d) -221 mod 23 d) 9
3. Analiza si cada uno de estos enteros es o no congruente con 5
módulo 17:
a) 80 a) No.
b) 103 b) No.
c) -29 c) Sí.
d) -122 d) No.
Para m = 4:
1/4 r = 1; 5/4 r = 1;
2/4 r = 2; 6/4 r = 2;
3/4 r = 3; 7/4 r = 3…
17 ≡ 10 (mod 7),
Una clase de restos consta de todos los enteros con el mismo resto
cuando se dividen entre m.
Ejemplo:
x = a ∈ Z ∶ a ≡ x (mod m)
18 ≡5 3 y 77 ≡5 2
Hay que tener cuidado al trabajar con las congruencias, pues algunas
propiedades que podemos esperar que sean ciertas, no son válidas. Por
ejemplo:
Ejemplo:
a = 4.982.744 a mod 5 = 4
b = 16.297.478 b mod 5 = 3
a + b = 21.280.222 (a + b) mod 5 = 7 mod 5 = 2
Tema 4. Teoría de números. Aritmética finita y modular 64
5.3 Aritmética modular o de congruencia
[2]+[3] = [5], [4]+[5] = [9] = [3], [2]·[2] = [4], [2]·[5] = [10] = [4]
+2 0 1 •2 0 1
0 0 1 0 0 0
1 1 0 1 0 1
+5 0 1 2 3 4 •5
0 1 2 3 4
0 0 1 2 3 4 0 0 0 0 0 0
1 1 2 3 4 0 1 0 1 2 3 4
2 2 3 4 0 1 2 0 2 4 1 3
3 3 4 0 1 2 3 0 3 1 4 2
4 4 0 1 2 3 4 0 4 3 2 1
Para encontrar los divisores de [0], habrá que buscar los valores de a
mayores que 1 y menores que m, es decir, 𝟏𝟏 < 𝐚𝐚 ≤ 𝐦𝐦 − 𝟏𝟏, tales que
mcd (a, m) ≠ 1.
3 = … , −15, −9, −3, 3, 9, 15, 21 … 4 = … , −14, −8, −2, 4, 10, 16, 22 … 5 = … , −13, −7, −1, 5, 11, 17, 23 …
0 = … , −18, −12, −6, 0, 6, 12, 18 … 1 = … , −17, −11, −5, 1, 7, 13, 19 … 2 = … , −16, −10, −4, 2, 8, 14, 20 …
3 = … , −15, −9, −3, 3, 9, 15, 21 … 4 = … , −14, −8, −2, 4, 10, 16, 22 … 5 = … , −13, −7, −1, 5, 11, 17, 23 …
En el caso de que a y m sean primos entre sí, mcd (a, m) =1, podemos
apoyarnos en el concepto de inverso para la resolución de estas
congruencias, teniendo en cuenta el siguiente teorema.
Demostración:
Según el Teorema de Bézout, como mcd (a, m) = 1, hay dos enteros s y t
tales que: sa + tm = 1.
x ≡ 20 (mod 7)
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)
Siendo:
• Mk = m / mk
• Mkyk ≡ 1 (mod mk), es decir, yk es inverso de Mk mod mk.
Resolver:
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)
x ≡ 2 (mod 3) → x = 3t + 2 [1]
→ t = 5s + 2
Ejercicios:
1. Calcula todas las soluciones del sistema de congruencias:
x ≡ 2 (mod 3)
x ≡ 1 (mod 4) Solución: x = 53 + 60k
x ≡ 3 (mod 5)
Por ejemplo, cuando m = 111, el fichero del estudiante con DNI número
064212848 se asigna a la posición de memoria 14, ya que:
Ejercicio:
1. ¿Qué posiciones de memoria asigna la función de dispersión
h(k) = k mod 101 a las fichas de los estudiantes con los números
de DNI siguientes?
a) 104578690 a) 58
b) 432222187 b) 60
c) 37201919 c) 84
d) 501338753 d) 3
Ejercicio:
1. ¿Qué sucesión de números pseudoaleatorios se genera utilizando el
generador multiplicativo puro xn+1 = 3xn mod 11 con la semilla x0 = 2?
x1 = 3x0 mod 11 = 3·2 mod 11 = 6 mod 11 = 6
x2 = 3x1 mod 11 = 3·6 mod 11 = 18 mod 11 = 7
x3 = 3x2 mod 11 = 3·7 mod 11 = 21 mod 11 = 10
x4 = 3x3 mod 11 = 3·10 mod 11 = 30 mod 11 = 8
x5 = 3x4 mod 11 = 3·8 mod 11 = 24 mod 11 = 2
La sucesión buscada es: 2, 6, 7, 10, 8, 2…
Según el Teorema chino del resto, se puede ver que un entero a, con
0 ≤ a < m, se representa de una única forma por una n-tupla
construida con los restos de las n divisiones de a entre los mi, con
i = 1, 2 … n. Es decir, a se puede expresar de manera única mediante:
Ejemplo: ¿cuáles son los pares usados para representar los números
enteros no negativos menores que 12 cuando se representan
mediante pares ordenados en los que la primera componente es el
resto de la división del entero entre 3 y la segunda componente es el
resto de la división del entero entre 4?
(33, 8, 9, 89) + (32, 92, 42, 16) = (65, 100, 51, 105) = (65, 2, 51, 10)
Ejercicio:
1. Expresa cada entero no negativo a menor que 15 usando los pares (a mod 3,
a mod 5).
Pseudoprimos
En la búsqueda de métodos eficientes para determinar si un número
n es primo, cuestión de gran interés en matemáticas y en ciencias de
la computación, algunos matemáticos chinos antiguos creían que n
era primo si, y solo si,
2n-1 ≡ 1 (mod n)
porque:
• Primero, observaron que esta congruencia se cumplía siempre
que n es primo (aunque no habían probado con todos los primos).
• Segundo, nunca llegaron a encontrar un entero compuesto n para
el cual se verificase la congruencia.
Ejemplo:
Ejercicios:
1. Cifra el mensaje “NO PASAR” traduciendo las letras a números,
aplicando la función de cifrado dada y pasando los números
obtenidos a letras (utiliza el alfabeto español de 27 letras,
suprimiendo la letra ch).
a) f(p) = (p+3) mod 27 a) PR SDVDU
b) f(p) = (p+13) mod 27 b) ZB CNFNE
c) f(p) = (3p+7) mod 27 c) SY BHKHE