Download Universidad de Costa Rica Escuela de Ciencias de la Computación

UNIVERSIDAD DE COSTA RICA
ESCUELA DE CIENCIAS DE LA COMPUTACIÓN E INFORMÁTICA
CI-1204 MATEMÁTICAS DISCRETAS
PROF. M.SC. KRYSCIA DAVIANA RAMÍREZ BENAVIDES
Práctica de Teoría de Números
Enunciado
Resuelva los siguientes problemas, haga el desarrollo de su trabajo completo, ordenado y legible.
1. Demostrar que 7 | (11n – 4n).
R/. Se dan valores para n, y así evaluar la expresión y saber qué valores toma:
n=0
110 – 40 = 1 – 1 = 0
n=1
111 – 41 = 11 – 4 = 7
n=2
112 – 42 = 121 – 16 = 105
n=3
113 – 43 = 1331 – 64 = 1267
n=4
114 – 44 = 14641 – 256 = 14385
n=5
115 – 45 = 161051 – 1024 = 160027
n=6
116 – 46 = 1771561 – 4096 = 1767465
Como se puede observar los resultados son divisibles entre 7. La demostración rigurosa de que 7 | (11n – 4n) se
verifica para todo n  0 debe realizarse por inducción sobre n.
2. Dados a,b  N tales que a | b y a | (b + 2), encontrar los valores de a para que se cumpla la afirmación anterior.
R/. Ya que a | b debe existir k  N tal que b = k • a. Análogamente, ya que a | (b + 2) debe existir l  N tal que b
+ 2 = l • a.
De las dos igualdades anteriores se deduce que (b + 2) – b = l • a – k • a  2 = (l – k) • a, con lo cual a|2. Se sabe
que 2 es primo y sus divisores son 1 y 2, por lo que la respuesta son sus divisores.
3. Sea x un número entero tal que 0  x  32, donde x  2 en Z/(5) y x  3 en Z/(4). De acuerdo a esto conteste
(justifique):
a. ¿Puede el número 7 ser el valor de x?
R/. Sí, ya que
x  2 Z/(5)
x  3 Z/(4)
7  2 Z/(5)
7  3 Z/(4)
7 - 2  5  1
5
5
7 - 3  4  1
4
4
b. ¿Puede el número 22 ser el valor de x?
R/. No, ya que
x  2 Z/(5)
x  3 Z/(4)
22  2 Z/(5)
22  3 Z/(4)
22 - 2  20  4
5
5
22 - 3  19  4.75
4
4
c. ¿Puede el número 27 ser el valor de x?
R/. No, ya que
x  2 Z/(5)
x  3 Z/(4)
22  2 Z/(5)
22  3 Z/(4)
22 - 2  20  4
5
5
22 - 3  19  4.75
4
4
4. Dado x  Z tal que 0  x  22, donde x  3 0 y x  5 1 , encontrar los valores de x para que se cumpla la
afirmación anterior.
R/. Los números comprendidos entre 0 y 22 cuyo resto al dividir por 3 es 0 son: 0, 3, 6, 9, 12, 15, 18 y 21. De
ellos, los que cuyo resto al dividir por 5 es 1 son: 6 y 21.
x 3 0
x 5 1
6 3 0
6 5 1
6 mod 3  0
6 mod 5  1
0 mod 3  0
1 mod 5  1
21  3 0
21  5 1
21 mod 3  0
21 mod 5  1
0 mod 3  0
1 mod 5  1
5. Calcular todos los números primos menores que 100 utilizando el método de la criba de Eratóstenes.
R/. La criba de Eratóstenes para encontrar los números primos < 100 es:
2
3
5
7
9
11
13
15
17
19
21
23
25
27
29
31
33
35
37
39
41
43
45
47
49
51
53
55
57
59
61
63
65
67
69
71
73
75
77
79
81
83
85
87
89
91
93
95
97
99
3 2  9  100  Tachar múltiplos de 3
5 2  25  100  Tachar múltiplos de 5
7 2  49  100  Tachar múltiplos de 7
112  121  100  Los números sin tachar son primos
Los números primos < 100 son P = {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}.
6. Indicar y justificar para cada uno de los siguientes números si es o no primo. Y cuáles parejas de ellos son primos
relativos.
a. 4803.
R/. Se calcula la raíz cuadrada del número
4803  69 , luego se verifica si existe algún divisor del
número entre los números que se encuentran en el rango ]1,69]:
 No es primo porque el número es divisible entre 3, ya que 4+8+0+3 = 15 que es múltiplo de 3.
b. 3803.










R/. Se calcula la raíz cuadrada del número
3803  61 , luego se verifica si existe algún divisor del
número entre los números que se encuentran en el rango ]1,61]. Al no existir ningún divisor del número
en ese rango se concluye que 3803 es un número primo.
c. 3804.
R/. Se calcula la raíz cuadrada del número
3804  61 , luego se verifica si existe algún divisor del
número entre los números que se encuentran en el rango ]1,61]:
 No es primo porque el número es divisible entre 2, ya que 2 | 3804 = 1902.
d. 5027.
R/. Se calcula la raíz cuadrada del número
5027  70 , luego se verifica si existe algún divisor del
número entre los números que se encuentran en el rango ]1,70]:
 No es primo porque el número es divisible entre 7, ya que 7 | 5027 = 457.
e. 5803.
R/. Se calcula la raíz cuadrada del número
5803  76 , luego se verifica si existe algún divisor del
número entre los números que se encuentran en el rango ]1,76]:
 No es primo porque el número es divisible entre 7, ya que 7 | 5803 = 829.
7. Calcular las descomposiciones en factores primos de 201, 1001 y 201000.
R/. La descomposición en factores primos de cada número es:
201 = 31 • 671
1001 = 71 • 111 • 131
201000 = 23 • 31 • 53 • 671
8. Calcular el MCD de 2406 y 654, y expresarlo en la forma 2406m + 654n, m,n  Z.
R/. Se aplica el algoritmo de Euclides con a = 2406 y b = 654. En cada paso ai+1 = bi y bi+1 = ri, siendo ri = ai mod
bi, porque mcd(ai,bi) = mcd(bi,ri). Los cálculos correspondientes se resumen en la siguiente tabla:
i
0
1
2
3
4
5
6
De la tabla se concluye que:
ai
2406
654
444
210
24
18
6
bi
654
444
210
24
18
6
0
ri
444
210
24
18
6
0
-
ci
3
1
2
8
1
3
-
mcd 2406,654  mcd 654,444  mcd 444,210  mcd 210,24  mcd 24,18  mcd 18,6  mcd 6,0  0
Al ser mcd(2406,654) = 6, el teorema de Bézout asegura que existe números enteros m, n tales que 2406m + 654n
= 6. Para obtener los dos coeficientes enteros se extiende la tabla con las columnas mi, ni, que se calculan de abajo
hacia arriba mediante la fórmula mi = ni+1, ni = mi+1 – ni+1 • ci, comenzando con m8 = 1 y n8 = 0 porque esos
valores cumplen que a8m8 + b8n8 = 6. Al llegar a i = 0 se obtiene finalmente m = m0 = 28 y n = n0 = -103.
i
ai
bi
ri
ci
mi
ni
0
2406
654
444
3
28
-103
1
654
444
210
1
-19
28
2
444
210
24
2
9
-19
3
210
24
18
8
-1
9
4
24
18
6
1
1
-1
5
18
6
0
3
0
1
6
6
0
1
0
Por lo que se concluye que m = 28 y n = -103, de forma que 2406 • 28 + 654 • -103 = 6.
9. Calcular el MCM de 2406 y 654.
R/. El mcm(2406,654) = 262254
Forma #1
2406 654
2
1203
327
3
401
109
401
1
1
109
Forma #2
2406 = 21 • 31 • 4011
654 = 21 • 31 • 1091
mcm(2406,654) = 21 • 31 • 4011 • 1091 = 262254
Forma #3
2406 • 654 = 1573524
2406 = 21 • 31 • 4011
654 = 21 • 31 • 1091
mcd(2406,654) = 21 • 31 = 6
mcm(2406,654) = (2406 • 654) / mcd(2406,654) = 1573524 / 6 = 262254
10. Encontrar las soluciones de la ecuación 3x  4  1 en Z/(6).
R/. La ecuación 3x  4  1 en Z/(6) se resuelve:
x=0
3 0  4  4
x=1
x=2
x=3
x=4
3 1  4  7  1
3  2  4  10  4
3  3  4  13  1
3  4  4  16  4
3  5  4  19  1
x=5
Su conjunto solución es S = {1,3,5}.
11. Encontrar las soluciones de la ecuación 9x  6 en Z/(12).
R/. La ecuación 9x  6 en Z/(12) se resuelve:
x=0
90  0
x=1
x=2
x=3
x=4
x=5
x=6
x=7
x=8
x=9
x = 10
9 1  9
9  2  18  6
9  3  27  3
9  4  36  0
9  5  45  9
9  6  54  6
9  7  63  3
9  8  72  0
9  9  81  9
9  10  90  6
9  11  99  3
x = 11
Su conjunto solución es S = {2,6,10}.
12. Encontrar todas las soluciones de la ecuación 35x ≡ 10 (mod 50).
R/. Sea la ecuación 35x  10 (mod 50), donde a = 35, b = 10 y n = 50
Línea 1 
(d,x,y) = EuclidesExtendido(a,n)
(d,x,y) = EuclidesExtendido(35,50)
i
ai
bi
ri
ci
0
35
50
35
0
1
50
35
15
1
2
35
15
5
2
3
15
5
0
3
4
5
0
De la tabla se obtiene que d = 5, m = 3 y n = -2 (35 • 3 + 50 • -2 = 5).
Por lo que, (d,x,y) = (5,3,-2).
mi
3
-2
1
0
1
ni
-2
3
-2
1
0
Línea 2  d b  5 10  2  Se ejecutan las líneas 3 - 5.
Línea 3  x0  3  10 / 5 mod 50  3  2  mod 50  6
Línea 4  El ciclo va de 0 a 4
Línea 5  Se imprimen los valores 6, 16, 26, 36 y 46
x1  6  0  50 / 5 mod 50  6
x 2  6  1  50 / 5 mod 50  6  10  mod 50  16 mod 50  16
x3  6  2  50 / 5 mod 50  6  20  mod 50  26 mod 50  26
x 4  6  3  50 / 5 mod 50  6  30  mod 50  36 mod 50  36
x5  6  4  50 / 5 mod 50  6  40  mod 50  46 mod 50  46 El conjunto solución de la
ecuación 35x  10 (mod 50) es
S = {6,16,26,36,46}.