Matemática Discreta

Hoja 1: Aritmética modular

1. Usando el algoritmo de Euclides, calcula m.c.d.(a, b), siendo

(i) a = 7469, b = 2464 (iii) a = 1109, b = 4999
(ii) a = 1485, b = 1745 (iv) a = 1320, b = 714.
Expresa en cada caso m.c.d.(a, b) como combinación lineal de a y b.
2. Si a, b ∈ N son relativamente primos (es decir m.c.d.(a, b) = 1), entonces
¿cuánto vale m.c.m.(a, b)? ¿Por qué?
3. ¿Tiene soluciones enteras la ecuación 12x+21y = 46? Justifica tu respuesta.
4. Encuentra todas las soluciones positivas de la ecuación diofántica 5x +
12y = 71.
5. Halla todas las la soluciones enteras de las siguientes ecuaciones diofánticas:
(a) 1485x + 1745y = 15.
(b) 37x + 23y = 10.
(c) 966x + 686y = 70.
(d) 154x + 260y = 3.
(e) 154x + 260y = 4.
6. Se desean cambiar 5000 coronas danesas en libras y dólares. Suponiendo
que el cambio se estima en 150 coronas por libra y 80 coronas por dólar,
encuentra todos los posibles cambios que pueden realizarse, sin considerar
los peniques ni los centavos.
7. Entre automóviles, triciclos y motocicletas tenemos 100 vehı́culos y el
número total de ruedas (sin contar las de repuesto) es 323. ¿Cuántos vehı́cu-
los puede haber de cada clase?
8. Realiza las siguientes operaciones módulo 5 y 6
2011 + 56, 361532 , 130 − 51.

9. Realiza las siguientes operaciones módulo 7

2345 + 214 · 432, 2419 + 987.

10. ¿En qué número termina 264 ?

11. Halla todas las soluciones enteras de la congruencia
5x + 2 ≡ 5 mód 7.

12. Demuestra que la congruencia

3x + 4 ≡ 5 mód 6
 no tiene solución.
13. Encuentra todos los números n ∈ N tal que su división por 3, 4 y 5 tenga
resto 1, 2 y 3 respectivamente.
14. Resuelve los siguientes sistemas de congruencias
 
 x ≡ 2 mód 3
 x≡3
 mód 5
(i) x ≡ 5 mód 7 (iii) x≡5 mód 7
 
x ≡ 1 mód 5 x≡2 mód 2
 

 x ≡ 4 mód 3

(ii) x ≡ 5 mód 7

x ≡ 2 mód 2


15. El Ministerio de Economı́a y Hacienda necesita que le enviemos un fax con

una copia del DNI para realizar unas gestiones. El fax que enviamos no es
de buena calidad y alguno de los dı́gitos de nuestro NIF no se pueden leer.
En el Ministerio el fax recibido es el siguiente:

NIF: 94176721 − 

(el cuadrado negro representa la letra que no se puede leer). ¿Podrı́as de-
ducir la letra que no hemos podido entender? En caso afirmativo dedúcelo
y en caso negativo explica por qué no se puede.
16. Calcular m.c.d.(n, n + 2), donde n ∈ N es cualquier número par mayor que
2. Calcular u, v ∈ Z tales que m.c.d.(n, n + 2) = u · n + v · (n + 2) (identidad
de Bezout).
17. Un coleccionista de obras de arte ha adquirido varios cuadros y dibujos de
un artista moderno. Las pinturas le han costado a 649 euros cada una y
los dibujos se los han dejado a 132 euros cada uno. Cuando el coleccionista
llega a su casa, no recuerda si el lote de obras de arte le ha costado 2760 o
2761 euros. ¿Podrı́as deducir cuánto le ha costado exactamente? ¿Cuántos
cuadros y cuantas pinturas ha comprado?
18. Encontrar todas las soluciones enteras positivas del siguiente sistema de
congruencias lineales:
(
x ≡ 2 mód 10
x ≡ 1 mód 7

19. Encontrar todas las soluciones enteras positivas del siguiente sistema de
congruencias lineales:
(
x ≡ 1 mód 7
x ≡ 4 mód 5
20. Calcula todos los números enteros que son múltiplos de 13, que terminan
en 4 y tales que al dividirlos por 7 nos da resto 2. ¿Cual entre todos ellos
es el número natural más pequeño?
21. Tenemos una colección de sellos de forma que si colocamos los sellos en
montones de 10, nos sobran 4 sellos, si los colocamos en montones de 9
nos sobran 6 y si los colocamos en montones de 7 no nos sobra ninguno.
¿Cuántos sellos puede tener la colección? ¿Cuál es el número más pequeño
de sellos que tiene la colección?
22. Sea c un número natural tal que 10 ≤ c ≤ 1000.
(a) ¿Para qué valores de c (comprendidos entre 10 y 1000) tiene soluciones
la ecuación diofántica 84x + 990y = c? Si c0 es el menor valor que
verifica lo anterior, resolver la ecuación diofántica 84x + 990y = c0 .
(b) ¿Existen valores de c (entre 10 y 1000) para los que dicha ecuación
tenga soluciones enteras positivas?
23. Se pide calcular números enteros x, y ∈ Z tales que que verifican si-
multáneamente las siguientes condiciones:
(a) x es igual a 1 más un múltiplo de 3 y al dividirlo por 17 da resto 5.
(b) y es múltiplo de 13 y su última cifra es 7.
(c) x e y son solución de la ecuación diofántica 128x + 41y = 564.
24. Calcula todos los números enteros x, y que cumplan simultáneamente
que x + 2y ≡ 1 mód 13 y 2x − y ≡ 3 mód 13. ¿Cuáles entre todos ellos
son los números x e y que son los números naturales más pequeños?
25. Calcular todos los números x, y, z ∈ Z que simultáneamentecumplan las
condiciones siguientes:

3x − y + 2z = 43
(a)
x − 23y − z = 12
(b) 3x − 2 es un múltiplo de 14.
(c) 2x + y es múltiplo de 7 y las dos últimas cifras de y son 12.

¿Hay soluciones x, y, z que cumplen que x > y? Razona tu respuesta y en

caso afirmativo calcúlalas.
26. Calcular todos los números enteros x, y ∈ Z de forma que 3x−2 es múltiplo
de 25 y las dos últimas cifras de 4x + 15y son 16. ¿Existen x, y ∈ Z cum-
pliendo lo anterior y además que 0 ≤ x ≤ y ≤ 50? Razona tus respuestas
y, en caso afirmativo, calcúlalos.
27. Consideremos el número 834.
(i) ¿De cuántas maneras diferentes podemos expresar 834 como suma de
dos números enteros positivos a, b ≥ 0 de forma que a es múltiplo
de 15 y b es múltiplo de 21?
 (ii) Calcula todas las formas de expresar 834 como suma de dos números
enteros impares y de cualquier signo a, b ∈ Z de forma que a es
múltiplo de 15 y b es múltiplo de 21.
28. Calcular todas las formas de poner 125 como suma de dos números enteros
n y m de forma que n sea múltiplo de 72 y m es divisible por 35. ¿De cuantas
formas se puede poner si n y m son mayores que -100 y menores que 100?
Razona tus respuestas.
29. Tras hacer la declaración de la renta (IRPF) del año pasado, la Agencia
Tributaria nos notifica que tenemos que pagar una cantidad entera de
euros x. Para facilitar el pago del impuesto, el Estado nos da a elegir una
de las siguientes formas de pago:
(a) Pagar 2 euros del impuesto ahora y el resto pagarlo en varias mensua-
lidades de 7 euros cada una.
(b) Pagar 10 euros del impuesto ahora y el resto pagarlo en varias men-
sualidades de 11 euros cada una.
(c) No abonar nada de entrada, pero pagar varias mensualidades de 39
euros cada una.
Calcula todos los valores de x que podemos deber a la Agencia Tributaria.
Si nuestra deuda es inferior a 10.000 euros, ¿cuánto le debemos a hacienda?
30. Un almacén de productos informáticos guarda una partida de paquetes de
DVD (tanto DVD+RW como DVD-RW) para distribuirlos próximamente.
Los DVDs estan empaquetados en cajas (todas del mismo tamaño) pero los
DVD+RW vienen en bobinas de 10 discos y los DVD-RW vienen en bobinas
de 11 discos cada una. A su vez las bobinas de discos están guardados en
cajas de 64 bobinas cada una de forma que en el almacén hay varias cajas
repletas de bobinas y una caja que solo tiene 32 bobinas. Si en total hay
6500 discos calcula cuántos DVD+RW y cuántos DVD-RW hay.
31. Se pide:
a) Calcular todas los números enteros x cuyo valor absoluto es ma-
yor que 100 y que además son solución del sistema de congruencias
siguiente:

(
x≡2 mód 7
x≡5 mód 8

b) Calcular todas los números enteros x menores que 50 y que además

son solución del sistema de congruencias siguiente:

x ≡ 2 mód 7

x ≡ 5 mód 8

x ≡ 5 mód 6

32. Una banda de cinco ladrones que acaba de robar un banco, trata de repar-
tirse el botı́n de lingotes de oro que acaba de robar. Desafortunadamente,
después de repartir el botı́n en partes iguales, sobraban tres lingotes, por lo
que se desató una pelea y uno de ellos murió. Tras hacer de nuevo el reparto
de todo el botı́n entre los supervivientes, sobraban 2 lingotes, por lo que
se volvió a desatar otra pelea y murió otro ladrón. Por último, volvieron
a repartirse el botı́n entre los supervivientes y ya no sobraban lingotes.
Calcula todos los lingotes que podı́an haber robado. ¿Cuál es el número
mı́nimo de lingotes que han robado si por lo menos han robado 100 lingotes
de oro?
33. Queremos enviar y recibir mensajes de forma segura codificando las comu-
nicaciones con un código de César. Para el proceso de cifrado se emplea
la siguiente tabla de cifrado
↔ 00 A ↔ 01 B ↔ 02 C↔ 03 D↔ 04 E ↔ 05 F↔ 06
G↔ 07 H↔ 08 I↔ 09 J↔ 10 K↔ 11 L↔ 12 M↔ 13
N↔ 14 Ñ↔ 15 O↔ 16 P↔ 17 Q↔ 18 R↔ 19 S↔ 20
T↔ 21 U↔ 22 V↔ 23 W↔ 24 X↔ 25 Y↔ 26 Z↔ 27
Se pide:
(a) Cifrar y codificar el mensaje ”SUERTE” empleando el código de César
que cada sı́mbolo cifrado x lo codifica como 3x + 5 mód 28.
(b) Decodificar y descifrar el mensaje cifrado 26 06 08 14 04 08 09 codificado
en el código de César del apartado anterior.
(c) Supongamos que interceptamos un mensaje cifrado y codificado largo
(como por ejemplo 06 18 · · · ) y sólo sabemos que ha sido codificado con
un código de César del tipo kx + 5 mód 28, donde k sólo puede valer
2,5,7,10 ó 14. ¿Podrı́amos deducir (sin hacer demasiadas cuentas) cuál
es el código empleado? Razona tus respuestas.
34. Tenemos que trasladar los libros de nuestra biblioteca en una serie de bol-
sas, de froma que si ponemos tres libros en cada bolsa nos sobran 3. Si
ponemos 5 en cada bolsa nos sobran 2 y si ponemos 7 en cada bolsa nos
sobran 5. Sabiendo que en nuestra colección hay más de 50 libros y menos
de 500, calcular cuńtos libros podemos tener.
35. Calcular todos los números enteros positivos que (simultáneamente) ter-
minan en 3 y son divisibles por 11 y además al dividirlos por 9 nos da resto
5. Hay alguno de estos n’umeros enteros que además de todo lo anterior
cumple que sea múltiplo de 6? Razona tus respuestas.
36. Demostrar que si p es primo y 0 < a < p, entonces existe un n’umero entero
0 < d < p tal que (a · d ≡ 1 mód p). Qué pasa si p no es primo? Razona
tus respuestas.
37. Calcular todos los números enteros x, y mayores que cien que son solu-
ción del siguiente sistema de congruencias:


 2y ≡ 1 mód 7
x + y ≡ 6 mód 7


 x − 2 ≡ 0 mód 5
x ≡ 3 mód 11
