Matemáticas de secundaria · Grades 10–12

29Aritmética

La aritmética estudia los números enteros: la divisibilidad, los números primos, los restos. Durante mucho tiempo se la consideró la más pura de las matemáticas puras y hoy protege todos los pagos por internet: el criptosistema RSA se apoya en los teoremas de Bézout, Gauss y Fermat que se demuestran en este capítulo.

29.1 Divisibilidad y división euclídea

Definición 29.1 (Divisibilidad)

Sean $a, b \in \Z$ . Decimos que $b$ divide a $a$ , y escribimos $b \mid a$ , si existe $k \in \Z$ con $a = kb$ . También decimos que $a$ es múltiplo de $b$ .

Proposición 29.2

Si $c \mid a$ y $c \mid b$ , entonces $c$ divide a toda combinación entera $au + bv$ ( $u, v \in \Z$ ). Si $a \mid b$ y $b \mid a$ con $a,b \in \N$ , entonces $a = b$ . Si $a \mid b$ y $b \neq 0$ , entonces $\abs a \leq \abs b$ .

Demostración. Escribimos $a = kc$ y $b = lc$ : entonces $au + bv = (ku + lv)c$ . Los demás puntos se siguen de $\abs{a} = \abs{k}\,\abs{b}$ con $\abs k \geq 1$ cuando $b = ka \neq 0$ . ∎

Teorema 29.3 (División euclídea)

Sean $a \in \Z$ y $b \in \N^*$ . Existe una única pareja $(q, r) \in \Z \times \N$ tal que

a = bq + r \qquad\text{y}\qquad 0 \leq r < b .

$q$ es el cociente y $r$ , el resto.

Demostración. Existencia. El conjunto de los múltiplos de $b$ que no superan a $a$ tiene un elemento máximo $bq$ (no es vacío y está acotado superiormente); tomamos $r = a - bq$ . Por maximalidad, $b(q+1) > a$ , luego $0 \leq r < b$ . Unicidad. Si $bq + r = bq' + r'$ con $0 \leq r, r' < b$ , entonces $b(q - q') = r' - r$ y $\abs{r' - r} < b$ : un múltiplo de $b$ de valor absoluto menor que $b$ tiene que ser $0$ , luego $r = r'$ y $q = q'$ . ∎

29.2 Congruencias

Definición 29.4 (Congruencia)

Sea $n \in \N^*$ . Dos enteros $a, b$ son congruentes módulo $n$ , y se escribe $a \equiv b \pmod n$ , si $n \mid (a - b)$ ; equivalentemente, si $a$ y $b$ dan el mismo resto en la división euclídea entre $n$ .

Proposición 29.5 (Compatibilidad con las operaciones)

Si $a \equiv b \pmod n$ y $c \equiv d \pmod n$ , entonces

a + c \equiv b + d, \qquad ac \equiv bd, \qquad a^k \equiv b^k \ (k \in \N) \pmod n .

Demostración. $n$ divide a $(a-b) + (c-d) = (a+c) - (b+d)$ , y $ac - bd = a(c - d) + d(a - b)$ también es múltiplo de $n$ . La regla de las potencias se sigue por inducción a partir de la del producto. ∎

Método 29.6 (Calcular potencias módulo $n$ )

Para calcular $a^k \bmod n$ , reduce la base módulo $n$ , busca después una potencia pequeña de $a$ congruente con $\pm1$ y úsala para colapsar el exponente. Por ejemplo, $2^{100} \bmod 7$ : como $2^3 = 8 \equiv 1 \pmod 7$ y $100 = 3\times33 + 1$ ,

2^{100} = \left(2^{3}\right)^{33} \times 2 \equiv 1^{33}\times 2 = 2 \pmod 7 .

29.3 Máximo común divisor, Bézout y Gauss

Definición 29.7 (Máximo común divisor)

Sean $a, b$ enteros no nulos a la vez. El máximo común divisor $\gcd(a, b)$ es el mayor entero que divide a la vez a $a$ y a $b$ . Cuando $\gcd(a,b) = 1$ , se dice que $a$ y $b$ son primos entre sí.

Proposición 29.8 (Algoritmo de Euclides)

Si $a = bq + r$ (con $b \neq 0$ ), entonces $\gcd(a, b) = \gcd(b, r)$ . Iterar la división euclídea calcula, por tanto, $\gcd(a,b)$ : el máximo común divisor es el último resto no nulo.

Demostración. Todo divisor común de $a$ y $b$ divide a $r = a - bq$ (Proposición 29.2) y es, por tanto, divisor común de $b$ y $r$ ; y recíprocamente, puesto que $a = bq + r$ . Las dos parejas tienen los mismos divisores comunes y, por tanto, el mismo máximo común divisor. El algoritmo termina porque los restos forman una sucesión estrictamente decreciente de enteros no negativos. ∎

Ejemplo 29.9

$\gcd(252, 198)$ : $252 = 198 + 54$ ; $198 = 3\times54 + 36$ ; $54 = 36 + 18$ ; $36 = 2 \times 18 + 0$ . Por tanto, $\gcd(252,198) = 18$ .

Teorema 29.10 (Identidad de Bézout)

Sean $a, b$ enteros no nulos a la vez y sea $d = \gcd(a,b)$ . Existen $u, v \in \Z$ tales que

au + bv = d .

En particular, $a$ y $b$ son primos entre sí si y solo si $au + bv = 1$ para ciertos enteros $u, v$ .

Demostración. Recorremos hacia atrás el algoritmo de Euclides: cada resto es una combinación entera de los dos anteriores, y los datos iniciales $a, b$ son combinaciones de sí mismos; por sustitución descendente, el último resto no nulo $d$ es una combinación entera de $a$ y $b$ . (En el Ejemplo 29.9: $18 = 54 - 36 = 54 - (198 - 3\times54) = 4\times54 - 198 = 4(252 - 198) - 198 = 4\times252 - 5\times198$ .)

Para la equivalencia: si $\gcd(a,b) = 1$ , Bézout proporciona $u, v$ ; recíprocamente, todo divisor común de $a$ y $b$ divide a $au + bv = 1$ , lo que obliga a $\gcd(a,b) = 1$ . ∎

Teorema 29.11 (Lema de Gauss)

Sean $a, b, c \in \Z$ . Si $a \mid bc$ y $\gcd(a, b) = 1$ , entonces $a \mid c$ .

Demostración. Bézout da $au + bv = 1$ ; multiplicamos por $c$ : $acu + bcv = c$ . Los dos términos del primer miembro son múltiplos de $a$ (el segundo porque $a \mid bc$ ), luego $c$ también lo es. ∎

Corolario 29.12

Si $a \mid c$ , $b \mid c$ y $\gcd(a,b) = 1$ , entonces $ab \mid c$ .

Demostración. Escribimos $c = ak$ . De $b \mid ak$ y $\gcd(a,b)=1$ , el lema de Gauss da $b \mid k$ , digamos $k = bl$ ; entonces $c = abl$ . ∎

29.4 Números primos

Definición 29.13 (Primo)

Un entero $p \geq 2$ es primo si sus únicos divisores positivos son $1$ y $p$ .

Proposición 29.14

Todo entero $n \geq 2$ tiene un divisor primo; y si $n$ no es primo, tiene un divisor primo $\leq \sqrt n$ . Si un primo $p$ divide a un producto $ab$ , entonces $p \mid a$ o $p \mid b$ (lema de Euclides).

Demostración. El menor divisor $d \geq 2$ de $n$ es primo (cualquier divisor propio de $d$ sería un divisor menor de $n$ ). Si $n = de$ es compuesto con $2 \leq d \leq e$ , entonces $d^2 \leq de = n$ , luego $d \leq \sqrt n$ . Para el lema de Euclides: si $p \nmid a$ , entonces $\gcd(p, a) = 1$ (los únicos divisores de $p$ son $1$ y $p$ ), y el lema de Gauss da $p \mid b$ . ∎

Teorema 29.15 (Euclides)

Hay infinitos números primos.

Demostración. Dada una lista finita cualquiera $p_1, \dots, p_k$ de primos, consideramos $N = p_1 p_2 \cdots p_k + 1$ . Algún primo $p$ divide a $N$ ; pero ningún $p_i$ divide a $N$ (el resto es $1$ ), así que $p$ es un primo que no está en la lista. Ninguna lista finita agota los primos. ∎

Teorema 29.16 (Teorema fundamental de la aritmética)

Todo entero $n \geq 2$ es producto de primos, y esa factorización es única salvo el orden de los factores:

n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_r^{\alpha_r}, \qquad p_1 < p_2 < \dots < p_r \text{ primos},\ \alpha_i \geq 1 .

Demostración. Existencia, por inducción fuerte: si $n$ es primo, él mismo es su factorización; si no, $n = de$ con $2 \leq d, e < n$ , y los dos se factorizan por la hipótesis de inducción. Unicidad: supongamos $p_1\cdots p_s = q_1 \cdots q_t$ (primos, con repeticiones permitidas). Por el lema de Euclides, $p_1$ divide a algún $q_j$ y, al ser primo, $p_1 = q_j$ ; simplificamos y repetimos. Las dos factorizaciones coinciden término a término. ∎

Teorema 29.17 (Pequeño teorema de Fermat)

Sea $p$ primo y sea $a \in \Z$ con $p \nmid a$ . Entonces

a^{p-1} \equiv 1 \pmod p .

Para todo $a \in \Z$ (sin suponer que sean primos entre sí), $a^p \equiv a \pmod p$ .

Demostración. Consideremos los $p - 1$ enteros $a, 2a, 3a, \dots, (p-1)a$ módulo $p$ . Ninguno es $\equiv 0$ (si $p \mid ka$ con $1 \leq k \leq p-1$ , el lema de Euclides obliga a $p \mid k$ , imposible) y son distintos dos a dos módulo $p$ (si $ka \equiv la$ , entonces $p \mid (k - l)a$ , luego $p \mid k - l$ y $k = l$ ). Por tanto, módulo $p$ son los números $1, 2, \dots, p-1$ en algún orden. Multiplicando todas las congruencias:

a^{p-1}\,(p-1)! \equiv (p-1)! \pmod p .

Como $p$ no divide a ninguno de los $1, \dots, p-1$ , aplicar repetidamente el lema de Euclides permite cancelar $(p-1)!$ y queda $a^{p-1} \equiv 1$ . La segunda forma se sigue multiplicando por $a$ (y es trivial cuando $p \mid a$ ). ∎

Ejemplo 29.18 (Aplicación a la criptografía)

El teorema de Fermat hace reversible la exponenciación módulo $n$ cuando los exponentes se eligen adecuadamente: ese es el corazón del criptosistema RSA. Con $p, q$ primos grandes y $n = pq$ , se publican $n$ y un exponente $e$ ; cifrar es $x \mapsto x^e \bmod n$ . Descifrar exige un exponente $d$ con $ed \equiv 1 \pmod{(p-1)(q-1)}$ , que solo puede calcular quien conozca $p$ y $q$ ; y recuperar $p$ y $q$ a partir de $n$ significa factorizar un número de cientos de cifras, cosa que ningún algoritmo conocido hace en un tiempo razonable.

29.5 Ejercicios

Ejercicio 29.1 ★

Calcula el cociente y el resto de la división euclídea de $2026$ entre $17$ , y de $-2026$ entre $17$ .

Solución

Solución de Ejercicio 29.1.

$17 \times 119 = 2023$ , luego $2026 = 17 \times 119 + 3$ : cociente $119$ y resto $3$ . Para $-2026$ : $-2026 = 17\times(-120) + 14$ (en efecto, $17 \times 120 = 2040$ y $2040 - 2026 = 14$ ): cociente $-120$ y resto $14$ (el resto tiene que estar en $\intco{0}{17}$ , así que no es $-3$ ).

Ejercicio 29.2 ★

¿Cuál es el resto de $7^{100}$ módulo $10$ ? (¿Cuál es la última cifra de $7^{100}$ ?)

Solución

Solución de Ejercicio 29.2.

Módulo $10$ : $7^2 = 49 \equiv 9 \equiv -1$ . Por tanto, $7^{100} = \left(7^2\right)^{50} \equiv (-1)^{50} = 1 \pmod{10}$ : la última cifra de $7^{100}$ es $1$ .

Ejercicio 29.3 ★

Usando el algoritmo de Euclides, calcula $\gcd(1071, 462)$ y halla enteros $u, v$ con $1071u + 462v = \gcd(1071, 462)$ .

Solución

Solución de Ejercicio 29.3.

Euclides: $1071 = 2\times462 + 147$ ; $462 = 3\times147 + 21$ ; $147 = 7\times21 + 0$ . Luego $\gcd = 21$ .

Sustitución hacia atrás: $21 = 462 - 3\times147 = 462 - 3(1071 - 2\times462) = 7\times462 - 3\times1071$ . Así que $u = -3$ y $v = 7$ : $1071\times(-3) + 462\times7 = 21$ .

Ejercicio 29.4 ★

Demuestra que para todo $n \in \Z$ , $n^2$ es congruente con $0$ o con $1$ módulo $4$ . Deduce que un entero $\equiv 3 \pmod 4$ nunca es suma de dos cuadrados.

Solución

Solución de Ejercicio 29.4.

Todo entero es $\equiv 0, 1, 2$ o $3 \pmod 4$ y, al elevar al cuadrado: $0^2 \equiv 0$ , $1^2 \equiv 1$ , $2^2 = 4 \equiv 0$ , $3^2 = 9 \equiv 1$ . Así que $n^2 \equiv 0$ o $1 \pmod 4$ . Una suma de dos cuadrados es entonces congruente con $0 + 0$ , $0 + 1$ o $1 + 1$ , es decir, con $0$ , $1$ o $2 \pmod 4$ ; nunca con $3$ .

Ejercicio 29.5 ★★

Demuestra que para todo $n \in \N$ , $n(n+1)(2n+1)$ es divisible entre $6$ .

Solución

Solución de Ejercicio 29.5.

Divisibilidad entre $2$ : de $n$ y $n + 1$ , uno es par. Divisibilidad entre $3$ : si $n \equiv 0$ , entonces $3 \mid n$ ; si $n \equiv 1 \pmod 3$ , entonces $2n + 1 \equiv 3 \equiv 0$ ; y si $n \equiv 2$ , entonces $n + 1 \equiv 0$ . En todos los casos, $3$ divide al producto. Como $\gcd(2,3) = 1$ , el Corolario 29.12 da $6 \mid n(n+1)(2n+1)$ . (Esto vuelve a demostrar, además, que $\frac{n(n+1)(2n+1)}{6}$ , la suma de cuadrados del Ejercicio 20.1, es un entero.)

Ejercicio 29.6 ★★

Resuelve en $\Z$ la congruencia $5x \equiv 3 \pmod{11}$ . (Indicación: halla el inverso de $5$ módulo $11$ .)

Solución

Solución de Ejercicio 29.6.

Buscamos el inverso de $5$ módulo $11$ : probando (o con Bézout), $5 \times 9 = 45 = 44 + 1 \equiv 1 \pmod{11}$ . Multiplicando la congruencia por $9$ :

x \equiv 9 \times 3 = 27 \equiv 5 \pmod{11}.

Las soluciones son los enteros $x = 5 + 11k$ , con $k \in \Z$ . (Comprobación: $5\times5 = 25 \equiv 3 \pmod{11}$ .)

Ejercicio 29.7 ★★

Resuelve en $\Z \times \Z$ la ecuación diofántica

17x - 40y = 1,

y describe después todas las soluciones de $17x - 40y = 6$ .

Solución

Solución de Ejercicio 29.7.

$\gcd(17, 40) = 1$ , así que hay soluciones. Euclides: $40 = 2\times17 + 6$ ; $17 = 2\times6 + 5$ ; $6 = 5 + 1$ . Sustituyendo hacia atrás: $1 = 6 - 5 = 6 - (17 - 2\times6) = 3\times6 - 17 = 3(40 - 2\times17) - 17 = 3\times40 - 7\times17$ . Por tanto, $17\times(-7) - 40\times(-3) = 1$ : la solución particular $(x_0, y_0) = (-7, -3)$ .

Solución general de $17x - 40y = 1$ : restando la relación particular, $17(x + 7) = 40(y + 3)$ ; y como $\gcd(17, 40) = 1$ , el lema de Gauss da $40 \mid x + 7$ , luego $x = -7 + 40k$ y después $y = -3 + 17k$ , con $k \in \Z$ (y todas ellas se comprueban).

Para $17x - 40y = 6$ , multiplicamos la solución particular por $6$ : $(x_1, y_1) = (-42, -18)$ , y el mismo razonamiento da

x = -42 + 40k, \qquad y = -18 + 17k, \qquad k \in \Z .

(Por ejemplo, con $k = 2$ : $x = 38$ , $y = 16$ ; en efecto, $17\times38 - 40\times16 = 646 - 640 = 6$ .)

Ejercicio 29.8 ★★

Demuestra que $\sqrt2$ es irracional usando la unicidad de la factorización en primos (compara el exponente de $2$ en los dos miembros de $a^2 = 2b^2$ ).

Solución

Solución de Ejercicio 29.8.

Supongamos $\sqrt2 = \frac ab$ con $a, b \in \N^*$ ; entonces $a^2 = 2b^2$ . En la factorización en primos de un cuadrado, todos los exponentes son pares; así que el exponente de $2$ en $a^2$ es par, mientras que en $2b^2$ es impar (uno más que un número par). Dos factorizaciones del mismo entero con exponentes distintos de $2$ contradicen la unicidad del Teorema 29.16. Por tanto, no existe tal fracción: $\sqrt2 \notin \Q$ .

Ejercicio 29.9 ★★★

Sea $p$ un primo.

Demuestra que para $1 \leq k \leq p - 1$ , $p$ divide a $\dbinom{p}{k}$ . (Indicación: usa $k\binom pk = p\binom{p-1}{k-1}$ , Ejercicio 27.7, y el lema de Gauss.)
Deduce, por inducción sobre $a \geq 0$ , otra demostración del pequeño teorema de Fermat en la forma $a^p \equiv a \pmod p$ .

Solución

Solución de Ejercicio 29.9.

1. De $k\binom pk = p \binom{p-1}{k-1}$ se sigue que $p$ divide a $k\binom pk$ . Para $1 \leq k \leq p-1$ , $p \nmid k$ y, siendo $p$ primo, $\gcd(p, k) = 1$ , así que el lema de Gauss da $p \mid \binom pk$ .

2. Inducción sobre $a$ . Para $a = 0$ : $0^p \equiv 0$ . Supongamos $a^p \equiv a \pmod p$ . Por el teorema del binomio,

(a+1)^p = \sum_{k=0}^{p} \binom pk a^k \equiv a^p + 1 \pmod p,

porque todos los términos intermedios se anulan módulo $p$ por el punto 1. Por la hipótesis de inducción, $(a+1)^p \equiv a + 1 \pmod p$ . Esto demuestra $a^p \equiv a$ para todo $a \in \N$ , y el caso $a < 0$ se sigue escribiendo $a \equiv a + kp$ con un representante positivo adecuado.

Ejercicio 29.10 ★★★

(Problema chino de los restos.) Halla todos los enteros $n$ tales que

n \equiv 2 \pmod 3, \qquad n \equiv 3 \pmod 5, \qquad n \equiv 2 \pmod 7 .

(Indicación: resuelve las dos primeras condiciones e incorpora después la tercera; los coeficientes de Bézout ayudan.)

Solución

Solución de Ejercicio 29.10.

$n \equiv 2 \pmod 3$ y $n \equiv 3 \pmod 5$ : escribimos $n = 2 + 3s$ ; entonces $2 + 3s \equiv 3 \pmod 5$ , es decir, $3s \equiv 1 \pmod 5$ . El inverso de $3$ módulo $5$ es $2$ ( $3\times2 = 6 \equiv 1$ ), luego $s \equiv 2 \pmod 5$ , digamos $s = 2 + 5t$ , y $n = 8 + 15t$ : las dos primeras condiciones significan $n \equiv 8 \pmod{15}$ .

Añadiendo $n \equiv 2 \pmod 7$ : $8 + 15t \equiv 2 \pmod 7$ , y $15 \equiv 1 \pmod 7$ , así que $t \equiv -6 \equiv 1 \pmod 7$ , digamos $t = 1 + 7u$ . Por tanto, $n = 23 + 105u$ :

n \equiv 23 \pmod{105}.

(Comprobación: $23 = 3\times7 + 2 = 5\times4 + 3 = 7\times3 + 2$ .)

29.6 Problema: Códigos secretos y dígitos de control

Problema 29.1

Problema de fin de semana — las congruencias custodian todos los códigos de barras y todas las tarjetas de crédito, y el pequeño teorema de Fermat maneja la cerradura de los secretos del mundo

G. H. Hardy presumía en 1940 de que la teoría de números estaba “sin mancillar” por las aplicaciones. Ochenta años después, cada pitido de un código de barras, cada pago con tarjeta y cada mensaje cifrado lo contradicen, y con exactamente las herramientas de este capítulo: las congruencias (Proposición 29.5), los inversos de Bézout (Teorema 29.10) y el pequeño teorema de Fermat (Ejercicio 29.9). Este problema comprueba los códigos, fuerza una versión de juguete de la cerradura y descubre por qué aguanta la de verdad.

Parte I — Soltura con las congruencias.

Calcula $2026 \bmod 7$ ; y después la última cifra de $7^{100}$ (halla el ciclo de las potencias de $7$ módulo $10$ ).
Exponenciación rápida (Método 29.6): calcula $5^{117} \bmod 13$ (parte de $5^2 \equiv -1$ ).
Resuelve $3x \equiv 5 \pmod 7$ .
Aplica el algoritmo de Euclides a $(97, 35)$ , sustituye hacia atrás para hallar enteros $u, v$ con $97u + 35v = 1$ y deduce el inverso de $35$ módulo $97$ .
Enuncia con precisión cuándo es $a$ invertible módulo $n$ y qué teorema entrega el inverso.

Parte II — Dígitos de control.

ISBN-10: las diez cifras $d_1 \dots d_{10}$ del código de un libro deben cumplir $10d_1 + 9d_2 + \dots + 2d_9 + 1d_{10} \equiv 0 \pmod{11}$ . Comprueba el ISBN real $0\,306\,40615\,2$ .
Demuestra que el esquema ISBN detecta todos los errores de una sola cifra: si una cifra cambia en $d \not\equiv 0$ , la suma ponderada cambia en $w d$ con $1 \leq w \leq 10$ ; ¿por qué eso nunca puede ser $\equiv 0 \pmod{11}$ (Teorema 29.11)?
Demuestra que también detecta cualquier trasposición de dos cifras adyacentes (distintas). Explica después el secreto del diseño: ¿qué propiedad del $11$ hizo funcionar las dos demostraciones y qué podría salir mal con el módulo $10$ ?
Los códigos de barras EAN-13 ponderan las cifras con $1, 3, 1, 3, \dots$ módulo $10$ . Calcula el dígito de control que completa $978\,2940199\,05$ . ¿Qué trasposiciones adyacentes no detecta el EAN? (¿Cuándo es $2(a - b) \equiv 0 \pmod{10}$ ?)
Las tarjetas de crédito usan el esquema de Luhn: desde la derecha, se dobla una cifra de cada dos (restando $9$ cuando el doble pasa de $9$ ), se suma todo y se exige un múltiplo de $10$ . Comprueba el número de prueba $4539\,1488\,0343\,6467$ .
En una frase: ¿qué le compró el módulo primo al ISBN que el EAN y Luhn, encadenados al $10$ , no pueden tener?

Parte III — La cerradura de Fermat.

Una trampa antes del tesoro: calcula $2^{10} \bmod 341$ , deduce $2^{340} \bmod 341$ y factoriza después $341$ . ¿Qué dice este ejemplo (un pseudoprimo de Fermat) sobre usar el pequeño teorema de Fermat como test de primalidad?
RSA en miniatura: tomamos $p = 3$ y $q = 11$ , de modo que $n = 33$ y $(p-1)(q-1) = 20$ ; el exponente público es $e = 3$ . Halla el exponente privado $d$ con $3d \equiv 1 \pmod{20}$ (el método de la pregunta 4).
Cifra el mensaje $m = 4$ : calcula $c = m^3 \bmod 33$ .
Descifra: calcula $c^d \bmod 33$ (usa $c \equiv -2 \pmod{33}$ ) y recupera el mensaje.
Por qué funciona siempre el descifrado: demuestra que $m^{21} \equiv m$ tanto módulo $3$ como módulo $11$ (el pequeño teorema de Fermat en cada mundo) y concluye módulo $33$ (el Teorema 29.11 pega las dos congruencias). ¿Dónde entró la forma especial $1 + 20k$ de $21 = ed$ ?
La seguridad de la cerradura: todo el mundo conoce $n$ y $e$ ; recuperar $d$ exige $(p-1)(q-1)$ y, por tanto, los factores de $n$ . Nuestro $33$ se factoriza de un vistazo; ¿por qué el mismo esquema, con un $n$ de seiscientas cifras, protege a los bancos del mundo? (Una frase sobre la asimetría entre multiplicar y factorizar.)

Parte IV — Clásicos.

El viejo recuento chino de soldados (compara con el Ejercicio 29.10): un número de soldados deja resto $2$ al formar de tres en tres y resto $3$ al formar de cinco en cinco. Halla todos los recuentos posibles y explica por qué la respuesta es única módulo $15$ .
Demostraciones de una línea, por fin: de $10 \equiv 1 \pmod 9$ , demuestra que todo número es congruente con la suma de sus cifras módulo $9$ ; y de $10 \equiv -1 \pmod{11}$ , deduce la regla de la suma alternada para el $11$ . (El volumen anterior las demostró con álgebra explícita; admira la compresión.)
Final: Hardy contra el código de barras: repasa la caja de herramientas del capítulo (la aritmética de congruencias, los inversos de Bézout, el pequeño teorema de Fermat y el pegado de módulos primos entre sí) y dónde encajó cada una en este problema; y da después el veredicto moderno sobre lo de “sin mancillar”.

Solución

Solución de Problema 29.1.

1. $2026 = 289 \times 7 + 3$ : $2026 \equiv 3 \pmod 7$ . Potencias de $7$ módulo $10$ : $7, 9, 3, 1$ , con un ciclo de longitud $4$ ; y $100 \equiv 0 \pmod 4$ : la última cifra de $7^{100}$ es $1$ .

2. $5^2 = 25 \equiv -1 \pmod{13}$ , luego $5^{116} = \left(5^2\right)^{58} \equiv (-1)^{58} = 1$ y $5^{117} \equiv 5 \pmod{13}$ .

3. El inverso de $3$ módulo $7$ es $5$ ( $15 \equiv 1$ ): $x \equiv 5 \times 5 = 25 \equiv 4 \pmod 7$ .

4. $97 = 2 \times 35 + 27$ ; $35 = 27 + 8$ ; $27 = 3 \times 8 + 3$ ; $8 = 2 \times 3 + 2$ ; $3 = 2 + 1$ . Sustituyendo hacia atrás: $1 = 97 \times 13 + 35 \times (-36)$ . Luego $35 \times (-36) \equiv 1 \pmod{97}$ : el inverso de $35$ es $-36 \equiv 61 \pmod{97}$ .

5. $a$ es invertible módulo $n$ exactamente cuando $\gcd(a, n) = 1$ : Bézout proporciona $au + nv = 1$ , es decir, $au \equiv 1$ ; y, recíprocamente, la existencia de un inverso obliga al máximo común divisor a dividir a $1$ .

6. $0{\cdot}10 + 3{\cdot}9 + 0{\cdot}8 + 6{\cdot}7 + 4{\cdot}6 + 0{\cdot}5 + 6{\cdot}4 + 1{\cdot}3 + 5{\cdot}2 + 2{\cdot}1 = 132 = 12 \times 11 \equiv 0 \pmod{11}$ : válido.

7. La suma cambia en $wd$ con $1 \leq w \leq 10$ y $1 \leq \abs d \leq 9$ : como $11$ es primo y no divide a ninguno de los dos factores, no puede dividir al producto (Teorema 29.11 y Proposición 29.14): la suma modificada nunca vuelve a ser $\equiv 0$ , así que todo error de una sola cifra dispara la alarma.

8. Intercambiar dos cifras adyacentes $a$ y $b$ (con pesos $w + 1$ y $w$ ) cambia la suma en $(w+1)b + wa - (w+1)a - wb = b - a \not\equiv 0$ si $a \neq b$ : detectado. El secreto es la primalidad del $11$ : módulo $10$ , productos como $5 \times 2$ se anulan sin que ninguno de los factores sea nulo, así que un error de $\pm 2$ en una posición de peso $5$ (o una trasposición desafortunada) podría colarse.

9. Suma ponderada de las doce cifras: $119$ ; el dígito de control tiene que completarla hasta un múltiplo de $10$ : $1$ (código completo, $978\,2940199\,051$ ). El EAN se pierde las trasposiciones adyacentes con $2(a - b) \equiv 0 \pmod{10}$ , es decir, con $\abs{a - b} = 5$ : intercambiar un $2$ y un $7$ , por ejemplo, pasa desapercibido; el precio del amable módulo $10$ .

10. Doblando una cifra de cada dos desde la derecha y plegando ( $16 \to 7$ , etc.), la suma da $80 \equiv 0 \pmod{10}$ : la tarjeta de prueba es válida.

11. Con un módulo primo, todos los pesos son invertibles, así que se detectan todos los errores de una cifra y todas las trasposiciones adyacentes: el lujo del ISBN; los esquemas módulo $10$ conservan cifras amables para las personas y aceptan un pequeño punto ciego.

12. $2^{10} = 1024 = 3 \times 341 + 1 \equiv 1 \pmod{341}$ , luego $2^{340} = \left(2^{10}\right)^{34} \equiv 1$ . Y, sin embargo, $341 = 11 \times 31$ es compuesto: pasa el test de Fermat en base $2$ sin ser primo. Moraleja: la congruencia de Fermat es necesaria, no suficiente; los tests de primalidad necesitan herramientas más finas (y las consiguen, en los volúmenes universitarios).

13. $3d \equiv 1 \pmod{20}$ : $d = 7$ ( $21 = 20 + 1$ ).

14. $c = 4^3 = 64 \equiv 31 \pmod{33}$ .

15. $31 \equiv -2$ : $(-2)^7 = -128$ , y $-128 + 4 \times 33 = 4$ : el texto cifrado se descifra como $m = 4$ . La cerradura gira.

16. Módulo $3$ : si $3 \nmid m$ , entonces $m^2 \equiv 1$ (Fermat), luego $m^{21} = m \cdot \left(m^2\right)^{10} \equiv m$ ; y si $3 \mid m$ , los dos miembros son $\equiv 0$ . Módulo $11$ : $m^{10} \equiv 1$ o bien $11 \mid m$ , y $m^{21} = m \cdot \left(m^{10}\right)^2 \equiv m$ . Tanto $3$ como $11$ dividen a $m^{21} - m$ y, al ser primos entre sí, su producto $33$ también (Gauss): $m^{21} \equiv m \pmod{33}$ . El exponente $ed = 21 = 1 + 20k$ se construyó para que desaparecieran los dos exponentes de Fermat ( $2$ y $10$ , que dividen a $20$ ).

17. Multiplicar dos primos de $300$ cifras cuesta un microsegundo; recuperarlos a partir de su producto derrota a todos los algoritmos conocidos y a todos los ordenadores del mundo: la cerradura es una calle de sentido único. (Nuestro $n = 33$ es esa calle a escala de juguete, transitable en los dos sentidos.)

18. Probando restos (o construyendo con Bézout): $n \equiv 8 \pmod{15}$ : los recuentos $8, 23, 38, 53, \dots$ Unicidad módulo $15$ : dos soluciones se diferencian en un múltiplo de $3$ y de $5$ y, por tanto, de $15$ ( $3$ y $5$ son primos entre sí; Gauss). El general con $1000$ soldados anuncia el “ $8$ ” con tres formaciones rápidas: el viejo truco del recuento.

19. $10 \equiv 1 \pmod 9$ da $10^k \equiv 1$ , luego $\sum d_k 10^k \equiv \sum d_k$ : un número y la suma de sus cifras son congruentes módulo $9$ (y módulo $3$ ). Y $10 \equiv -1 \pmod{11}$ da $\sum d_k 10^k \equiv \sum (-1)^k d_k$ : la regla alternada. Dos reglas de la infancia, a una línea cada una.

20. Las congruencias convirtieron los restos en una aritmética (Parte I); Bézout acuñó los inversos que resuelven las congruencias lineales y el $d$ de RSA (preguntas 4 y 13); el pequeño teorema de Fermat abrió y cerró la cerradura (preguntas 15 y 16); y pegar módulos primos entre sí contó soldados y remató la demostración (preguntas 16 y 18). Veredicto sobre Hardy: el más puro de los teoremas que él conocía custodia hoy cada compra; la pureza, con tiempo, es lo más aplicable que hay.

Términos definidos en este capítulo

Ver los 395 términos del glosario