La letra del DNI sale de un resto
La aritmética modular trabaja con restos: es la matemática de un reloj, donde después de las 12 vuelve a empezar. Con ella se calculan letras de control, se reparten datos en tablas y se protegen mensajes.
La letra de un DNI sale de dividir su número entre 23 y mirar el resto. Si te equivocas al teclear una cifra, la letra casi nunca coincide, y el error se detecta.
Al final de esta lección
Nota
Puedo usar restos, el máximo común divisor y los números primos para resolver problemas.
Palabras clave
| Palabra | Qué significa | Ejemplo |
|---|---|---|
| Resto | lo que sobra al dividir | 17 % 5 = 2 |
| Módulo | el número por el que se divide para sacar el resto | |
| Divisor | un número que divide a otro sin dejar resto | |
| Máximo común divisor | el mayor divisor que tienen en común dos números (mcd) | |
| Número primo | un número mayor que 1 con solo dos divisores: 1 y él mismo | |
| Dígito de control | una cifra o letra que se calcula para detectar errores |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
El resto cuenta como un reloj
El resto de dividir 17 entre 5 es 2, porque 17 = 3 × 5 + 2. En Python se escribe 17 % 5. El número por el que divides es el módulo.
Con módulo 5, los restos posibles son 0, 1, 2, 3 y 4. Al llegar a 5 se vuelve a 0, como un reloj. Por eso el resto nunca es negativo: -1 % 5 vale 4.
Ejemplo resuelto: los restos entre 5
| Número | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| Resto entre 5 | 0 | 1 | 2 | 3 | 4 | 0 | 1 | 2 | 3 |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Tres restos en Python
python3 -c "print(17 % 5, -1 % 5, 100 % 7)"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
La letra del DNI 12345678
python3 -c "print(12345678 % 23, 'TRWAGMYFPDXBNJZSQVHLCKE'[12345678 % 23])"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Un resto reparte direcciones en una caché
En el laboratorio, una caché de 8 líneas guarda cada dirección de memoria en la línea que sale de dividir la dirección entre 8. La dirección 21 va a la línea 5.
Es el mismo reparto que una tabla con 8 casillas: el resto dice en qué casilla cae cada número.
El algoritmo de Euclides halla el mcd
El máximo común divisor (mcd) de dos números es el mayor que divide a los dos. Euclides lo calcula con restos: el mcd de a y b es el mcd de b y el resto de a entre b.
Repites hasta que el resto es 0. El último divisor es el mcd.
Ejemplo resuelto: mcd de 48 y 18
| Paso | Cuenta | Resto |
|---|---|---|
| 1 | 48 = 2 × 18 + 12 | 12 |
| 2 | 18 = 1 × 12 + 6 | 6 |
| 3 | 12 = 2 × 6 + 0 | 0 |
| Resultado | El último divisor es 6 | mcd = 6 |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Python halla el mcd
python3 -c "import math; print(math.gcd(48, 18))"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Un error frecuente
Advertencia
Mucha gente cree que el 1 es un número primo. No lo es. Un primo tiene exactamente dos divisores, 1 y él mismo, y el 1 solo tiene uno. El primer primo es el 2.
Un primo solo tiene dos divisores
Un número primo es mayor que 1 y no tiene más divisores que 1 y él mismo. Para saber si n es primo, prueba a dividirlo entre 2, 3, 4 y así hasta n − 1. Si alguna división no deja resto, no es primo.
Los primos más pequeños son 2, 3, 5, 7, 11 y 13.
Los primos menores que 30
python3 -c "print([n for n in range(2, 30) if all(n % d != 0 for d in range(2, n))])"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
El inverso modular deshace una multiplicación
El inverso de a, con módulo m, es el número x que cumple a × x % m = 1. Con módulo 26, el inverso de 7 es 15, porque 7 × 15 = 105 = 4 × 26 + 1.
Solo existe si el mcd de a y m es 1. Con módulo 8, el 4 no tiene inverso, porque su mcd con 8 es 4. Es la base del cifrado con claves.
El inverso de 7 con módulo 26
python3 -c "print(pow(7, -1, 26), 7 * 15 % 26)"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.