---
title: "Aritmética"
book: "Matemáticas de secundaria"
subject: math
language: es
chapter: 29
exercises: 10
source: https://one-course.com/books/math/2/es/chapter/29-aritmetica
---

# Capítulo 29 — Aritmética

La aritmética estudia los [números enteros](https://one-course.com/books/math/2/es/chapter/1-numeros-y-conjuntos-de-numeros#def-g10-numbers-sets): la [divisibilidad](#def-g12-arith-divides), los [números primos](#def-g12-arith-prime), 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](#def-g12-arith-divides) 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](https://one-course.com/books/math/2/es/chapter/3-funciones#def-g10-functions-extrema) $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](https://one-course.com/books/math/2/es/chapter/1-numeros-y-conjuntos-de-numeros#def-g10-numbers-abs) 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](#thm-g12-arith-euclid) 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](#def-g12-arith-divides) 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 nnn).**

Para calcular $a^k \bmod n$, reduce la base [módulo](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $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](#def-g12-arith-divides) 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](#thm-g12-arith-euclid) calcula, por tanto, $\gcd(a,b)$: el [máximo común divisor](#def-g12-arith-gcd) es el último resto no nulo.

**Demostración.** Todo divisor común de $a$ y $b$ [divide](#def-g12-arith-divides) a $r = a - bq$ ([Proposición 29.2](#prop-g12-arith-divprops)) 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](#def-g12-arith-gcd). El algoritmo termina porque los restos forman una [sucesión](https://one-course.com/books/math/2/es/chapter/20-sucesiones#def-g12-seq-sequence) estrictamente [decreciente](https://one-course.com/books/math/2/es/chapter/3-funciones#def-g10-functions-variations) 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í](#def-g12-arith-gcd) si y solo si $au + bv = 1$ para ciertos enteros $u, v$.

**Demostración.** Recorremos hacia atrás el [algoritmo de Euclides](#prop-g12-arith-euclidalgo): 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](#ex-g12-arith-euclidalgo): $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](#def-g12-arith-divides) 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](#def-g12-arith-prime); y si $n$ no es [primo](#def-g12-arith-prime), tiene un divisor [primo](#def-g12-arith-prime) $\leq \sqrt n$. Si un [primo](#def-g12-arith-prime) $p$ [divide](#def-g12-arith-divides) 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](#def-g12-arith-prime) (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](#def-g12-arith-prime).

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

**Teorema 29.16 (Teorema fundamental de la aritmética).**

Todo entero $n \geq 2$ es producto de [primos](#def-g12-arith-prime), 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](#def-g12-arith-prime), é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](#def-g12-arith-prime), con repeticiones permitidas). Por el lema de Euclides, $p_1$ [divide](#def-g12-arith-divides) a algún $q_j$ y, al ser [primo](#def-g12-arith-prime), $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](#def-g12-arith-prime) 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í](#def-g12-arith-gcd)), $a^p \equiv a \pmod p$.

**Demostración.** Consideremos los $p - 1$ enteros $a, 2a, 3a, \dots, (p-1)a$ [módulo](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $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](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $p$ (si $ka \equiv la$, entonces $p \mid (k - l)a$, luego $p \mid k - l$ y $k = l$). Por tanto, [módulo](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $p$ son los números $1, 2, \dots, p-1$ en algún orden. Multiplicando todas las [congruencias](#def-g12-arith-congruence):

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

Como $p$ no [divide](#def-g12-arith-divides) 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](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $n$ cuando los exponentes se eligen adecuadamente: ese es el corazón del criptosistema *RSA*. Con $p, q$ [primos](#def-g12-arith-prime) 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](https://one-course.com/books/math/2/es/chapter/2-algebra-ecuaciones-e-inecuaciones#def-g10-algebra-expand) 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](#thm-g12-arith-euclid) de $2026$ entre $17$, y de $-2026$ entre $17$.

**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](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $10$? (¿Cuál es la última cifra de $7^{100}$?)

**Solución de Ejercicio 29.2.**

[Módulo](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $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](#prop-g12-arith-euclidalgo), calcula $\gcd(1071, 462)$ y halla enteros $u, v$ con $1071u + 462v = \gcd(1071, 462)$.

**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](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $4$. Deduce que un entero $\equiv 3 \pmod 4$ nunca es suma de dos cuadrados.

**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 de Ejercicio 29.5.**

[Divisibilidad](#def-g12-arith-divides) entre $2$: de $n$ y $n + 1$, uno es par. [Divisibilidad](#def-g12-arith-divides) 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](#def-g12-arith-divides) al producto. Como $\gcd(2,3) = 1$, el [Corolario 29.12](#cor-g12-arith-coprimeprod) 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](https://one-course.com/books/math/2/es/chapter/20-sucesiones#exo-g12-seq-1), es un entero.)

**Ejercicio 29.6 ★★.**

Resuelve en $\Z$ la [congruencia](#def-g12-arith-congruence) $5x \equiv 3 \pmod{11}$. (Indicación: halla el inverso de $5$ [módulo](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $11$.)

**Solución de Ejercicio 29.6.**

Buscamos el inverso de $5$ [módulo](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $11$: probando (o con Bézout), $5 \times 9 = 45 = 44 + 1 \equiv 1 \pmod{11}$. Multiplicando la [congruencia](#def-g12-arith-congruence) 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](https://one-course.com/books/math/2/es/chapter/2-algebra-ecuaciones-e-inecuaciones#def-g10-algebra-equation) diofántica

$$
17x - 40y = 1,
$$

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

**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](#def-g12-arith-prime) (compara el exponente de $2$ en los dos miembros de $a^2 = 2b^2$).

**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](#def-g12-arith-prime) 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](https://one-course.com/books/math/2/es/chapter/11-funciones-y-variacion#def-g11-func-parity) (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](#thm-g12-arith-fta). Por tanto, no existe tal fracción: $\sqrt2 \notin \Q$.

**Ejercicio 29.9 ★★★.**

Sea $p$ un [primo](#def-g12-arith-prime).

1. Demuestra que para $1 \leq k \leq p - 1$ , $p$ [divide](#def-g12-arith-divides) a $\dbinom{p}{k}$ . (Indicación: usa $k\binom pk = p\binom{p-1}{k-1}$ , [Ejercicio 27.7](https://one-course.com/books/math/2/es/chapter/27-combinatoria-y-conteo#exo-g12-comb-7) , y el lema de Gauss.)
2. 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 de Ejercicio 29.9.**

*1.* De $k\binom pk = p \binom{p-1}{k-1}$ se sigue que $p$ [divide](#def-g12-arith-divides) a $k\binom pk$. Para $1 \leq k \leq p-1$, $p \nmid k$ y, siendo $p$ [primo](#def-g12-arith-prime), $\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](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $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 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](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $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](#def-g12-arith-congruence) ([Proposición 29.5](#prop-g12-arith-congops)), los inversos de Bézout ([Teorema 29.10](#thm-g12-arith-bezout)) y el pequeño teorema de Fermat ([Ejercicio 29.9](#exo-g12-arith-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](#def-g12-arith-congruence).**

1. Calcula $2026 \bmod 7$ ; y después la última cifra de $7^{100}$ (halla el ciclo de las potencias de $7$ [módulo](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $10$ ).
2. Exponenciación rápida ( [Método 29.6](#met-g12-arith-powers) ): calcula $5^{117} \bmod 13$ (parte de $5^2 \equiv -1$ ).
3. Resuelve $3x \equiv 5 \pmod 7$ .
4. Aplica el [algoritmo de Euclides](#prop-g12-arith-euclidalgo) a $(97, 35)$ , sustituye hacia atrás para hallar enteros $u, v$ con $97u + 35v = 1$ y deduce el inverso de $35$ [módulo](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $97$ .
5. Enuncia con precisión cuándo es $a$ invertible [módulo](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $n$ y qué teorema entrega el inverso.

**Parte II — Dígitos de control.**

6. 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$ .
7. 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](#thm-g12-arith-gauss) )?
8. 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](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $10$ ?
9. Los códigos de barras EAN-13 ponderan las cifras con $1, 3, 1, 3, \dots$ [módulo](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $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}$ ?)
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$ .
11. En una frase: ¿qué le compró el [módulo](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) [primo](#def-g12-arith-prime) al ISBN que el EAN y Luhn, encadenados al $10$ , no pueden tener?

**Parte III — La cerradura de Fermat.**

12. 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?
13. 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).
14. Cifra el mensaje $m = 4$ : calcula $c = m^3 \bmod 33$ .
15. Descifra: calcula $c^d \bmod 33$ (usa $c \equiv -2 \pmod{33}$ ) y recupera el mensaje.
16. Por qué funciona siempre el descifrado: demuestra que $m^{21} \equiv m$ tanto [módulo](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $3$ como [módulo](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $11$ (el pequeño teorema de Fermat en cada mundo) y concluye [módulo](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $33$ (el [Teorema 29.11](#thm-g12-arith-gauss) pega las dos [congruencias](#def-g12-arith-congruence) ). ¿Dónde entró la forma especial $1 + 20k$ de $21 = ed$ ?
17. 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](https://one-course.com/books/math/2/es/chapter/2-algebra-ecuaciones-e-inecuaciones#def-g10-algebra-expand) .)

**Parte IV — Clásicos.**

18. El viejo recuento chino de soldados (compara con el [Ejercicio 29.10](#exo-g12-arith-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](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $15$ .
19. 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](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $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.)
20. Final: Hardy contra el código de barras: repasa la caja de herramientas del capítulo (la aritmética de [congruencias](#def-g12-arith-congruence) , los inversos de Bézout, el pequeño teorema de Fermat y el pegado de [módulos](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) [primos entre sí](#def-g12-arith-gcd) ) y dónde encajó cada una en este problema; y da después el veredicto moderno sobre lo de “sin mancillar”.

**Solución de Problema 29.1.**

**1.** $2026 = 289 \times 7 + 3$: $2026 \equiv 3 \pmod 7$. Potencias de $7$ [módulo](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $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](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $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](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $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](#def-g12-arith-gcd) 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](#def-g12-arith-prime) y no [divide](#def-g12-arith-divides) a ninguno de los dos factores, no puede dividir al producto ([Teorema 29.11](#thm-g12-arith-gauss) y [Proposición 29.14](#prop-g12-arith-primedivides)): 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](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $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](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $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](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) [primo](#def-g12-arith-prime), 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](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $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](#def-g12-arith-prime). Moraleja: la [congruencia](#def-g12-arith-congruence) 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](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $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](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $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í](#def-g12-arith-gcd), 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](#def-g12-arith-prime) 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](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $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í](#def-g12-arith-gcd); 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](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $9$ (y [módulo](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) $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](#def-g12-arith-congruence) convirtieron los restos en una aritmética (Parte I); Bézout acuñó los inversos que resuelven las [congruencias](#def-g12-arith-congruence) 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](https://one-course.com/books/math/2/es/chapter/28-numeros-complejos#def-g12-complex-modulus) [primos entre sí](#def-g12-arith-gcd) 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.