Matemáticas universitarias — Grado 1 · Bachelor Year 1

6Aritmética de los enteros

La aritmética — el estudio de la divisibilidad 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 y algoritmo de Euclides, identidad de Bézout y lema de Gauss, factorización en primos y el cálculo de congruencias hasta el pequeño teorema de Fermat. Más allá de su encanto propio, esta materia es el modelo que el Capítulo 8 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 $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 $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$ ; existencia del mcd)

Todo subgrupo de $(\Z, +)$ es de la forma $n\Z = \{nk : k \in \Z\}$ para un único $n \in \N$ .
Para $a, b \in \Z$ no ambos nulos, el conjunto $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 a $a$ y a $b$ , y todo divisor común de $a$ y $b$ divide 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, 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); $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 a los dos. Y si $c$ divide a $a$ y a $b$ , entonces $c$ divide 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 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$ .

(Lema de Gauss) Si $a \mid bc$ y $\gcd(a, b) = 1$ , entonces $a \mid c$ .
Si $a \mid c$ , $b \mid c$ y $\gcd(a,b) = 1$ , entonces $ab \mid c$ .
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, $\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 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, 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 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), 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 $\leq \sqrt n$ . Por tanto, para comprobar si $n$ es primo basta probar los primos 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, 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.

Teorema 6.14 (Euclides)

Hay infinitos primos.

Demostración. Todo entero $n \geq 2$ tiene un divisor primo: su menor divisor $\geq 2$ es primo (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 y sea $N = p_1 p_2 \cdots p_k + 1 \geq 2$ . Algún primo $p_i$ divide a $N$ ; pero $p_i$ divide 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, 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): $n = 2$ es primo; para $n > 2$ , o bien $n$ es primo, 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 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 supera a $1$ ). Para $r \geq 1$ : el primo $p_1$ divide 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 a algún $q_j$ . Pero $q_j$ es primo 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 iguales. ∎

Proposición 6.16 (Valuaciones)

Para $p$ primo 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 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 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 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 $9$ con la suma de sus cifras (se demuestra en el Ejercicio 6.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 en miniatura: las comprobaciones por congruencias refutan, no certifican.

Proposición 6.20 (Invertibilidad módulo $n$ )

$a$ es invertible módulo $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 $n$ y se calcula con el algoritmo de Euclides 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). Unicidad: si $ab \equiv ab' \equiv 1$ , entonces $b \equiv b(ab') = (ab)b' \equiv b' \pmod n$ . ∎

Ejemplo 6.21 (Invertir $7$ módulo $26$ )

Como $\gcd(7, 26) = 1$ , la clase de $7$ es invertible módulo $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 $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, donde los módulos 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 $20$ — pero la ecuación sigue siendo tratable. La congruencia 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 $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. 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 $\binom pk = \frac{p!}{k!(p-k)!}$ es divisible por $p$ : en efecto, $k!\,(p-k)!\,\binom pk = p!$ y $p$ divide a $p!$ pero es coprimo 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 $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 $p$ (Proposición 6.20). ∎

Ejemplo 6.24 (El recíproco de Fermat falla: $341$ )

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 con $n$ , entonces $n$ no es primo. ¿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 del Observación 6.27. Moraleja: una implicación y su recíproca llevan vidas separadas (Observación 1.10), incluso tratándose de teoremas.

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

¿Cuál es el resto de $7^{2026}$ módulo $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 el orden que proporciona Fermat y redúzcanse las potencias intermedias en cada paso.

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

Dividir una congruencia. 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 también el módulo: $ac \equiv bc \pmod n \iff a \equiv b \pmod{n/\gcd(c,n)}$ .
Usar mal el lema de Euclides. $a \mid bc$ implica $a \mid b$ o $a \mid c$ solo para $a$ primo (o coprimo con uno de los factores): $6 \mid 4 \times 9$ y, sin embargo, $6$ no divide a ninguno de los dos.
Coprimo es una relación, no una propiedad. « $8$ y $9$ son coprimos» es cierto aunque ninguno sea primo; «coprimos dos a dos» es más fuerte que «coprimos en conjunto» ( $\gcd(6, 10, 15) = 1$ , pero ningún par es coprimo).
Los exponentes no viven módulo $n$ . En $a^k \bmod n$ , el exponente solo se puede reducir módulo el orden de $a$ (por ejemplo, $p - 1$ cuando se aplica Fermat), nunca módulo $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.

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, 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 se convierte en el anillo $\Z/n\Z$ en el Capítulo 7, cuyos elementos invertibles (Proposición 6.20) 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. Más allá de este volumen, la inversión de Bézout módulo $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 que allí se usan.

Observación 6.28 (Interludio: $\Z$ 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 (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, 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, donde las cuestiones de invertibilidad (la Proposición 6.20 de este capítulo) se vuelven enunciados 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. — 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, y un par de Bézout para él.

Solución

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 en base $10$ : un entero es congruente módulo $9$ con la suma de sus cifras, y módulo $11$ con la suma alternada de sus cifras. ¿Cuánto vale $123\,456\,789$ módulo $9$ y módulo $11$ ?

Solución

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 $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

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

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 y $\min(\alpha,\beta) + \max(\alpha,\beta) = \alpha + \beta$ .)

Solución

Solución de Ejercicio 6.5.

Para todo primo $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 son iguales (Proposición 6.16), 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

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); 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 $p$ , usando valuaciones: compárese $v_p$ en los dos miembros de $p q^2 = r^2$ .

Solución

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, el par de congruencias $x \equiv a \ (m)$ , $x \equiv b\ (n)$ tiene siempre solución, única módulo $mn$ .

Solución

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 a $x - x'$ , luego $mn \mid x - x'$ (Teorema 6.8 (2)): unicidad módulo $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 $7$ , y las dos últimas cifras decimales de $7^{100}$ (módulo $100 = 4 \times 25$ : úsese el Ejercicio 6.8).

Solución

Solución de Ejercicio 6.9.

Módulo $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 $4$ y módulo $25$ . Módulo $4$ : $7 \equiv -1$ , luego $7^{100} \equiv 1$ . Módulo $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), $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 $2^n - 1$ es $2^r - 1$ , donde $r$ es el resto de $m$ módulo $n$ ; síganse después los pasos del algoritmo de Euclides.

Solución

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 a $2^{nq} - 1 = (2^n - 1)(2^{n(q-1)} + \dots + 1)$ . Así pues, módulo $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 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. Demuéstrese que

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

emparejando cada factor de $(p-1)!$ con su inverso módulo $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, entonces $(n-1)! \not\equiv -1 \pmod n$ .

Solució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 $p$ , y su inverso $a^{-1}$ es de nuevo uno de los factores (Proposición 6.20). 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$ .

Demuéstrese que $F_0 F_1 \cdots F_{n-1} = F_n - 2$ para $n \geq 1$ (inducción).
Dedúzcase que los números de Fermat son coprimos dos a dos.
Dedúzcase una segunda demostración, independiente del Teorema 6.14, de que hay infinitos primos.

Solución

Solución de Ejercicio 6.12.

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 .$
Sean $m < n$ y $d = \gcd(F_m, F_n)$ . Por (1), $F_m$ divide a $F_n - 2$ , luego $d$ divide a la vez a $F_n$ y a $F_n - 2$ , y por tanto divide a $2$ . Pero todo número de Fermat es impar, luego $d = 1$ .
Cada $F_n \geq 3$ tiene un divisor primo $p_n$ (primer paso del Teorema 6.14). Si $m \neq n$ , entonces $p_m \neq p_n$ , pues un primo común dividiría a $\gcd(F_m, F_n) = 1$ . La aplicación $n \mapsto p_n$ es, por tanto, inyectiva de $\N$ en los primos: hay infinitos primos.

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 $p$ que divide a $n!$ , o que divide a un coeficiente binomial? 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. En todo el problema, $p$ es un primo, $\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.

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$ .
Demuéstrese que, para $x \in \R$ y $n \in \N^*$ , $\bigl\lfloor \lfloor x \rfloor / n \bigr\rfloor = \lfloor x/n \rfloor$ .
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)$ .
Pruébese que el número de múltiplos de $m$ en $\intint1n$ es $\lfloor n/m \rfloor$ .
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.

Calcúlense $v_5(1000!)$ y $v_2(1000!)$ y conclúyase: ¿en cuántos ceros termina $1000!$ ?
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} .$
Dos consecuencias para $p = 2$ : pruébese que $2^n$ nunca divide a $n!$ , y que $2^{n-1}$ divide a $n!$ exactamente cuando $n$ es una potencia de $2$ .
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.
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.

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$ .
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$ .)
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, recuperado.)
Demuéstrese que $v_2\binom{2n}n = s_2(n)$ . Dedúzcase que el coeficiente binomial central es siempre par, y que $\binom{2n}n \equiv 2 \pmod 4$ exactamente cuando $n$ es una potencia de $2$ .
Pruébese, usando la identidad de Vandermonde (Ejercicio 2.7) y la pregunta 13, que $\binom{2p}p \equiv 2 \pmod p$ para todo primo $p$ .
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.

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$ .
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$ .
Dedúzcase que todas las entradas interiores $\binom nk$ ( $0 < k < n$ ) son pares si y solo si $n$ es una potencia de $2$ .
Demuéstrese que toda potencia de un primo 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?)
Dedúzcase que $\binom{2n}n$ divide 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.

Parte V — Síntesis.

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.)
Una última comprobación cruzada: pruébese que $7$ no divide 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.
¿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? Una frase para cada uno.
Síntesis, en un párrafo breve: la fórmula de Legendre convierte una cuestión de divisibilidad 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 (el enunciado completo, el teorema de los números primos, queda muy lejos de este volumen; el análogo polinómico de las herramientas de este capítulo es el Capítulo 8).

Solución

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 usada en el Teorema 6.23.

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 $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, $\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 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.

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 (Proposición 6.16). (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.

25. Legendre convierte «qué potencia de $p$ divide a $n!$ » en aritmética de cifras en base $p$ ; Kummer comprime la respuesta para los coeficientes binomiales en los acarreos de una sola suma — la divisibilidad, 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, 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, donde el análogo del desarrollo en cifras es el desarrollo en potencias de $(X - a)$ .

Términos definidos en este capítulo

Ver los 395 términos del glosario