---
title: "Aritmética de los enteros"
book: "Matemáticas universitarias — Grado 1"
subject: math
language: es
chapter: 6
exercises: 12
source: https://one-course.com/books/math/3/es/chapter/6-aritmetica-de-los-enteros
---

# Capítulo 6 — Aritmética de los enteros

La aritmética — el estudio de la [divisibilidad](#def-b1-arith-divides) en $\Z$ — se empezó en el volumen anterior. Este capítulo la reconstruye por completo a partir de la división euclídea y con demostraciones completas: [máximo común divisor](#thm-b1-arith-gcd) y [algoritmo de Euclides](#met-b1-arith-euclid), identidad de Bézout y lema de Gauss, [factorización en primos](#thm-b1-arith-fta) y el cálculo de [congruencias](#def-b1-arith-congruence) hasta el pequeño teorema de Fermat. Más allá de su encanto propio, esta materia es el modelo que el [Capítulo 8](https://one-course.com/books/math/3/es/chapter/8-polinomios#ch-b1-poly) imita para los polinomios.

## 6.1 Divisibilidad y división euclídea

**Definición 6.1 (Divisibilidad).**

Para $a, b \in \Z$, se dice que $b$ *divide* a $a$ (y se escribe $b \mid a$) cuando $a = bq$ para algún $q \in \Z$. Consecuencias básicas: si $b \mid a$ y $b \mid a'$, entonces $b \mid (ua + va')$ para todos $u, v \in \Z$; si $b \mid a$ y $a \neq 0$, entonces $\abs b \leq \abs a$; y $a \mid b$ junto con $b \mid a$ obligan a $b = \pm a$.

**Teorema 6.2 (División euclídea).**

Para todos $a \in \Z$ y $b \in \N^*$ existe exactamente un par $(q, r) \in \Z \times \N$ con

$$
a = bq + r, \qquad 0 \leq r < b .
$$

**Demostración.** *Existencia.* El [conjunto](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-sets) $A = \{a - bk : k \in \Z\} \cap \N$ es un subconjunto no vacío de $\N$ (tómese $k = -\abs a$: $a + b\abs a
\geq a + \abs a \geq 0$). Sea $r = a - bq$ su elemento mínimo. Si $r \geq b$, entonces $r - b = a - b(q+1)$ sería un elemento menor de $A$: contradicción. 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$: el múltiplo de $b$ del miembro izquierdo tiene que ser $0$, luego $q = q'$ y $r = r'$. ∎

**Ejemplo 6.3 (Numeración posicional por divisiones sucesivas).**

Escríbase $2026$ en base $7$. Divídase repetidamente por $7$, guardando los restos:

$$
2026 = 7 \times 289 + 3, \quad
289 = 7 \times 41 + 2, \quad
41 = 7 \times 5 + 6, \quad
5 = 7 \times 0 + 5 .
$$

Leyendo los restos del último al primero: $2026 = (5\,6\,2\,3)_7$. Comprobación: $5 \times 343 + 6 \times 49 + 2 \times 7 + 3 = 1715 +
294 + 14 + 3 = 2026$. La unicidad de la división euclídea es exactamente lo que hace que cada cifra quede *forzada*: en cada paso, el resto es el único entero de $\intint06$ congruente con el valor actual [módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) $7$, así que la escritura en base $7$ es única — hecho que se usa en silencio siempre que el problema del fin de semana manipula «las cifras de $n$ en base $p$».

## 6.2 Máximo común divisor

**Teorema 6.4 (Subgrupos de Z\ZZ; existencia del mcd).**

1. Todo subgrupo de $(\Z, +)$ es de la forma $n\Z = \{nk : k  \in \Z\}$ para un único $n \in \N$ .
2. Para $a, b \in \Z$ no ambos nulos, el [conjunto](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-sets) $a\Z + b\Z =  \{au + bv : u, v \in \Z\}$ es un subgrupo de $\Z$ y, por tanto, es igual a $d\,\Z$ para un único $d \in \N^*$ . Ese $d$ es el *máximo común divisor* $\gcd(a, b)$ : [divide](#def-b1-arith-divides) a $a$ y a $b$ , y todo divisor común de $a$ y $b$ [divide](#def-b1-arith-divides) a $d$ .

**Demostración.** (1) Sea $H \subseteq \Z$ un subgrupo (no vacío y estable por resta; la definición formal está en el [Capítulo 7](https://one-course.com/books/math/3/es/chapter/7-estructuras-algebraicas#ch-b1-structures), y aquí solo se usan esas dos propiedades). Si $H = \{0\}$, tómese $n = 0$. En caso contrario, $H$ contiene un elemento no nulo y su opuesto, luego un menor elemento estrictamente positivo $n$. Entonces $n\Z \subseteq H$. Para $x \in H$, escríbase $x = nq + r$ con $0 \leq r < n$ ([Teorema 6.2](#thm-b1-arith-division)); $r = x - nq \in H$, y la minimalidad de $n$ obliga a $r = 0$: $x \in n\Z$. Unicidad: $n$ es el menor elemento positivo de $n\Z$.

(2) $a\Z + b\Z$ contiene $0$ y es estable por resta, luego es $d\Z$ con $d \geq 1$ (contiene $a$ o $b$, no nulos). Como $a, b \in d\Z$, $d$ [divide](#def-b1-arith-divides) a los dos. Y si $c$ [divide](#def-b1-arith-divides) a $a$ y a $b$, entonces $c$ [divide](#def-b1-arith-divides) a todo $au + bv$ — en particular $c \mid d$, pues $d \in a\Z
+ b\Z$. Esta es la propiedad anunciada (e implica $\abs c \leq d$, de modo que $d$ merece el nombre de *máximo* común divisor). ∎

**Corolario 6.5 (Identidad de Bézout).**

Para $a, b$ no ambos nulos existen $u, v \in \Z$ con

$$
au + bv = \gcd(a, b) .
$$

En particular ($\gcd(a,b) = 1$, el caso *coprimo*): $a$ y $b$ son [coprimos](#cor-b1-arith-bezout) si y solo si $au + bv = 1$ tiene solución.

**Demostración.** $\gcd(a,b) = d \in d\Z = a\Z + b\Z$. Para la equivalencia: si $\gcd(a,b) = 1$, Bézout da la solución; recíprocamente, $au + bv = 1$ obliga a todo divisor común de $a, b$ a dividir a $1$. ∎

**Método 6.6 (Algoritmo de Euclides, extendido).**

Para calcular $\gcd(a, b)$ ($a > b > 0$): divídase $a = bq + r$; entonces $\gcd(a, b) = \gcd(b, r)$ (los divisores comunes de $(a,b)$ y los de $(b,r)$ coinciden, pues $r = a - bq$); itérese hasta que el resto sea $0$; el último resto no nulo es el mcd. Recorrer las divisiones hacia atrás (o arrastrar los coeficientes al bajar) produce un par de Bézout $(u, v)$.

**Ejemplo 6.7.**

$\gcd(120, 23)$: $120 = 5 \times 23 + 5$; $23 = 4 \times 5 + 3$; $5 = 1\times 3 + 2$; $3 = 1 \times 2 + 1$; $2 = 2 \times 1 + 0$. Luego $\gcd = 1$. Hacia atrás:

$$
\begin{align*}
1 &= 3 - 2 = 3 - (5 - 3) = 2\times 3 - 5 = 2(23 - 4\times 5) - 5 \\
&= 2 \times 23 - 9 \times 5 = 2\times 23 - 9(120 - 5\times 23)
= 47 \times 23 - 9 \times 120 .
\end{align*}
$$

Comprobación: $47 \times 23 = 1081$, $9 \times 120 = 1080$.

**Teorema 6.8 (Lema de Gauss y consecuencias).**

Sean $a, b, c \in \Z$.

1. (Lema de Gauss) Si $a \mid bc$ y $\gcd(a, b) = 1$ , entonces $a \mid c$ .
2. Si $a \mid c$ , $b \mid c$ y $\gcd(a,b) = 1$ , entonces $ab \mid c$ .
3. Si $\gcd(a, b) = \gcd(a, c) = 1$ , entonces $\gcd(a, bc) = 1$ .

**Demostración.** (1) Bézout: $au + bv = 1$. Multiplíquese por $c$: $acu + bcv = c$. Los dos términos son divisibles por $a$ (el segundo porque $a \mid bc$), luego $a \mid c$.

(2) Escríbase $c = aq$; de $b \mid aq$ y $\gcd(a, b) = 1$, el punto (1) da $b \mid q$, luego $ab \mid aq = c$.

(3) $au + bv = 1$ y $au' + cv' = 1$. Multiplíquense las dos relaciones:

$$
1 = (au + bv)(au' + cv')
= a\,\bigl(auu' + ucv' + u'bv\bigr) + bc\,(vv') ,
$$

una relación de Bézout entre $a$ y $bc$: por el [Corolario 6.5](#cor-b1-arith-bezout), $\gcd(a, bc) = 1$. ∎

**Ejemplo 6.9 (Resolución de una ecuación diofántica lineal).**

Hállense todos los $(x, y) \in \Z^2$ con $6x + 10y = 4$. Primero, el *test de existencia*: $\gcd(6, 10) = 2$ [divide](#def-b1-arith-divides) a $4$, luego hay soluciones (si el mcd no dividiese al miembro derecho, el izquierdo sería siempre múltiplo suyo y no habría ninguna). Divídase todo: $3x + 5y = 2$. Se ve una solución particular: $(x_0, y_0) = (-1, 1)$. Para la general, réstese: $3(x + 1) = -5(y - 1)$, luego $3 \mid 5(y-1)$, y el lema de Gauss ($\gcd(3,5) = 1$) da $3 \mid y - 1$: $y = 1 - 3k$ y después $x = -1 + 5k$. Recíprocamente, todo par así sirve:

$$
(x, y) = (-1 + 5k,\ 1 - 3k), \qquad k \in \Z .
$$

El patrón es general: una solución particular más los múltiplos enteros de $\bigl(\frac b{\gcd}, -\frac a{\gcd}\bigr)$ — la misma estructura de «particular más homogénea» que en el [Capítulo 5](https://one-course.com/books/math/3/es/chapter/5-ecuaciones-diferenciales-lineales#ch-b1-diffeq), con el lema de Gauss haciendo el papel de la unicidad.

**Definición 6.10 (Mínimo común múltiplo).**

$\operatorname{lcm}(a, b)$ es el generador en $\N$ del subgrupo $a\Z \cap b\Z$: es un múltiplo común de $a$ y $b$ que [divide](#def-b1-arith-divides) a todo múltiplo común y, para $a, b \in \N^*$,

$$
\gcd(a,b) \times \operatorname{lcm}(a,b) = ab
\qquad (\text{demostración en el } \text{Ejercicio 6.5}).
$$

**Ejemplo 6.11 (Los problemas de coincidencia son problemas de mcm).**

Dos ruedas dentadas engranadas tienen $84$ y $36$ dientes. ¿Tras cuántos dientes de movimiento común vuelven las dos a su posición inicial? La configuración se repite cuando el número de dientes transcurridos es un múltiplo común de $84$ y $36$; la primera vez es

$$
\operatorname{lcm}(84, 36) = \frac{84 \times 36}{\gcd(84, 36)}
= \frac{3024}{12} = 252
$$

dientes — es decir, $3$ vueltas de la rueda grande y $7$ de la pequeña ($252/84$ y $252/36$). Obsérvese la vía práctica: *calcúlese primero el mcd* (Euclides: $84 = 2\times36 + 12$, $36 = 3\times12$) y divídase después — nunca se construya el mcm enumerando múltiplos. Toda cuestión de coincidencias periódicas (engranajes, alineaciones planetarias, decimales periódicos que se encuentran) se reduce a este único cálculo.

## 6.3 Números primos

**Definición 6.12.**

Un entero $p \geq 2$ es *primo* cuando sus únicos divisores positivos son $1$ y $p$. Para $p$ primo y $a \in \Z$: o bien $p \mid a$, o bien $\gcd(p, a) = 1$. En consecuencia ([Teorema 6.8](#thm-b1-arith-gauss)), se cumple el *lema de Euclides*: si $p \mid ab$, entonces $p \mid a$ o $p \mid b$.

**Observación 6.13 (Probar la primalidad por divisiones sucesivas).**

Si $n = ab$ con $2 \leq a \leq b$, entonces $a^2 \leq ab = n$, luego $a \leq \sqrt n$: un $n$ compuesto tiene siempre un divisor [primo](#def-b1-arith-prime) $\leq \sqrt n$. Por tanto, para comprobar si $n$ es [primo](#def-b1-arith-prime) basta probar los [primos](#def-b1-arith-prime) hasta $\sqrt n$. Para $n = 271$: $\sqrt{271} < 17$, y $271$ no es divisible por ninguno de $2, 3, 5, 7, 11, 13$ (es impar, su suma de cifras es $10$, no acaba en $0$ ni en $5$, y $271 = 7\cdot38 + 5 = 11\cdot24 + 7 = 13\cdot20 + 11$): [primo](#def-b1-arith-prime), tras seis divisiones en lugar de doscientas. La barrera $\sqrt n$ es un umbral real: cruzarla con eficacia para números de cien cifras exige los tests de primalidad modernos nacidos del [Teorema 6.23](#thm-b1-arith-fermat).

**Teorema 6.14 (Euclides).**

Hay infinitos [primos](#def-b1-arith-prime).

**Demostración.** Todo entero $n \geq 2$ tiene un divisor [primo](#def-b1-arith-prime): su menor divisor $\geq 2$ es [primo](#def-b1-arith-prime) (una factorización propia suya produciría un divisor menor de $n$). Supóngase ahora que $p_1, \dots, p_k$ fuesen todos los [primos](#def-b1-arith-prime) y sea $N = p_1 p_2 \cdots p_k + 1 \geq 2$. Algún [primo](#def-b1-arith-prime) $p_i$ [divide](#def-b1-arith-divides) a $N$; pero $p_i$ [divide](#def-b1-arith-divides) también a $N - 1 = p_1\cdots p_k$, luego $p_i \mid 1$ — absurdo. ∎

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

Todo entero $n \geq 2$ es un producto de [primos](#def-b1-arith-prime), y la factorización

$$
n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}
\qquad (p_1 < p_2 < \dots < p_k \text{ primos},\ \alpha_i \in \N^*)
$$

es única.

**Demostración.** *Existencia*, por inducción fuerte ([Teorema 1.12](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#thm-b1-logic-induction)): $n = 2$ es [primo](#def-b1-arith-prime); para $n > 2$, o bien $n$ es [primo](#def-b1-arith-prime), o bien $n = ab$ con $2 \leq a, b < n$, y la hipótesis de inducción factoriza $a$ y $b$.

*Unicidad.* Supóngase $p_1 \cdots p_r = q_1 \cdots q_s$ ([primos](#def-b1-arith-prime) enumerados con repetición, digamos $r \leq s$) y hágase inducción sobre $r$. Si $r = 0$, el miembro izquierdo es $1$, lo que obliga a $s = 0$ (un producto no vacío de [primos](#def-b1-arith-prime) supera a $1$). Para $r \geq 1$: el [primo](#def-b1-arith-prime) $p_1$ [divide](#def-b1-arith-divides) a $q_1(q_2\cdots q_s)$, luego, por el lema de Euclides, $p_1 \mid q_1$ o $p_1 \mid q_2\cdots q_s$; iterando, $p_1$ [divide](#def-b1-arith-divides) a algún $q_j$. Pero $q_j$ es [primo](#def-b1-arith-prime) y $p_1 \geq 2$: necesariamente $p_1 = q_j$. Cancélese este factor común (es legítimo: $\Z$ es un dominio de integridad) para obtener

$$
p_2 \cdots p_r = q_1 \cdots \widehat{q_j} \cdots q_s
$$

(el sombrero marca la omisión), una igualdad de productos más cortos; la hipótesis de inducción dice que las dos listas $p_2, \dots, p_r$ y $q_1, \dots, \widehat{q_j}, \dots, q_s$ coinciden salvo el orden, y por tanto también lo hacían las originales. La forma con exponentes agrupa los [primos](#def-b1-arith-prime) iguales. ∎

**Proposición 6.16 (Valuaciones).**

Para $p$ [primo](#def-b1-arith-prime) y $n \in \N^*$, escríbase $v_p(n)$ para el exponente de $p$ en la factorización de $n$ (con $v_p(n) = 0$ si $p \nmid n$). Entonces

$$
v_p(mn) = v_p(m) + v_p(n),
\qquad
m \mid n \iff \forall p,\ v_p(m) \leq v_p(n),
$$

$$
v_p\bigl(\gcd(m,n)\bigr) = \min\bigl(v_p(m), v_p(n)\bigr),
\qquad
v_p\bigl(\operatorname{lcm}(m,n)\bigr) = \max\bigl(v_p(m),
v_p(n)\bigr).
$$

**Demostración.** La primera identidad se cumple porque las factorizaciones se multiplican y la de $mn$ es única. Si $m \mid n$, escríbase $n = mq$ y aplíquese. Recíprocamente, si todos los $v_p(m) \leq v_p(n)$, el entero $q = \prod_p p^{\,v_p(n) - v_p(m)}$ cumple $mq = n$. Fórmula del mcd: el entero $d = \prod p^{\min}$ [divide](#def-b1-arith-divides) a los dos por el criterio, y todo divisor común $c$ cumple $v_p(c) \leq \min$ para todo $p$, luego $c \mid d$; el mismo razonamiento vale para el mcm con el $\max$. ∎

**Ejemplo 6.17 (Cuadrados y cubos a través de las valuaciones).**

Un entero $n \geq 1$ es un cuadrado perfecto si y solo si todos los $v_p(n)$ son pares (si $n = m^2$, entonces $v_p(n) = 2v_p(m)$; recíprocamente, divídase por la mitad cada exponente). Lo análogo vale para los cubos con múltiplos de $3$. Así, $21168 = 2^4 \times 3^3
\times 7^2$ no es un cuadrado ($v_3 = 3$ es impar) ni un cubo ($v_2 = 4$); el menor entero positivo $m$ tal que $21168\,m$ *sí* sea un cubo se halla completando cada exponente hasta el siguiente múltiplo de $3$:

$$
m = 2^{6-4} \times 3^{3-3} \times 7^{3-2} = 2^2 \times 7 = 28,
\qquad
21168 \times 28 = 2^6\,3^3\,7^3 = (2^2 \times 3 \times 7)^3
= 84^3 .
$$

La idea clave: las cuestiones multiplicativas (cuadrados, cubos, divisores, mcd, mcm) se vuelven cuestiones *coordenada a coordenada* sobre los vectores de exponentes $(v_2, v_3, v_5, \dots)$ — la factorización única es el [enunciado](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-statement) de que esas coordenadas existen y están bien definidas.

## 6.4 Congruencias

**Definición 6.18.**

Para $n \in \N^*$: $a \equiv b \pmod n$ cuando $n \mid a - b$. Es una [relación de equivalencia](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-equiv) compatible con la suma y el producto: si $a \equiv b$ y $a' \equiv b'$ (mód $n$), entonces $a + a' \equiv b + b'$, $aa' \equiv bb'$ y $a^k \equiv b^k$ para $k \in \N$.

**Ejemplo 6.19 (La prueba del nueve).**

La compatibilidad con $+$ y $\times$ es un método de comprobación tan viejo como el comercio. Como $10 \equiv 1 \pmod 9$, todo entero es congruente [módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) $9$ con la suma de sus cifras (se demuestra en el [Ejercicio 6.2](#exo-b1-arith-2)). Para comprobar la afirmación $1234 \times 567 = 699\,678$: las sumas de cifras dan $1234 \equiv 1$ y $567 \equiv 18 \equiv 0 \pmod 9$, luego el producto debe ser $\equiv 1 \times 0 = 0$; y, en efecto, $6 + 9 + 9 + 6 + 7 + 8 = 45
\equiv 0$. La comprobación pasa (y el producto es de hecho correcto). Si alguien hubiese dado $699\,478$, la suma de cifras $43 \equiv 7
\not\equiv 0$ lo delataría al instante. El test es de un solo sentido — caza el error salvo que el propio error sea múltiplo de $9$ —, que es exactamente la lección de los seudoprimos del [Ejemplo 6.24](#ex-b1-arith-pseudoprime) en miniatura: las comprobaciones por [congruencias](#def-b1-arith-congruence) refutan, no certifican.

**Proposición 6.20 (Invertibilidad módulo nnn).**

$a$ es *invertible [módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) $n$* (es decir, $ab \equiv 1 \pmod n$ para algún $b$) si y solo si $\gcd(a, n) = 1$. El inverso es entonces único [módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) $n$ y se calcula con el [algoritmo de Euclides](#met-b1-arith-euclid) extendido.

**Demostración.** $ab \equiv 1 \pmod n$ significa $ab + nk = 1$ para algún $k$: una relación de Bézout, que existe si y solo si $\gcd(a,n) = 1$ ([Corolario 6.5](#cor-b1-arith-bezout)). Unicidad: si $ab \equiv ab' \equiv 1$, entonces $b \equiv b(ab') = (ab)b' \equiv b' \pmod n$. ∎

**Ejemplo 6.21 (Invertir 777 módulo 262626).**

Como $\gcd(7, 26) = 1$, la clase de $7$ es invertible [módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) $26$. Euclides extendido:

$$
26 = 3 \times 7 + 5, \qquad
7 = 1 \times 5 + 2, \qquad
5 = 2 \times 2 + 1 ,
$$

y después hacia atrás:

$$
1 = 5 - 2 \times 2 = 5 - 2(7 - 5) = 3 \times 5 - 2 \times 7
= 3(26 - 3 \times 7) - 2 \times 7 = 3 \times 26 - 11 \times 7 .
$$

Por tanto $7 \times (-11) \equiv 1 \pmod{26}$, es decir, $7^{-1} \equiv -11 \equiv 15 \pmod{26}$; comprobación: $7 \times 15 = 105 = 4 \times 26 + 1$. Con el inverso en la mano, cualquier [congruencia](#def-b1-arith-congruence) $7x \equiv c \pmod{26}$ se resuelve con una multiplicación: $x \equiv 15c$. Esta inversión mecánica es el caballo de batalla de la aritmética modular — y de los protocolos de clave pública mencionados en el [Observación 6.27](#rem-b1-arith-whereused), donde los [módulos](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) tienen cientos de cifras pero el algoritmo es exactamente este.

**Ejemplo 6.22 (Cuando el coeficiente no es invertible).**

Resuélvase $12x \equiv 8 \pmod{20}$. Aquí $\gcd(12, 20) = 4$, así que $12$ no es invertible [módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) $20$ — pero la ecuación sigue siendo tratable. La [congruencia](#def-b1-arith-congruence) dice que $20 \mid 12x - 8$; dividiendo toda la relación por $4$ (divisor de los tres ingredientes), equivale a $5 \mid 3x - 2$, es decir,

$$
3x \equiv 2 \pmod 5 .
$$

Ahora $\gcd(3, 5) = 1$ y $3^{-1} \equiv 2 \pmod 5$ ($3 \times 2 = 6
\equiv 1$), luego $x \equiv 4 \pmod 5$: las soluciones son $x \equiv 4, 9, 14, 19 \pmod{20}$ — *cuatro* clases [módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) $20$, tantas como el mcd. (Si el miembro derecho no hubiese sido divisible por $4$, por ejemplo $12x \equiv 6 \pmod{20}$, no habría ninguna solución: el miembro izquierdo es siempre $\equiv 0 \pmod 4$.) Forma general: $ax \equiv b \pmod n$ tiene solución si y solo si $\gcd(a, n) \mid b$, y entonces tiene exactamente $\gcd(a, n)$ clases de soluciones — divídase todo por el mcd e inviértase.

**Teorema 6.23 (Pequeño teorema de Fermat).**

Sea $p$ [primo](#def-b1-arith-prime). Para todo $a \in \Z$:

$$
a^p \equiv a \pmod p,
$$

y, si $p \nmid a$, entonces $a^{p-1} \equiv 1 \pmod
p$.

**Demostración.** Primero, para $1 \leq k \leq p - 1$, el [coeficiente binomial](https://one-course.com/books/math/3/es/chapter/2-combinatoria#def-b1-counting-objects) $\binom pk = \frac{p!}{k!(p-k)!}$ es divisible por $p$: en efecto, $k!\,(p-k)!\,\binom pk = p!$ y $p$ [divide](#def-b1-arith-divides) a $p!$ pero es [coprimo](#cor-b1-arith-bezout) con $k!(p-k)!$ (todos sus factores son $< p$), luego el lema de Gauss da $p \mid \binom pk$.

Pruébese ahora $a^p \equiv a$ para $a \in \N$ por inducción. Cierto para $a = 0$. Si $a^p \equiv a$, entonces, por el teorema del binomio,

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

anulándose [módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) $p$ todos los términos intermedios. Para $a < 0$, aplíquese el resultado a $-a$ y sepárese $p = 2$ (donde $x \equiv -x$) de $p$ impar (donde $(-a)^p = -a^p$). Por último, si $p \nmid a$, multiplíquese $a^p \equiv a$ por un inverso de $a$ [módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) $p$ ([Proposición 6.20](#prop-b1-arith-invmod)). ∎

**Ejemplo 6.24 (El recíproco de Fermat falla: 341341341).**

El pequeño teorema de Fermat da un test barato de *composición*: si $a^{n-1} \not\equiv 1 \pmod n$ para algún $a$ [coprimo](#cor-b1-arith-bezout) con $n$, entonces $n$ no es [primo](#def-b1-arith-prime). ¿Podría el test certificar también la primalidad? No: tómese $n = 341 = 11 \times 31$, compuesto, y $a = 2$. Como $2^{10} = 1024 = 3 \times 341 + 1$,

$$
2^{10} \equiv 1 \pmod{341}
\qquad\Longrightarrow\qquad
2^{340} = \bigl(2^{10}\bigr)^{34} \equiv 1 \pmod{341} :
$$

el compuesto $341$ pasa el test de Fermat en base $2$ (es el menor *seudoprimo* de esta clase). La base $3$ lo desenmascara ($3^{340} \not\equiv 1$), y por eso los tests de primalidad prácticos se ejecutan en varias bases, además de con refinamientos — las versiones industriales de esta idea son las que certifican los grandes [primos](#def-b1-arith-prime) del [Observación 6.27](#rem-b1-arith-whereused). Moraleja: una implicación y su recíproca llevan vidas separadas ([Observación 1.10](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#rem-b1-logic-pitfalls)), incluso tratándose de teoremas.

**Ejemplo 6.25 (Cálculos prácticos con congruencias).**

¿Cuál es el resto de $7^{2026}$ [módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) $11$? Por Fermat, $7^{10} \equiv 1 \pmod{11}$. Como $2026 = 10 \times 202 + 6$:

$$
7^{2026} \equiv 7^6 = (7^2)^3 = 49^3 \equiv 5^3 = 125 \equiv 4
\pmod{11}.
$$

El resto es $4$. La estrategia: redúzcase el exponente [módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) el orden que proporciona Fermat y redúzcanse las potencias intermedias en cada paso.

**Observación 6.26 (Errores frecuentes en aritmética).**

1. *Dividir una [congruencia](#def-b1-arith-congruence).* De $ac \equiv bc \pmod n$ *no* se puede concluir $a \equiv b$ salvo si $\gcd(c, n) = 1$ : $6 \equiv 2 \pmod 4$ , pero $3 \not\equiv 1 \pmod 4$ . La regla general correcta [divide](#def-b1-arith-divides) también el [módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) : $ac \equiv bc \pmod n \iff a  \equiv b \pmod{n/\gcd(c,n)}$ .
2. *Usar mal el lema de Euclides.* $a \mid bc$ implica $a \mid b$ o $a \mid c$ solo para $a$ *[primo](#def-b1-arith-prime)* (o [coprimo](#cor-b1-arith-bezout) con uno de los factores): $6 \mid 4 \times 9$ y, sin embargo, $6$ no [divide](#def-b1-arith-divides) a ninguno de los dos.
3. *[Coprimo](#cor-b1-arith-bezout) es una relación, no una propiedad.* « $8$ y $9$ son [coprimos](#cor-b1-arith-bezout) » es cierto aunque ninguno sea [primo](#def-b1-arith-prime) ; « [coprimos](#cor-b1-arith-bezout) dos a dos» es más fuerte que « [coprimos](#cor-b1-arith-bezout) en [conjunto](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-sets) » ( $\gcd(6, 10, 15) = 1$ , pero ningún par es [coprimo](#cor-b1-arith-bezout) ).
4. *Los exponentes no viven [módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) $n$.* En $a^k \bmod n$ , el exponente solo se puede reducir [módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) el *orden* de $a$ (por ejemplo, $p - 1$ cuando se aplica Fermat), nunca [módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) $n$ : $2^{10} \bmod 11$ vale $1$ , no $2^{10 \bmod 11} = 2^{10}$ — la reducción que sí funciona es la que hace el [Ejemplo 6.25](#ex-b1-arith-congruences) .

**Observación 6.27 (Dónde se usa este capítulo).**

Este capítulo es tanto una plantilla como una caja de herramientas. Toda la cadena — división euclídea, mcd, Bézout, Gauss, factorización única — se repite literalmente para los polinomios en el [Capítulo 8](https://one-course.com/books/math/3/es/chapter/8-polinomios#ch-b1-poly), donde el «grado» hace el papel del valor absoluto; comparar los dos capítulos en paralelo es la mejor manera de entender ambos. El cálculo de [congruencias](#def-b1-arith-congruence) se convierte en el anillo $\Z/n\Z$ en el [Capítulo 7](https://one-course.com/books/math/3/es/chapter/7-estructuras-algebraicas#ch-b1-structures), cuyos elementos invertibles ([Proposición 6.20](#prop-b1-arith-invmod)) forman el primer ejemplo no trivial de grupo de unidades. Las valuaciones vuelven en el problema del fin de semana (fórmula de Legendre) y sostienen las demostraciones de irracionalidad del [Capítulo 10](https://one-course.com/books/math/3/es/chapter/10-numeros-reales#ch-b1-reals). Más allá de este volumen, la inversión de Bézout [módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) $n$ es el motor de la criptografía de clave pública, y el pequeño teorema de Fermat es el abuelo de los tests de primalidad que certifican los grandes [primos](#def-b1-arith-prime) que allí se usan.

**Observación 6.28 (Interludio: Z\ZZ como plantilla).**

Tómese distancia de los teoremas concretos y obsérvese la arquitectura del capítulo: una herramienta (la división euclídea) produjo una clasificación (los subgrupos $n\Z$), que produjo un teorema de existencia (mcd, Bézout), que produjo un cálculo de [divisibilidad](#def-b1-arith-divides) (Gauss), que produjo la factorización única — cada piso apoyado únicamente en el inmediatamente inferior. El mismo edificio se levantará dos veces más en este volumen con plantas bajas distintas: en el [Capítulo 8](https://one-course.com/books/math/3/es/chapter/8-polinomios#ch-b1-poly), donde dividir por el grado sustituye a dividir por el tamaño y todo lo de arriba se repite *literalmente*; y, en miniatura, dentro de cada $\Z/n\Z$ del [Capítulo 7](https://one-course.com/books/math/3/es/chapter/7-estructuras-algebraicas#ch-b1-structures), donde las cuestiones de invertibilidad (la [Proposición 6.20](#prop-b1-arith-invmod) de este capítulo) se vuelven [enunciados](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-statement) estructurales sobre anillos y cuerpos. Reconocer un argumento como «el argumento de $\Z$, trasplantado» es la forma más rápida de aprender esos capítulos — y el primer sabor del hábito central del álgebra: demostrar teoremas sobre *axiomas* y no sobre objetos.

![Filas 0 a 7 del triángulo de Pascal con las entradas impares rellenas: la fila n contiene 2s_2(n) de ellas, donde s_2(n) es el número de unos de la escritura binaria de n (filas 1, 2, 4: dos entradas impares; fila 7 = (111)_2: las ocho). El patrón autosemejante — cada «triángulo de impares» engendra dos copias de sí mismo — es el teorema de Kummer en forma de imagen, demostrado en el problema del fin de semana.](https://one-course.com/images/onecourse/chapters/math-3/b1-arith/fig-8546c89fa14c.svg)

*Filas $0$ a $7$ del triángulo de Pascal con las entradas *impares* rellenas: la fila $n$ contiene $2^{s_2(n)}$ de ellas, donde $s_2(n)$ es el número de unos de la escritura binaria de $n$ (filas $1, 2, 4$: dos entradas impares; fila $7 = (111)_2$: las ocho). El patrón autosemejante — cada «triángulo de impares» engendra dos copias de sí mismo — es el teorema de Kummer en forma de imagen, demostrado en el problema del fin de semana.*

## 6.5 Ejercicios

**Ejercicio 6.1 ★.**

Calcúlese $\gcd(1\,001, 777)$ con el [algoritmo de Euclides](#met-b1-arith-euclid), y un par de Bézout para él.

**Solución de Ejercicio 6.1.**

$1001 = 1 \times 777 + 224$; $777 = 3 \times 224 + 105$; $224 = 2 \times 105 + 14$; $105 = 7 \times 14 + 7$; $14 = 2 \times 7 + 0$. Luego $\gcd(1001, 777) = 7$. Hacia atrás:

$$
7 = 105 - 7 \times 14
= 105 - 7(224 - 2\times 105) = 15 \times 105 - 7 \times 224
$$

$$
= 15(777 - 3\times 224) - 7\times 224 = 15 \times 777 - 52 \times 224
= 15 \times 777 - 52(1001 - 777) = 67 \times 777 - 52 \times 1001 .
$$

Comprobación: $67 \times 777 = 52\,059$ y $52 \times 1001 = 52\,052$; la diferencia es $7$. Par de Bézout: $(u, v) = (-52, 67)$ para $1001u + 777v = 7$.

**Ejercicio 6.2 ★.**

Demuéstrense los criterios de [divisibilidad](#def-b1-arith-divides) en base $10$: un entero es congruente [módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) $9$ con la suma de sus cifras, y [módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) $11$ con la suma alternada de sus cifras. ¿Cuánto vale $123\,456\,789$ [módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) $9$ y [módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) $11$?

**Solución de Ejercicio 6.2.**

Como $10 \equiv 1 \pmod 9$: $10^k \equiv 1$, luego $\sum_k d_k 10^k
\equiv \sum_k d_k \pmod 9$. Como $10 \equiv -1 \pmod{11}$: $10^k
\equiv (-1)^k$, luego el entero es congruente con la suma alternada $\sum_k (-1)^k d_k$ [módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) $11$ (empezando por la cifra de las *unidades* con signo $+$).

$123\,456\,789$: suma de cifras $45 \equiv 0 \pmod 9$. Suma alternada desde las unidades: $9 - 8 + 7 - 6 + 5 - 4 + 3 - 2 + 1 = 5$, luego el número es $\equiv 5 \pmod{11}$.

**Ejercicio 6.3 ★.**

Resuélvase en $\Z$: $91x \equiv 1 \pmod{237}$ *(Euclides extendido)*.

**Solución de Ejercicio 6.3.**

Euclides: $237 = 2 \times 91 + 55$; $91 = 1 \times 55 + 36$; $55 = 1 \times 36 + 19$; $36 = 1 \times 19 + 17$; $19 = 1 \times 17 + 2$; $17 = 8 \times 2 + 1$. Hacia atrás:

$$
1 = 17 - 8\times 2 = 17 - 8(19 - 17) = 9\times 17 - 8\times 19
= 9(36 - 19) - 8\times 19 = 9\times 36 - 17\times 19
$$

$$
= 9\times 36 - 17(55 - 36) = 26\times 36 - 17\times 55
= 26(91 - 55) - 17\times 55 = 26\times 91 - 43\times 55
$$

$$
= 26\times 91 - 43(237 - 2\times 91) = 112 \times 91 - 43 \times 237.
$$

Así pues, $91 \times 112 \equiv 1 \pmod{237}$: las soluciones son $x \equiv 112 \pmod{237}$. (Comprobación: $91 \times 112 = 10\,192 = 43 \times 237 + 1$.)

**Ejercicio 6.4 ★.**

Hállense todos los pares $(x, y) \in \Z^2$ con $17x + 39y = 1$; y después todos los pares con $17 x + 39 y = 5$.

**Solución de Ejercicio 6.4.**

$\gcd(17, 39) = 1$: Euclides da $39 = 2\times 17 + 5$, $17 = 3\times 5 + 2$, $5 = 2\times 2 + 1$, y hacia atrás

$$
1 = 5 - 2\times 2 = 5 - 2(17 - 3\times 5) = 7\times 5 - 2\times 17
= 7(39 - 2\times 17) - 2\times 17 = 7\times 39 - 16\times 17 .
$$

Solución particular $(x_0, y_0) = (-16, 7)$. Solución general de la ecuación homogénea $17x + 39y = 0$: $x = 39k$, $y = -17k$ (pues $17 \mid 39y$ y $\gcd(17,39) = 1$ obligan a $17 \mid y$ — lema de Gauss). Por tanto

$$
(x, y) = (-16 + 39k,\; 7 - 17k), \qquad k \in \Z .
$$

Para el miembro derecho $5$, multiplíquese por $5$ la solución particular: $(x, y) = (-80 + 39k,\; 35 - 17k)$, $k \in \Z$.

**Ejercicio 6.5 ★★.**

Demuéstrese que, para $a, b \in \N^*$, $\gcd(a,b) \times
\operatorname{lcm}(a,b) = ab$. *(Úsense las fórmulas de valuación de la [Proposición 6.16](#prop-b1-arith-valuation) y $\min(\alpha,\beta) + \max(\alpha,\beta) = \alpha + \beta$.)*

**Solución de Ejercicio 6.5.**

Para todo [primo](#def-b1-arith-prime) $p$, con $\alpha = v_p(a)$ y $\beta = v_p(b)$:

$$
v_p\bigl(\gcd(a,b)\bigr) + v_p\bigl(\operatorname{lcm}(a,b)\bigr)
= \min(\alpha, \beta) + \max(\alpha, \beta)
= \alpha + \beta = v_p(ab) .
$$

Dos enteros positivos con la misma valuación en todo [primo](#def-b1-arith-prime) son iguales ([Proposición 6.16](#prop-b1-arith-valuation)), luego $\gcd(a,b)\operatorname{lcm}(a,b) = ab$.

**Ejercicio 6.6 ★★.**

Sean $a = 2^{10} \times 3^4 \times 5^2$ y $b = 2^6 \times 3^7 \times
7$. Calcúlense $\gcd(a, b)$, $\operatorname{lcm}(a,b)$ y el número de divisores positivos de $a$. *(Demuéstrese la fórmula del número de divisores $\prod_i (\alpha_i + 1)$.)*

**Solución de Ejercicio 6.6.**

Valuaciones: $\gcd(a, b) = 2^{\min(10,6)} 3^{\min(4,7)} 5^{\min(2,0)}
7^{\min(0,1)} = 2^6\, 3^4 = 5184$; $\operatorname{lcm}(a,b) = 2^{10}\, 3^7\, 5^2\, 7$.

Número de divisores: un divisor positivo de $n = \prod p_i^{\alpha_i}$ es exactamente una elección $\prod p_i^{\beta_i}$ con $0 \leq \beta_i \leq \alpha_i$ ([Proposición 6.16](#prop-b1-arith-valuation)); las elecciones son independientes, luego hay $\prod_i (\alpha_i + 1)$ divisores. Para $a$: $(10+1)(4+1)(2+1) = 165$.

**Ejercicio 6.7 ★★.**

Demuéstrese que $\sqrt p$ es irracional para todo [primo](#def-b1-arith-prime) $p$, usando valuaciones: compárese $v_p$ en los dos miembros de $p q^2 = r^2$.

**Solución de Ejercicio 6.7.**

Supóngase $\sqrt p = \frac rq$ con $r, q \in \N^*$, es decir, $p q^2 = r^2$. Aplíquese $v_p$: $v_p(pq^2) = 1 + 2v_p(q)$ es impar, mientras que $v_p(r^2) = 2 v_p(r)$ es par. Un entero no puede tener a la vez valuación $p$-ádica par e impar: contradicción. Luego $\sqrt p \notin \Q$.

**Ejercicio 6.8 ★★.**

(Problema chino de los restos) Hállense todos los enteros $x$ con

$$
x \equiv 2 \pmod 7, \qquad x \equiv 5 \pmod{11}.
$$

Demuéstrese de paso que, para $m, n$ [coprimos](#cor-b1-arith-bezout), el par de [congruencias](#def-b1-arith-congruence) $x \equiv a \ (m)$, $x \equiv b\ (n)$ tiene siempre solución, única [módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) $mn$.

**Solución de Ejercicio 6.8.**

*Hecho general.* Con $\gcd(m,n) = 1$, Bézout da $mu + nv = 1$. Póngase $x_0 = b\,mu + a\,nv$. Entonces $x_0 \equiv a\,nv \equiv
a(1 - mu) \equiv a \pmod m$ y, análogamente, $x_0 \equiv b \pmod n$: existencia. Si $x$ y $x'$ son dos soluciones, $m$ y $n$ [dividen](#def-b1-arith-divides) a $x - x'$, luego $mn \mid x - x'$ ([Teorema 6.8](#thm-b1-arith-gauss) (2)): unicidad [módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) $mn$.

*Numéricamente:* $m = 7$, $n = 11$: $7 \times (-3) + 11 \times 2 =
1$. Luego $x_0 = 5 \times 7 \times (-3) + 2 \times 11 \times 2 = -105 +
44 = -61 \equiv 16 \pmod{77}$. Comprobación: $16 = 2\times 7 + 2
\equiv 2 \pmod 7$; $16 = 11 + 5 \equiv 5 \pmod{11}$. Soluciones: $x \equiv 16 \pmod{77}$.

**Ejercicio 6.9 ★★.**

Calcúlese $3^{1000}$ [módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) $7$, y las dos últimas cifras decimales de $7^{100}$ *([módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) $100 = 4 \times 25$: úsese el [Ejercicio 6.8](#exo-b1-arith-8))*.

**Solución de Ejercicio 6.9.**

[Módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) $7$: Fermat da $3^6 \equiv 1$, y $1000 = 6 \times 166 + 4$, luego $3^{1000} \equiv 3^4 = 81 \equiv 4 \pmod 7$.

Dos últimas cifras de $7^{100}$: trabájese [módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) $4$ y [módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) $25$. [Módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) $4$: $7 \equiv -1$, luego $7^{100} \equiv 1$. [Módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) $25$: $7^2 = 49 \equiv -1$, luego $7^4 \equiv 1$ y $7^{100} = (7^4)^{25} \equiv 1$. Por el teorema chino del resto ([Ejercicio 6.8](#exo-b1-arith-8)), $7^{100} \equiv 1 \pmod{100}$: las dos últimas cifras son $01$.

**Ejercicio 6.10 ★★★.**

Para $m, n \in \N^*$, demuéstrese que $\gcd(2^m - 1,\, 2^n - 1) =
2^{\gcd(m,n)} - 1$. *Indicación: véase primero que el resto de $2^m - 1$ [módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) $2^n - 1$ es $2^r - 1$, donde $r$ es el resto de $m$ [módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) $n$; síganse después los pasos del [algoritmo de Euclides](#met-b1-arith-euclid).*

**Solución de Ejercicio 6.10.**

Escríbase $m = nq + r$, $0 \leq r < n$. Entonces

$$
2^m - 1 = 2^r\bigl(2^{nq} - 1\bigr) + 2^r - 1,
$$

y $2^n - 1$ [divide](#def-b1-arith-divides) a $2^{nq} - 1 = (2^n - 1)(2^{n(q-1)} + \dots +
1)$. Así pues, [módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) $2^n - 1$ se tiene $\;2^m - 1 \equiv 2^r - 1$ y, como $0 \leq 2^r - 1 < 2^n - 1$, este *es* el resto euclídeo.

Por tanto, el [algoritmo de Euclides](#met-b1-arith-euclid) sobre el par $(2^m - 1, 2^n - 1)$ reproduce, exponente a exponente, el algoritmo sobre $(m, n)$: cada paso de división sustituye $(m, n)$ por $(n, r)$ arriba y $(2^m - 1, 2^n - 1)$ por $(2^n - 1, 2^r - 1)$ abajo. Arriba el algoritmo termina en $\gcd(m,n)$, luego abajo termina en $2^{\gcd(m,n)} - 1$.

**Ejercicio 6.11 ★★★.**

(Teorema de Wilson) Sea $p$ un [primo](#def-b1-arith-prime). Demuéstrese que

$$
(p-1)! \equiv -1 \pmod p ,
$$

emparejando cada factor de $(p-1)!$ con su inverso [módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) $p$ e identificando los factores emparejados consigo mismos (resuélvase antes $x^2 \equiv 1 \pmod p$). Compruébese el recíproco: si $n \geq 2$ no es [primo](#def-b1-arith-prime), entonces $(n-1)! \not\equiv -1 \pmod n$.

**Solución de Ejercicio 6.11.**

Resuélvase primero $x^2 \equiv 1 \pmod p$: $p \mid (x-1)(x+1)$, luego, por el lema de Euclides, $x \equiv 1$ o $x \equiv -1 \pmod p$.

En el producto $(p-1)! = 1 \times 2 \times \dots \times (p-1)$, todo factor $a$ es invertible [módulo](https://one-course.com/books/math/3/es/chapter/3-numeros-complejos#def-b1-complex-field) $p$, y su inverso $a^{-1}$ es de nuevo uno de los factores ([Proposición 6.20](#prop-b1-arith-invmod)). Emparéjese cada $a$ con $a^{-1}$: cada pareja multiplica a $1$, salvo los factores emparejados consigo mismos ($a = a^{-1}$, es decir, $a^2 \equiv 1$), que quedan solos — y esos son exactamente $1$ y $p - 1$. Por tanto

$$
(p-1)! \equiv 1 \times (p - 1) \equiv -1 \pmod p .
$$

(Para $p = 2$: $1! = 1 \equiv -1 \pmod 2$; el argumento del emparejamiento degenera, pero el resultado se mantiene.)

*Recíproco.* Sea $n \geq 2$ compuesto, $n = ab$ con $1 < a \leq b < n$. Si $a < b$, los dos aparecen como factores distintos de $(n-1)!$, luego $n \mid (n-1)!$ y $(n-1)! \equiv 0 \not\equiv -1$. Si $a = b$ (es decir, $n = a^2$): para $a \geq 3$, tanto $a$ como $2a$ son $< n$, luego $n = a^2 \mid a \times 2a \mid (n-1)!$, misma conclusión; y para $n = 4$, $(n-1)! = 6 \equiv 2 \not\equiv -1 \pmod 4$.

**Ejercicio 6.12 ★★★.**

(Números de Fermat) Para $n \in \N$, sea $F_n = 2^{2^n} + 1$.

1. Demuéstrese que $F_0 F_1 \cdots F_{n-1} = F_n - 2$ para $n \geq 1$ (inducción).
2. Dedúzcase que los números de Fermat son [coprimos](#cor-b1-arith-bezout) dos a dos.
3. Dedúzcase una segunda demostración, independiente del [Teorema 6.14](#thm-b1-arith-euclidprimes) , de que hay infinitos [primos](#def-b1-arith-prime) .

**Solución de Ejercicio 6.12.**

1. Inducción. Para $n = 1$: $F_0 = 3 = F_1 - 2 = 5 - 2$. Suponiendo $F_0\cdots F_{n-1} = F_n - 2$: $$F_0 \cdots F_n = (F_n - 2)F_n  = \bigl(2^{2^n} - 1\bigr)\bigl(2^{2^n} + 1\bigr)  = 2^{2^{n+1}} - 1 = F_{n+1} - 2 .$$
2. Sean $m < n$ y $d = \gcd(F_m, F_n)$ . Por (1), $F_m$ [divide](#def-b1-arith-divides) a $F_n - 2$ , luego $d$ [divide](#def-b1-arith-divides) a la vez a $F_n$ y a $F_n - 2$ , y por tanto [divide](#def-b1-arith-divides) a $2$ . Pero todo número de Fermat es impar, luego $d = 1$ .
3. Cada $F_n \geq 3$ tiene un divisor [primo](#def-b1-arith-prime) $p_n$ (primer paso del [Teorema 6.14](#thm-b1-arith-euclidprimes) ). Si $m \neq n$ , entonces $p_m \neq p_n$ , pues un [primo](#def-b1-arith-prime) común dividiría a $\gcd(F_m, F_n) = 1$ . La [aplicación](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-map) $n \mapsto p_n$ es, por tanto, [inyectiva](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) de $\N$ en los [primos](#def-b1-arith-prime) : hay infinitos [primos](#def-b1-arith-prime) .

## 6.6 Problema: la fórmula de Legendre y los acarreos de Kummer

**Problema 6.1.**

¿En cuántos ceros termina la escritura decimal de $1000!$ y, más a fondo, cuál es la potencia exacta de un [primo](#def-b1-arith-prime) $p$ que [divide](#def-b1-arith-divides) a $n!$, o que [divide](#def-b1-arith-divides) a un [coeficiente binomial](https://one-course.com/books/math/3/es/chapter/2-combinatoria#def-b1-counting-objects)? Las respuestas completas son dos joyas de la aritmética elemental: la *fórmula de Legendre* $v_p(n!) = \sum_{k\geq1}
\lfloor n/p^k \rfloor$, con su avatar digital $v_p(n!) = \frac{n
- s_p(n)}{p-1}$, y el *teorema de Kummer*: $v_p\binom{m+n}m$ cuenta los *acarreos* al sumar $m$ y $n$ en base $p$. Este problema demuestra los dos, los contrasta numéricamente entre sí y recolecta las consecuencias clásicas — ceros finales, paridad del triángulo de Pascal y una primera cota en la dirección del teorema de los [números primos](#def-b1-arith-prime). En todo el problema, $p$ es un [primo](#def-b1-arith-prime), $\floor{x}$ es la parte entera y $s_p(n)$ denota la suma de las cifras de $n$ escrito en base $p$.

**Parte I — Partes enteras, valuaciones y fórmula de Legendre.**

1. Calentamiento: calcúlese $10!$ y léase su número de ceros finales; calcúlense $v_2(10!)$ y $v_5(10!)$ directamente a partir de la factorización de cada factor $1, 2, \dots, 10$ .
2. Demuéstrese que, para $x \in \R$ y $n \in \N^*$ , $\bigl\lfloor \lfloor x \rfloor / n \bigr\rfloor =  \lfloor x/n \rfloor$ .
3. Demuéstrese que $v_p(a + b) \geq \min\bigl(v_p(a),  v_p(b)\bigr)$ para todos $a, b \in \N^*$ , con igualdad siempre que $v_p(a) \neq v_p(b)$ .
4. Pruébese que el número de múltiplos de $m$ en $\intint1n$ es $\lfloor n/m \rfloor$ .
5. Demuéstrese la *fórmula de Legendre*: para todo $n \in \N^*$, $$v_p(n!) = \sum_{k=1}^{\infty}  \Bigl\lfloor \frac{n}{p^k} \Bigr\rfloor$$ (una suma finita: los términos se anulan en cuanto $p^k > n$). *Cuéntense, para cada $k$, los factores de $\intint1n$ divisibles por $p^k$: cada uno aporta exactamente una unidad por cada nivel al que llega.*

**Parte II — La forma digital y los ceros finales.**

6. Calcúlense $v_5(1000!)$ y $v_2(1000!)$ y conclúyase: ¿en cuántos ceros termina $1000!$ ?
7. Demuéstrese la forma digital de la fórmula de Legendre: escribiendo $n = \sum_i a_i p^i$ en base $p$, $$v_p(n!) = \frac{n - s_p(n)}{p - 1} .$$
8. Dos consecuencias para $p = 2$ : pruébese que $2^n$ nunca [divide](#def-b1-arith-divides) a $n!$ , y que $2^{n-1}$ [divide](#def-b1-arith-divides) a $n!$ exactamente cuando $n$ es una potencia de $2$ .
9. Acótese el defecto: pruébese que $\frac n{p-1} - \log_p(n) - 1  \leq v_p(n!) < \frac n{p-1}$ , de modo que $\frac{v_p(n!)}{n} \to \frac1{p-1}$ : a la larga, se acumula una proporción $\frac1{p-1}$ de un factor $p$ por unidad.
10. Sea $Z(n) = v_5(n!)$ el número de ceros finales de $n!$ . Pruébese que $Z(n) - Z(n-1) = v_5(n)$ , dedúzcase que $Z$ se salta por completo el valor $5$ (calcúlense $Z(24)$ y $Z(25)$ ) y demuéstrese que ningún factorial termina en exactamente cinco ceros.

**Parte III — El teorema de Kummer.**

11. Demuéstrese que $\lfloor x + y \rfloor - \lfloor x \rfloor -  \lfloor y \rfloor \in \{0, 1\}$ para todos $x, y \in \R$, y dedúzcase de la fórmula de Legendre que $$v_p\binom{m+n}m  = \sum_{k\geq1}\Bigl(  \Bigl\lfloor\frac{m+n}{p^k}\Bigr\rfloor  - \Bigl\lfloor\frac{m}{p^k}\Bigr\rfloor  - \Bigl\lfloor\frac{n}{p^k}\Bigr\rfloor\Bigr),$$ una suma de términos iguales cada uno a $0$ o a $1$.
12. Demuéstrese el *teorema de Kummer* : el $k$ -ésimo término de esa suma vale $1$ exactamente cuando la suma de $m$ y $n$ en base $p$ produce un acarreo en la posición $k$ ; por tanto, $v_p\binom{m+n}m$ es el número total de acarreos. *(Escríbanse $m = p^km_1 + m_0$ y $n = p^kn_1 + n_0$ con $0 \leq m_0, n_0 < p^k$ y examínese $\lfloor (m_0 +  n_0)/p^k \rfloor$.)*
13. Dedúzcase que, para $0 < j < p^k$: $$v_p\binom{p^k}{j} = k - v_p(j) ,$$ contando los acarreos de la suma $j + (p^k - j)$. (En particular, $p \mid \binom p j$ para $0 < j < p$: el paso clave del [Teorema 6.23](#thm-b1-arith-fermat), recuperado.)
14. Demuéstrese que $v_2\binom{2n}n = s_2(n)$ . Dedúzcase que el [coeficiente binomial](https://one-course.com/books/math/3/es/chapter/2-combinatoria#def-b1-counting-objects) central es siempre par, y que $\binom{2n}n \equiv 2 \pmod 4$ exactamente cuando $n$ es una potencia de $2$ .
15. Pruébese, usando la identidad de Vandermonde ( [Ejercicio 2.7](https://one-course.com/books/math/3/es/chapter/2-combinatoria#exo-b1-counting-7) ) y la pregunta 13, que $\binom{2p}p \equiv 2 \pmod p$ para todo [primo](#def-b1-arith-prime) $p$ .
16. Calcúlese $v_3\binom{1000}{500}$ de dos maneras: una por Kummer (escríbase $500$ en base $3$ y cuéntense los acarreos de $500 + 500$ ) y otra por la forma digital de Legendre (calcúlense $s_3(500)$ y $s_3(1000)$ ); compruébese que las dos dan el mismo valor.

**Parte IV — La paridad del triángulo de Pascal y una cota de densidad de [primos](#def-b1-arith-prime).**

17. Demuéstrese el criterio de las cifras: $\binom nk$ es *impar* si y solo si cada cifra binaria de $k$ es menor o igual que la cifra correspondiente de $n$ . Enúnciese y demuéstrese el criterio análogo para $p \nmid \binom nk$ en base $p$ .
18. Dedúzcase que la fila $n$ del triángulo de Pascal contiene exactamente $2^{s_2(n)}$ entradas impares; compruébese en las filas $4$ y $5$ .
19. Dedúzcase que todas las entradas interiores $\binom nk$ ( $0 < k < n$ ) son pares si y solo si $n$ es una potencia de $2$ .
20. Demuéstrese que toda potencia de un [primo](#def-b1-arith-prime) que divida a $\binom{m+n}m$ es a lo sumo $m + n$ : si $p^a \mid \binom{m+n}m$ , entonces $p^a \leq m + n$ . *(¿Cuántos términos no nulos puede tener la suma de la pregunta 11?)*
21. Dedúzcase que $\binom{2n}n$ [divide](#def-b1-arith-divides) a $\operatorname{lcm}(1, 2, \dots, 2n)$ y combínese con la cota inferior $\binom{2n}n \geq \frac{4^n}{2n+1}$ (que se demostrará: la entrada central es la mayor de las $2n + 1$ entradas de la fila $2n$) para obtener $$\operatorname{lcm}(1, \dots, 2n) \geq \frac{4^n}{2n+1} :$$ los múltiplos comunes de los primeros enteros crecen *exponencialmente* — un primer atisbo cuantitativo de la abundancia de [primos](#def-b1-arith-prime).

**Parte V — Síntesis.**

22. Hállese el menor $n$ tal que $n!$ termine en al menos $2026$ ceros. *(Estímese $Z(n) \approx n/4$ y ajústese después con la fórmula exacta.)*
23. Una última comprobación cruzada: pruébese que $7$ *no* [divide](#def-b1-arith-divides) a $\binom{100}{50}$ , primero escribiendo $50$ en base $7$ y comprobando que la suma $50 + 50$ no tiene acarreos, y después calculando $v_7(100!)$ y $v_7(50!)$ con la fórmula de Legendre.
24. ¿Dónde ha usado exactamente el problema: (i) la factorización única; (ii) la descomposición por división euclídea $n = p^k n_1 + n_0$ ; (iii) un argumento combinatorio del [Capítulo 2](https://one-course.com/books/math/3/es/chapter/2-combinatoria#ch-b1-counting) ? Una frase para cada uno.
25. Síntesis, en un párrafo breve: la fórmula de Legendre convierte una cuestión de [divisibilidad](#def-b1-arith-divides) en aritmética de cifras, y el teorema de Kummer lee la respuesta en los acarreos de una sola suma — coméntese esta traducción, las comprobaciones de la pregunta 16 y lo que la cota de la pregunta 21 sugiere sobre los [primos](#def-b1-arith-prime) (el [enunciado](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-statement) completo, el teorema de los [números primos](#def-b1-arith-prime) , queda muy lejos de este volumen; el análogo polinómico de las herramientas de este capítulo es el [Capítulo 8](https://one-course.com/books/math/3/es/chapter/8-polinomios#ch-b1-poly) ).

**Solución de Problema 6.1.**

**1.** $10! = 3\,628\,800$: dos ceros finales. Valuaciones factor a factor: las potencias de $2$ vienen de $2, 4 = 2^2, 6, 8 = 2^3, 10$, en total $v_2(10!) = 1 + 2 + 1 + 3 + 1 = 8$; las de $5$, de $5$ y $10$: $v_5(10!) = 2$. Ceros finales $= \min(v_2, v_5) = 2$, coherente.

**2.** Escríbase la división euclídea $\lfloor x\rfloor = nq + r$, $0 \leq r \leq n - 1$. Entonces $x = nq + r + \{x\}$ con $0 \leq r + \{x\} < n$, luego $\lfloor x/n \rfloor = q = \bigl\lfloor \lfloor x \rfloor / n \bigr\rfloor$.

**3.** Sean $\alpha = v_p(a) \leq \beta = v_p(b)$ (intercámbiense si hace falta) y escríbanse $a = p^\alpha a'$, $b = p^\beta b'$ con $p \nmid a', b'$. Entonces $a + b = p^\alpha\bigl(a' + p^{\beta - \alpha}b'\bigr)$, luego $v_p(a + b) \geq \alpha = \min$. Si $\alpha < \beta$, el paréntesis es $a' + p^{\beta-\alpha}b' \equiv a' \not\equiv 0 \pmod p$: la valuación vale exactamente $\alpha$.

**4.** Los múltiplos de $m$ en $\intint1n$ son $m, 2m, \dots, qm$, donde $q$ es el mayor entero con $qm \leq n$, es decir, $q = \lfloor n/m \rfloor$.

**5.** Por la factorización única, $v_p(n!) = \sum_{j=1}^{n} v_p(j)$. Cuéntese de otro modo: cada $j$ aporta $v_p(j) = \#\{k \geq 1 : p^k \mid j\}$, luego

$$
v_p(n!) = \sum_{j=1}^n \#\{k : p^k \mid j\}
= \sum_{k\geq1} \#\{j \leq n : p^k \mid j\}
= \sum_{k\geq1} \Bigl\lfloor \frac n{p^k} \Bigr\rfloor
$$

por la pregunta 4 — la fórmula de Legendre. La suma es finita: los términos con $p^k > n$ se anulan.

**6.** $v_5(1000!) = 200 + 40 + 8 + 1 = 249$ (divisiones por $5, 25, 125, 625$); $v_2(1000!) = 500 + 250 + 125 + 62 + 31 + 15 +
7 + 3 + 1 = 994$. Ceros finales de $1000!$: cada cero consume un $2$ y un $5$, luego hay $\min(994, 249) = 249$.

**7.** Con $n = \sum_i a_ip^i$, la pregunta 2 da $\lfloor n/p^k \rfloor = \sum_{i \geq k} a_ip^{i-k}$ (se trunca el desarrollo en base $p$). Sumando en $k \geq 1$ e intercambiando las dos sumas finitas:

$$
v_p(n!) = \sum_{i\geq1} a_i \sum_{k=1}^{i} p^{i-k}
= \sum_{i\geq0} a_i\,\frac{p^i - 1}{p - 1}
= \frac{n - s_p(n)}{p - 1} .
$$

**8.** Para $p = 2$: $v_2(n!) = n - s_2(n)$. Como todo $n \geq 1$ tiene $s_2(n) \geq 1$, siempre $v_2(n!) \leq n - 1 < n$: $2^n \nmid n!$. Y $v_2(n!) = n - 1$ si y solo si $s_2(n) = 1$, si y solo si $n$ es una potencia de $2$.

**9.** $n$ tiene $\lfloor \log_p n \rfloor + 1$ cifras en base $p$, cada una a lo sumo $p - 1$, luego $1 \leq s_p(n) \leq (p-1)\bigl(\log_p(n) + 1\bigr)$. Sustituyendo en la pregunta 7:

$$
\frac n{p-1} - \log_p(n) - 1 \;\leq\; v_p(n!) \;<\; \frac n{p-1},
$$

y dividiendo por $n$: $\frac{v_p(n!)}n \to \frac1{p-1}$.

**10.** $Z(n) - Z(n-1) = v_5(n!/(n-1)!) = v_5(n)$: el número de ceros finales salta $v_5(n)$ en cada múltiplo de $5$ y es constante entre ellos. $Z(24) = \lfloor24/5\rfloor = 4$ y $Z(25) = 5 + 1 = 6$: en $n = 25$ el recuento salta de $4$ directamente a $6$ ($v_5(25) = 2$) y, como $Z$ es no decreciente con $Z \leq 4$ antes y $Z \geq 6$ después, el valor $5$ no se alcanza nunca: ningún factorial termina en exactamente cinco ceros.

**11.** Escríbase $x = \lfloor x\rfloor + \{x\}$: $\lfloor x + y\rfloor = \lfloor x\rfloor + \lfloor y\rfloor +
\lfloor \{x\} + \{y\}\rfloor$, y $0 \leq \{x\} + \{y\} < 2$ hace que la última parte entera valga $0$ o $1$. Después, aplicando Legendre tres veces,

$$
v_p\binom{m+n}m = v_p\bigl((m{+}n)!\bigr) - v_p(m!) - v_p(n!)
= \sum_{k\geq1}\Bigl(
\Bigl\lfloor\frac{m+n}{p^k}\Bigr\rfloor
- \Bigl\lfloor\frac{m}{p^k}\Bigr\rfloor
- \Bigl\lfloor\frac{n}{p^k}\Bigr\rfloor\Bigr),
$$

una suma finita de $0$ y $1$ (aplíquese la primera afirmación a $x = m/p^k$, $y = n/p^k$).

**12.** Fíjese $k \geq 1$ y escríbanse $m = p^km_1 + m_0$, $n = p^kn_1 + n_0$ con $0 \leq m_0, n_0 < p^k$ (división euclídea: $m_0$ es el número formado por las $k$ cifras bajas de $m$). Entonces

$$
\Bigl\lfloor\frac{m+n}{p^k}\Bigr\rfloor
- \Bigl\lfloor\frac m{p^k}\Bigr\rfloor
- \Bigl\lfloor\frac n{p^k}\Bigr\rfloor
= \Bigl\lfloor\frac{m_0 + n_0}{p^k}\Bigr\rfloor ,
$$

que vale $1$ si $m_0 + n_0 \geq p^k$ y $0$ en caso contrario. Pero $m_0 + n_0 \geq p^k$ dice precisamente que sumar las $k$ cifras bajas de $m$ y de $n$ desborda hacia la posición $k$ — un acarreo hacia la posición $k$ en el algoritmo escolar de la suma. Sumando en $k$: $v_p\binom{m+n}m$ es el número de acarreos de la suma $m + n$ en base $p$. (Kummer, 1852.)

**13.** Aplíquese Kummer con $m = j$, $n = p^k - j$, de suma $p^k = (1\underbrace{0\cdots0}_{k})_p$. Sea $a = v_p(j)$: las cifras en base $p$ de $j$ en las posiciones $0, \dots, a-1$ son $0$ y la cifra en la posición $a$ no es nula. Las cifras de $p^k - j$ por debajo de la posición $a$ también son $0$ ($p^k - j = p^a(p^{k-a} - j/p^a)$). En la posición $a$, las dos cifras no nulas deben sumar $p$ (cifra resultante $0$): un acarreo; y en cada posición $a+1, \dots, k-1$, las cifras más el acarreo entrante suman $p$ (de nuevo cifra resultante $0$): el acarreo se propaga. En total, $k - a$ acarreos, luego $v_p\binom{p^k}j = k - v_p(j)$. Para $k = 1$: $v_p\binom pj = 1$ para $0 < j < p$, la [divisibilidad](#def-b1-arith-divides) usada en el [Teorema 6.23](#thm-b1-arith-fermat).

**14.** Por la forma digital (pregunta 7), usando $s_2(2n) = s_2(n)$ (se añade una cifra cero):

$$
v_2\binom{2n}n = \bigl(2n - s_2(2n)\bigr) - 2\bigl(n -
s_2(n)\bigr) = 2s_2(n) - s_2(2n) = s_2(n) \geq 1 :
$$

$\binom{2n}n$ es siempre par, y $v_2 = 1$ (es decir, $\binom{2n}n \equiv 2 \pmod 4$) exactamente cuando $s_2(n) = 1$, es decir, cuando $n$ es una potencia de $2$.

**15.** Vandermonde con $m = n = k = p$: $\binom{2p}p =
\sum_{j=0}^p \binom pj\binom p{p-j} = \sum_{j=0}^p \binom pj^2$. Para $0 < j < p$, $p \mid \binom pj$ (pregunta 13), luego $\binom pj^2 \equiv 0 \pmod p$; los términos de los extremos dan $1 + 1$: $\binom{2p}p \equiv 2 \pmod p$.

**16.** Base $3$: $500 = 486 + 9 + 3 + 2$, cifras (de baja a alta) $(2, 1, 1, 0, 0, 2)$, luego $s_3(500) = 6$; y $1000 = 729 + 243 + 27 + 1$, cifras $(1, 0, 0, 1, 0, 1, 1)$, luego $s_3(1000) = 4$. *Kummer:* súmese $500 + 500$ en base $3$: posición $0$: $2 + 2 = 4$, cifra $1$ y acarreo $1$; posición $1$: $1 + 1 + 1 = 3$, cifra $0$ y acarreo $1$; posición $2$: $1 + 1 + 1 = 3$, cifra $0$ y acarreo $1$; posición $3$: $0 + 0 + 1 = 1$, sin acarreo; posición $4$: $0$; posición $5$: $2 + 2 = 4$, cifra $1$ y acarreo $1$; posición $6$: cae el acarreo, cifra $1$. Cuatro acarreos: $v_3\binom{1000}{500} = 4$. *Legendre:* $v_3(1000!) = \frac{1000 - 4}2 = 498$ y $v_3(500!) = \frac{500 - 6}2 = 247$, luego $v_3\binom{1000}{500} = 498 - 2\times247 = 4$. Los dos cálculos coinciden — y las cifras de la suma $(1, 0, 0, 1, 0, 1, 1)$ reproducen $1000$, como debe ser.

**17.** Por Kummer ($p = 2$, $m = k$, $n' = n - k$): $\binom nk$ es impar si y solo si la suma $k + (n - k)$ en base $2$ no tiene acarreos, si y solo si en cada posición las cifras cumplen $k_i + (n - k)_i = n_i$; en tal caso $k_i \leq n_i$ para todo $i$. Recíprocamente, si $k_i \leq n_i$ para todo $i$, entonces el número de cifras $n_i - k_i$ es $n - k$ y la suma no tiene acarreos. La misma demostración en base $p$: $p \nmid \binom nk$ si y solo si cada cifra en base $p$ de $k$ es a lo sumo la cifra correspondiente de $n$.

**18.** Contando los $k \in \intint0n$ cuyas cifras cumplen $k_i \leq n_i$: cada cifra de $k$ se elige independientemente entre $n_i + 1$ valores, lo que da $\prod_i (n_i + 1)$ elecciones; en base $2$ esto es $2^{\#\{i : n_i = 1\}} = 2^{s_2(n)}$. Fila $4 = (100)_2$: $2^1 = 2$ entradas impares — en efecto, $1, 4, 6, 4, 1$ solo tiene entradas impares en los extremos. Fila $5 = (101)_2$: $2^2 = 4$ — en efecto, $1, 5, 10, 10, 5, 1$.

**19.** Todas las entradas interiores son pares $\iff$ la fila tiene exactamente $2$ entradas impares (las de los dos extremos siempre lo son) $\iff 2^{s_2(n)} = 2 \iff s_2(n) = 1 \iff n$ es una potencia de $2$.

**20.** En la suma de la pregunta 11, el $k$-ésimo término se anula en cuanto $p^k > m + n$ (las tres partes enteras coinciden entonces; de hecho la primera vale $0$ cuando $p^k > m+n$; más simplemente, cada término es $0$). Por tanto, a lo sumo $\lfloor \log_p(m+n)\rfloor$ términos son no nulos, y cada uno vale $1$: $a = v_p\binom{m+n}m \leq \log_p(m+n)$, es decir, $p^a \leq m + n$.

**21.** Para todo [primo](#def-b1-arith-prime) $p$, $v_p\bigl(\operatorname{lcm}(1, \dots, 2n)\bigr) =
\lfloor\log_p(2n)\rfloor$ (la mayor potencia de $p$ que no supera a $2n$ aparece entre $1, \dots, 2n$). La pregunta 20 con $m = n$ da $v_p\binom{2n}n \leq \lfloor\log_p(2n)\rfloor$ para todo $p$: por la [Proposición 6.16](#prop-b1-arith-valuation), $\binom{2n}n \mid
\operatorname{lcm}(1, \dots, 2n)$. En cuanto al tamaño: el cociente $\binom{2n}{k+1}/\binom{2n}k = \frac{2n-k}{k+1} \geq 1$ exactamente para $k < n$, así que la entrada central es la mayor de las $2n + 1$ de la fila $2n$, de donde $4^n = \sum_k \binom{2n}k \leq
(2n+1)\binom{2n}n$. Combinando:

$$
\operatorname{lcm}(1, \dots, 2n) \geq \binom{2n}n \geq
\frac{4^n}{2n + 1} .
$$

Si hubiese pocos [primos](#def-b1-arith-prime) por debajo de $2n$, el mcm no podría ser tan grande: el crecimiento exponencial del mcm es una huella cuantitativa de la abundancia de [primos](#def-b1-arith-prime).

**22.** $Z(n) = \sum_k\lfloor n/5^k\rfloor \approx \frac n4$, así que se apunta cerca de $n = 4 \times 2026 = 8104$: $Z(8104) = 1620 + 324 + 64 + 12 + 2 = 2022$. Súbase por múltiplos de $5$: $Z(8110) = 2024$, $Z(8115) = 2025$, y

$$
Z(8120) = 1624 + 324 + 64 + 12 + 2 = 2026 .
$$

Como $Z$ es constante entre múltiplos de $5$ y $Z(8119) = Z(8115) =
2025$, el menor $n$ con al menos $2026$ ceros finales es $n = 8120$.

**23.** Base $7$: $50 = 49 + 1$, cifras (de baja a alta) $(1, 0, 1)$. Al sumar $50 + 50$: posición $0$: $1 + 1 = 2 < 7$, sin acarreo; posición $1$: $0 + 0 = 0$; posición $2$: $1 + 1 = 2 < 7$, sin acarreo. Sin acarreos, luego, por Kummer, $v_7\binom{100}{50} = 0$: $7 \nmid \binom{100}{50}$. Legendre coincide: $v_7(100!) = \lfloor 100/7 \rfloor + \lfloor 100/49 \rfloor = 14 + 2 =
16$ y $v_7(50!) = 7 + 1 = 8$, luego $v_7\binom{100}{50} = 16 - 2\times8 = 0$.

**24.** (i) La factorización única sostiene la definición misma de $v_p$ y su aditividad y, por tanto, la fórmula de Legendre y toda conclusión de [divisibilidad](#def-b1-arith-divides) ([Proposición 6.16](#prop-b1-arith-valuation)). (ii) La división euclídea produjo la identidad de truncamiento de la pregunta 2 y la separación $m = p^km_1 + m_0$ que aísla el acarreo (pregunta 12). (iii) Recuentos: el número de múltiplos de $m$ (pregunta 4), el producto de elecciones de cifras (pregunta 18) y la cota de la suma de una fila $4^n \leq (2n+1)\binom{2n}n$ (pregunta 21) son todos argumentos al estilo del [Capítulo 2](https://one-course.com/books/math/3/es/chapter/2-combinatoria#ch-b1-counting).

**25.** Legendre convierte «qué potencia de $p$ [divide](#def-b1-arith-divides) a $n!$» en aritmética de cifras en base $p$; Kummer comprime la respuesta para los [coeficientes binomiales](https://one-course.com/books/math/3/es/chapter/2-combinatoria#def-b1-counting-objects) en los acarreos de una sola suma — la [divisibilidad](#def-b1-arith-divides), en apariencia una propiedad global de números enormes, se lee localmente, cifra a cifra. La pregunta 16 es el paradigma: cuatro acarreos, calculados a mano, determinan la potencia exacta de $3$ en un número de cientos de cifras. Y la pregunta 21 muestra el mismo círculo de ideas rozando aguas profundas: una cota inferior exponencial para $\operatorname{lcm}(1, \dots, 2n)$ es un primer paso, enteramente elemental, hacia el teorema de los [números primos](#def-b1-arith-prime), cuya demostración queda muy lejos de este volumen. Toda la caja de herramientas — división, mcd, valuaciones — se repite para los polinomios en el [Capítulo 8](https://one-course.com/books/math/3/es/chapter/8-polinomios#ch-b1-poly), donde el análogo del desarrollo en cifras es el desarrollo en potencias de $(X - a)$.