Teoría de números y aritmética modular: problemas de práctica con soluciones paso a paso
También llamado: aritmética modular
Problemas gratis de Teoría de números y aritmética modular con diagramas, pistas y soluciones completas. Valores nuevos cada vez, en tres niveles: mcd y restos, inversos y congruencias, potencias modulares y RSA.
Problema de práctica gratisFácil
Halla 942 mod 11, el resto r con 0 ≤ r < 11.
a = 942n = 11
Respuesta exacta: un número entero, sin redondear.
Cómo resolver problemas de Teoría de números y aritmética modular
Reduce primero cada número módulo n; los restos están entre 0 y n − 1.
Para un mcd, divide repetidamente con el algoritmo de Euclides; el último resto distinto de cero es el mcd.
Para un inverso, aplica el algoritmo extendido y quédate con el coeficiente de a; suma n si es negativo.
Resuelve a·x ≡ b multiplicando por a⁻¹; combina dos congruencias escribiendo x = r₁ + m₁k.
Para las potencias, escribe el exponente en binario y eleva al cuadrado repetidamente; en RSA, d = e⁻¹ mod φ(n) con φ(n) = (p − 1)(q − 1).
Errores frecuentes
Dar un resto negativo para un número negativo.
Detener el algoritmo de Euclides en el primer resto.
Dejar el inverso negativo en lugar de sumarle n.
Tomar el exponente RSA d módulo n en lugar de módulo φ(n).
Reducir el exponente módulo p en lugar de módulo p − 1 con el teorema de Fermat.
Fórmulas clave
División con resto
a = q·n + r, 0 ≤ r < n
Euclides
gcd(a, b) = gcd(b, a mod b)
Mínimo común múltiplo
lcm(a, b) = a·b/gcd(a, b)
Inversa
a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
Congruencia lineal
a·x ≡ b → x ≡ a⁻¹·b (mod n)
Función φ de Euler
φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
Fermat
aᵖ⁻¹ ≡ 1 (mod p)
RSA
n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n
Aprende Teoría de números y aritmética modular desde cero
1Restos y congruencias
Al dividir a entre n se obtiene un cociente q y un resto r: a = q·n + r con 0 ≤ r < n. El resto se escribe a mod n. Para un número negativo, q también es negativo: −3 = −1·7 + 4, así que −3 mod 7 = 4.
Dos números son congruentes módulo n, a ≡ b (mod n), cuando dejan el mismo resto, es decir, cuando n divide a a − b.
Los restos se pueden reducir en cada paso, lo que mantiene los números pequeños:
(a + b) mod n = ((a mod n) + (b mod n)) mod n, y lo mismo para a·b
Por ejemplo, 47·58 mod 9: 47 ≡ 2 y 58 ≡ 4, así que 47·58 ≡ 8 (mod 9).
Autoevaluación ¿Cuánto es −17 mod 5?
2
3
−2
−3
Respuesta: 3. −17 = −4·5 + 3, así que el resto es 3. La respuesta 2 es 17 mod 5; un resto nunca es negativo.
2Algoritmo de Euclides
El máximo común divisor mcd(a, b) es el mayor número que divide a ambos. El algoritmo de Euclides usa mcd(a, b) = mcd(b, a mod b):
Divide: a = q·b + r.
Sustituye (a, b) por (b, r).
Repite hasta que el resto sea 0. El último resto distinto de cero es el mcd.
El mínimo común múltiplo se deduce de él: mcm(a, b) = a·b / mcd(a, b).
Autoevaluación ¿Cuánto es mcd(84, 36)?
12
252
4
6
Respuesta: 12. 84 = 2·36 + 12 y 36 = 3·12 + 0, así que el mcd es 12. 252 es el mínimo común múltiplo, 84·36/12.
3Inversos y el algoritmo extendido
El inverso de a módulo n es el número x con a·x ≡ 1 (mod n). Existe exactamente cuando mcd(a, n) = 1.
El algoritmo de Euclides extendido aplica Euclides a (n, a) y guarda un coeficiente t para cada resto, de modo que cada resto r ≡ t·a (mod n). Empieza con t = 0 para n y t = 1 para a; cada nuevo t es el t de dos filas más arriba menos q veces el t de una fila más arriba. Cuando aparece el resto 1, su t es el inverso.
Con el inverso, una congruencia a·x ≡ b (mod n) se resuelve con x ≡ a⁻¹·b. Cuando d = mcd(a, n) es mayor que 1, hay d soluciones si d divide a b, y ninguna en caso contrario.
Dos congruencias con módulos coprimos, x ≡ r₁ (mod m₁) y x ≡ r₂ (mod m₂), tienen exactamente una solución módulo m₁·m₂ (el teorema chino del resto). Escribe x = r₁ + m₁k y despeja k.
El cuadrado repetido calcula aᵏ mod n con rapidez: escribe k en binario, halla a, a², a⁴, a⁸, … mod n elevando al cuadrado y reduciendo, y multiplica las potencias cuyo bit es 1.
El pequeño teorema de Fermat: para un primo p que no divide a a, aᵖ⁻¹ ≡ 1 (mod p). Por tanto, el exponente se puede reducir módulo p − 1.
RSA construye una clave a partir de dos primos p y q:
n = p·q y φ(n) = (p − 1)(q − 1).
Elige e con mcd(e, φ(n)) = 1; (n, e) es la clave pública.
Calcula d = e⁻¹ mod φ(n): la clave privada.
Cifra c = mᵉ mod n; descifra m = cᵈ mod n.
La φ(n) de Euler cuenta los números de 1 a n que son coprimos con n: φ(p) = p − 1 para un primo, φ(pᵏ) = pᵏ − pᵏ⁻¹, y φ es multiplicativa para factores coprimos.
Autoevaluación Una clave RSA usa p = 5, q = 11 y e = 3. ¿Cuánto es d?
13
27
37
3
Respuesta: 27. φ(n) = 4·10 = 40, y 3·27 = 81 = 2·40 + 1, así que d = 27. El inverso de 3 módulo n = 55 sería 37, pero d se toma módulo φ(n).
5Errores frecuentes
Dar un resto negativo para un número negativo: −17 mod 5 es 3, no −2.
Detener Euclides en el primer resto en lugar de en el último distinto de cero.
Olvidar sumar n a un coeficiente negativo del algoritmo extendido.
Calcular el exponente RSA d módulo n en lugar de módulo φ(n).
Reducir un exponente módulo p en lugar de módulo p − 1 con el teorema de Fermat.
6Cómo son las preguntas de examen
Fácil: mcd y restos. Ejecutas el algoritmo de Euclides para un mcd o un mcm, hallas restos de números negativos y reduces sumas y productos módulo n.
Medio: inversos y congruencias. Hallas inversos modulares con el algoritmo extendido, resuelves congruencias lineales, combinas dos congruencias con el teorema chino del resto y calculas la φ(n) de Euler.
Difícil: potencias modulares y RSA. Usas el cuadrado repetido y el teorema de Fermat, resuelves congruencias con varias soluciones y hallas exponentes privados RSA, textos cifrados y mensajes descifrados.
Halla (914·953) mod 11 sin multiplicar los números grandes: reduce primero.
n = 11
Calcula (914·953) mod 11
Mostrar pistas
(x·y) mod n = ((x mod n)·(y mod n)) mod n, y lo mismo vale para las sumas.
914 mod 11 = 1, 953 mod 11 = 7.
Reduce módulo 11 el producto de los restos.
Mostrar la respuesta y la solución paso a paso
Divisibilidad y restos: a mod n es el resto r con 0 ≤ r < n y a = q·n + r, también cuando a es negativo. El algoritmo de Euclides halla mcd(a, b) repitiendo a = q·b + r y sustituyendo (a, b) por (b, r); el último resto distinto de cero es el mcd. Entonces mcm(a, b) = a·b/mcd(a, b). Los restos se pueden reducir en cada paso: (a + b) mod n y (a·b) mod n solo dependen de a mod n y de b mod n.
Reduce cada número
914 ≡ 1, 953 ≡ 7 (mod 11)
Combina
1·7 = 7 ≡ 7 (mod 11)
Respuesta
(914·953) mod 11 = 7
Ejemplo 2Media
Halla la función φ de Euler φ(637), el número de enteros de 1 a 637 que son coprimos con 637.
n = 637 = 72·13
Calcula φ(637)
Mostrar pistas
Factoriza n en primos: 637 = 72·13.
φ es multiplicativa para factores coprimos, y φ(pᵏ) = pᵏ − pᵏ⁻¹.
φ(n) = n·∏(1 − 1/p).
Mostrar la respuesta y la solución paso a paso
Inversos y congruencias: a tiene inverso módulo n exactamente cuando mcd(a, n) = 1. El algoritmo de Euclides extendido escribe 1 = s·n + t·a, y entonces a⁻¹ ≡ t (mod n). Una congruencia a·x ≡ b (mod n) con mcd(a, n) = 1 tiene la solución x ≡ a⁻¹·b. Dos congruencias x ≡ r₁ (mod m₁) y x ≡ r₂ (mod m₂) con módulos coprimos tienen una solución módulo m₁·m₂ (teorema chino del resto). La φ(n) de Euler cuenta los números de 1 a n que son coprimos con n: φ(n) = n·∏(1 − 1/p).
Factores primos
637 = 72·13
Función φ
φ(637) = φ(49)·φ(13) = 42·12 = 504
Respuesta
φ(637) = 504
Ejemplo 3Difícil
Una clave RSA usa p = 13, q = 37 y e = 23. Descifra el texto cifrado c = 225: halla el mensaje m.
p = 13q = 37e = 23c = 225
Calcula m
Mostrar pistas
n = 481, φ(n) = 432.
d = e⁻¹ mod φ(n) = 263.
m = cd mod n = 225263 mod 481: usa el cuadrado repetido.
Mostrar la respuesta y la solución paso a paso
Potencias modulares y RSA: calcula aᵏ mod n por cuadrado repetido: escribe k en binario, eleva al cuadrado, reduce después de cada paso y multiplica las potencias cuyo bit es 1. Fermat: aᵖ⁻¹ ≡ 1 (mod p) para un primo p que no divide a a, así que el exponente se puede reducir módulo p − 1. RSA: elige los primos p y q, n = p·q y φ(n) = (p − 1)(q − 1); el exponente público e es coprimo con φ(n), y el exponente privado es d = e⁻¹ mod φ(n). Cifra con c = mᵉ mod n y descifra con m = cᵈ mod n.
Exponente privado
n = 481, φ(n) = 432
d = 23−1 mod 432 = 263
Descifra por cuadrado repetido
263 = 256 + 4 + 2 + 1
2251 ≡ 225 (mod 481)
2252 ≡ 120 (mod 481)
2254 ≡ 451 (mod 481)
2258 ≡ 419 (mod 481)
22516 ≡ 477 (mod 481)
22532 ≡ 16 (mod 481)
22564 ≡ 256 (mod 481)
225128 ≡ 120 (mod 481)
225256 ≡ 451 (mod 481)
225263 ≡ 225·120·451·451 ≡ 361 (mod 481)
Mensaje
m = 361
comprobación: 36123 mod 481 = 225
Respuesta
m = 361
Preguntas y respuestas
Teoría de números y aritmética modular: ¿qué es?
Al dividir a entre n se obtiene un cociente q y un resto r: a = q·n + r con 0 ≤ r < n. El resto se escribe a mod n. Para un número negativo, q también es negativo: −3 = −1·7 + 4, así que −3 mod 7 = 4.
Dos números son congruentes módulo n, a ≡ b (mod n), cuando dejan el mismo resto, es decir, cuando n divide a a − b.
Teoría de números y aritmética modular: ¿cómo se resuelven los ejercicios paso a paso?
Reduce primero cada número módulo n; los restos están entre 0 y n − 1.
Para un mcd, divide repetidamente con el algoritmo de Euclides; el último resto distinto de cero es el mcd.
Para un inverso, aplica el algoritmo extendido y quédate con el coeficiente de a; suma n si es negativo.
Resuelve a·x ≡ b multiplicando por a⁻¹; combina dos congruencias escribiendo x = r₁ + m₁k.
Para las potencias, escribe el exponente en binario y eleva al cuadrado repetidamente; en RSA, d = e⁻¹ mod φ(n) con φ(n) = (p − 1)(q − 1).
Teoría de números y aritmética modular: ¿cuáles son los errores más comunes?
Dar un resto negativo para un número negativo.
Detener el algoritmo de Euclides en el primer resto.
Dejar el inverso negativo en lugar de sumarle n.
Tomar el exponente RSA d módulo n en lugar de módulo φ(n).
Reducir el exponente módulo p en lugar de módulo p − 1 con el teorema de Fermat.
Teoría de números y aritmética modular: ¿qué se practica?
Fácil: mcd y restos
Media: inversos y congruencias
Difícil: potencias modulares y RSA
Cada problema tiene valores nuevos, así aprendes el método y no una respuesta. ¿Te has atascado? Abre primero una pista pequeña y la explicación completa solo cuando la necesites.
Cómo funciona la práctica
Cada problema tiene valores nuevos, así aprendes el método y no una respuesta.
¿Te has atascado? Abre primero una pista pequeña y la explicación completa solo cuando la necesites.
Tu progreso, tus errores y tus problemas guardados se conservan para que puedas repasar antes del examen.