Matemáticas universitarias — Grado 1 · Bachelor Year 1

6Aritmética de enteros

Aritmética — el estudio de divisibilidad en $\Z$ — se inició en el volumen de la escuela secundaria. Este capítulo lo reconstruye completamente a partir del División euclidiana, con pruebas completas: máximo común divisor y el algoritmo euclidiano, la identidad de Bézout y el lema de Gauss, factorización en primos, y el cálculo de congruencias hasta el pequeño de Fermat. teorema. Más allá de su propio encanto, este material es el modelo que Capítulo 8 imita polinomios.

6.1 Divisibilidad y división euclidiana

Definición 6.1 (Divisibilidad)

Para $a, b \in \Z$ , $b$ divide $a$ (escrito $b \mid a$ ) cuando $a = bq$ para algunos $q \in \Z$ . Básico consecuencias: 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$ fuerzan $b = \pm a$ .

Teorema 6.2 (división euclidiana)

Para todos los $a \in \Z$ y $b \in \N^*$ , hay 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$ (tome $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 más pequeño de $A$ : contradicción. Entonces $0 \leq r < b$ .

Unicidad. Si $bq + r = bq' + r'$ con $0 \leq r, r' < b$ , luego $b(q - q') = r' - r$ y $\abs{r' - r} < b$ : el múltiplo de $b$ en el lado izquierdo debe estar $0$ , por lo que $q = q'$ y $r = r'$ . ∎

Ejemplo 6.3 (Numeración posicional por división repetida)

Escribe $2026$ en la base $7$ . Divida repetidamente por $7$ , manteniendo el 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$ . Verificar: $5 \times 343 + 6 \times 49 + 2 \times 7 + 3 = 1715 + 294 + 14 + 3 = 2026$ . La singularidad de Euclidiana La división es exactamente lo que hace que cada dígito sea forzado: en cada paso el resto es el único número entero en $\intint06$ congruente al valor actual mod $7$ , por lo que la escritura base- $7$ es única — el hecho se utiliza silenciosamente cada vez que el problema del fin de semana manipula “los dígitos de $n$ en la base $p$ ”.

6.2 máximo común divisor

Teorema 6.4 (Subgrupos de $\Z$ ; existencia del mcd)

Cada subgrupo de $(\Z, +)$ tiene la forma $n\Z = \{nk : k \in \Z\}$ para un $n \in \N$ único.
Para $a, b \in \Z$ no ambos son cero, conjunto $a\Z + b\Z = \{au + bv : u, v \in \Z\}$ es un subgrupo de $\Z$ , por lo tanto es igual $d\,\Z$ para un $d \in \N^*$ único. Este $d$ es el máximo común divisor $\gcd(a, b)$ : es divide $a$ y $b$ , y todos los comunes divisor de $a$ y $b$ divide $d$ .

Demostración. (1) Sea $H \subseteq \Z$ un subgrupo (no vacío, estable bajo resta; la definición formal está en Capítulo 7, y sólo se utilizan estas dos propiedades). Si $H = \{0\}$ , tome $n = 0$ . De lo contrario, $H$ contiene un elemento distinto de cero y su opuesto, por lo tanto, elemento estrictamente positivo más pequeño $n$ . Entonces $n\Z \subseteq H$ . Para $x \in H$ , escriba $x = nq + r$ con $0 \leq r < n$ (Teorema 6.2); $r = x - nq \in H$ , y minimalidad de $n$ fuerzas $r = 0$ : $x \in n\Z$ . Unicidad: $n$ es el menos positivo. elemento de $n\Z$ .

(2) $a\Z + b\Z$ contiene $0$ y es estable bajo resta, por lo que es $d\Z$ con $d \geq 1$ (contiene $a$ o $b$ distinto de cero). Desde $a, b \in d\Z$ , $d$ divide ambos. Y si $c$ divide $a$ y $b$ , entonces $c$ divide cada $au + bv$ — en particular $c \mid d$ , desde $d \in a\Z + b\Z$ . Esta es la propiedad anunciada (e implica $\abs c \leq d$ , por lo que $d$ merece el nombre de divisor común mayor). ∎

Corolario 6.5 (Identidad de Bézout)

Para $a, b$ no ambos cero, existe $u, v \in \Z$ con

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

En particular ( $\gcd(a,b) = 1$ , el coprimo caso): $a$ y $b$ son coprimo si y sólo si $au + bv = 1$ tiene un 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 proporciona la solución; por el contrario, $au + bv = 1$ obliga a cada divisor común de $a, b$ a dividir $1$ . ∎

Método 6.6 (Algoritmo euclidiano, ampliado)

Para calcular $\gcd(a, b)$ ( $a > b > 0$ ): divida $a = bq + r$ ; entonces $\gcd(a, b) = \gcd(b, r)$ (divisores comunes de $(a,b)$ y de $(b,r)$ coinciden, desde $r = a - bq$ ); iterar hasta que el resto sea $0$ ; el El último resto distinto de cero es gcd. corriendo las divisiones al revés (o manteniendo los coeficientes en el camino abajo) produce un par 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$ . entonces $\gcd = 1$ . al revé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*}

Verificar: $47 \times 23 = 1081$ , $9 \times 120 = 1080$ .

Teorema 6.8 (Lema de Gauss y consecuencias)

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

(lema de Gauss) Si $a \mid bc$ y $\gcd(a, b) = 1$ , luego $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$ . Multiplicar por $c$ : $acu + bcv = c$ . ambos Los términos son divisibles por $a$ (el segundo porque $a \mid bc$ ), por lo que $a \mid c$ .

(2) Escriba $c = aq$ ; de $b \mid aq$ y $\gcd(a, b) = 1$ , punto (1) da $b \mid q$ , entonces $ab \mid aq = c$ .

(3) $au + bv = 1$ y $au' + cv' = 1$ . multiplica los 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 Corolario 6.5, $\gcd(a, bc) = 1$ . ∎

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

Encuentra todos los $(x, y) \in \Z^2$ con $6x + 10y = 4$ . Primero, el prueba de existencia: $\gcd(6, 10) = 2$ divide $4$ , entonces soluciones existe (si el mcd no dividió el lado derecho, el lado izquierdo siempre sería un múltiplo de él y no habría ninguno). dividir a través de: $3x + 5y = 2$ . Se ve una solución particular: $(x_0, y_0) = (-1, 1)$ . Para el general, reste: $3(x + 1) = -5(y - 1)$ , por lo que $3 \mid 5(y-1)$ , y el lema de Gauss ( $\gcd(3,5) = 1$ ) da $3 \mid y - 1$ : $y = 1 - 3k$ , luego $x = -1 + 5k$ . Por el contrario cada tal par funciona:

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

El patrón es general: una solución particular más el número entero. múltiplos de $\bigl(\frac b{\gcd}, -\frac a{\gcd}\bigr)$ — el misma estructura "particular más homogénea" que en Capítulo 5, con el lema de Gauss interpretando la unicidad papel.

Definición 6.10 (Mínimo común múltiple)

$\operatorname{lcm}(a, b)$ es el generador en $\N$ del subgrupo $a\Z \cap b\Z$ : es un generador común múltiplo de $a$ y $b$ que divide cada múltiplo común, y para $a, b \in \N^*$ ,

\gcd(a,b) \times \operatorname{lcm}(a,b) = ab \qquad (\text{proof in } \text{Ejercicio 6.5}).

Ejemplo 6.11 (Los problemas de alineación son problemas de lcm)

Dos engranajes engranados tienen dientes $84$ y $36$ . ¿Después de cuántos dientes de movimiento común ¿vuelven juntos 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 del engranaje grande y $7$ del uno pequeño ( $252/84$ y $252/36$ ). Tenga en cuenta la ruta práctica: calcular el mcd primero (Euclid: $84 = 2\times36 + 12$ , $36 = 3\times12$ ), luego divida — nunca construya el mcm enumerando múltiplos. Cada pregunta de coincidencia periódica (engranajes, planetarios) alineaciones, encuentro de decimales periódicos) se reduce a este cálculo.

6.3 numeros primos

Definición 6.12

Un número entero $p \geq 2$ es principal cuando es sólo los divisores positivos son $1$ y $p$ . Para $p$ principal y $a \in \Z$ : ya sea $p \mid a$ o $\gcd(p, a) = 1$ . En consecuencia (Teorema 6.8), Lema de Euclides contiene: si $p \mid ab$ entonces $p \mid a$ o $p \mid b$ .

Observación 6.13 (Prueba de primalidad por división de prueba)

Si $n = ab$ con $2 \leq a \leq b$ , entonces $a^2 \leq ab = n$ , entonces $a \leq \sqrt n$ : un $n$ compuesto siempre tiene un divisor primo $\leq \sqrt n$ . Por lo tanto, para comprobar si $n$ es primo, basta con probar desde primos hasta $\sqrt n$ . Para $n = 271$ : $\sqrt{271} < 17$ y $271$ no es divisible por ninguno de $2, 3, 5, 7, 11, 13$ (dígito impar). suma $10$ , no termina en $0$ o $5$ , $271 = 7\cdot38 + 5 = 11\cdot24 + 7 = 13\cdot20 + 11$ ): primo, después de seis divisiones en lugar de doscientos. La barrera $\sqrt n$ es una auténtica umbral: cruzarlo eficientemente para números de cien dígitos requiere las modernas pruebas de primalidad nacidas de Teorema 6.23.

Teorema 6.14 (Euclides)

Hay infinitos primos.

Demostración. Todo número entero $n \geq 2$ tiene un divisor primo: su divisor más pequeño $\geq 2$ es primo (una factorización adecuada produciría un divisor más pequeño de $n$ ). Ahora supongamos que $p_1, \dots, p_k$ fueran todos los primos y deja que $N = p_1 p_2 \cdots p_k + 1 \geq 2$ . Algunos primo $p_i$ divide $N$ ; pero $p_i$ también divide $N - 1 = p_1\cdots p_k$ , entonces $p_i \mid 1$ — absurdo. ∎

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

Todo número entero $n \geq 2$ es 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{ primes},\ \alpha_i \in \N^*)

es único.

Demostración. Existencia por inducción fuerte (Teorema 1.12): $n = 2$ es primo; para $n > 2$ , $n$ es primo o $n = ab$ con $2 \leq a, b < n$ y los factores de hipótesis de inducción $a$ y $b$ .

Unicidad. Supongamos $p_1 \cdots p_r = q_1 \cdots q_s$ (primos listado con repetición, dice $r \leq s$ ), e induzca en $r$ . Si $r = 0$ el lado izquierdo es $1$ , forzando a $s = 0$ (un producto de primos excede $1$ ). Para $r \geq 1$ : el primo $p_1$ divide $q_1(q_2\cdots q_s)$ , por lo que según el lema de Euclides $p_1 \mid q_1$ o $p_1 \mid q_2\cdots q_s$ ; iterando, $p_1$ divide algunos $q_j$ . Pero $q_j$ es primo y $p_1 \geq 2$ : necesariamente $p_1 = q_j$ . Cancelar este factor común (legítimo: $\Z$ es un dominio integral) para obtener

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

(la omisión de la marca del sombrero), una igualdad de productos más cortos; el 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$ coincide con el pedido, de ahí que también lo hicieran los originales. Los exponentes forman grupos iguales. primos. ∎

Proposición 6.16 (Valoraciones)

Para $p$ primo y $n \in \N^*$ , escriba $v_p(n)$ para el exponente de $p$ en el 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 La factorización de $mn$ es única. Si $m \mid n$ , escriba $n = mq$ y aplicarlo. Por el contrario, si todo es $v_p(m) \leq v_p(n)$ , el número entero $q = \prod_p p^{\,v_p(n) - v_p(m)}$ satisface $mq = n$ . La fórmula del mcd: el número entero $d = \prod p^{\min}$ divide tanto por el criterio, como cada divisor común $c$ tiene $v_p(c) \leq \min$ para todos los $p$ , por lo que $c \mid d$ ; Mismo razonamiento para el mcm con $\max$ . ∎

Ejemplo 6.17 (Cuadrados y cubos mediante valoraciones)

Un número entero $n \geq 1$ es un cuadrado perfecto si y sólo si cada $v_p(n)$ es par (si $n = m^2$ , entonces $v_p(n) = 2v_p(m)$ ; a la inversa, reducir a la mitad cada exponente). Lo mismo ocurre con los cubos con múltiplos de $3$ . Por lo tanto $21168 = 2^4 \times 3^3 \times 7^2$ no es un cuadrado ( $v_3 = 3$ es impar) y no un cubo ( $v_2 = 4$ ); el entero positivo más pequeño $m$ tal que $21168\,m$ is a El cubo se encuentra elevando cada exponente al 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: preguntas multiplicativas (cuadrados, cubos, divisores, mcd, mcm) se convierten en preguntas coordinadamente sobre el exponente vectores $(v_2, v_3, v_5, \dots)$ — la factorización única es la enunciado que estas 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$ . Este es un relación de equivalencia compatible con adición y multiplicación: si $a \equiv b$ y $a' \equiv b'$ (mod $n$ ), entonces $a + a' \equiv b + b'$ , $aa' \equiv bb'$ y $a^k \equiv b^k$ para $k \in \N$ .

Ejemplo 6.19 (Expulsando nueves)

Compatibilidad con $+$ y $\times$ es un dispositivo de control tan antiguo como comercio. Desde $10 \equiv 1 \pmod 9$ , cada número entero es mod $9$ congruente con su suma de dígitos (probado como Ejercicio 6.2). Para comprobar la afirmación $1234 \times 567 = 699\,678$ : las sumas de los dígitos dan $1234 \equiv 1$ y $567 \equiv 18 \equiv 0 \pmod 9$ , por lo que el producto debe ser $\equiv 1 \times 0 = 0$ ; y de hecho $6 + 9 + 9 + 6 + 7 + 8 = 45 \equiv 0$ . el cheque pasa (y el producto es de hecho correcto). ¿Alguien había reportado $699\,478$ , la suma de dígitos $43 \equiv 7 \not\equiv 0$ sería condenarlos al instante. La prueba es unilateral: detecta un error a menos que el error sea en sí mismo un múltiplo de $9$ — que es exactamente la lección pseudoprincipal de Ejemplo 6.24 en miniatura: cheques congruencia refutan, no certifican.

Proposición 6.20 (Mod invertibilidad $n$ )

$a$ es mod reversible $n$ (es decir, $ab \equiv 1 \pmod n$ para algunos $b$ ) si y sólo si $\gcd(a, n) = 1$ . Lo inverso es entonces mod único. $n$ y calculado por el algoritmo euclidiano extendido.

Demostración. $ab \equiv 1 \pmod n$ significa $ab + nk = 1$ para algunos $k$ : un Bézout relación, que existe si $\gcd(a,n) = 1$ (Corolario 6.5). Unicidad: si $ab \equiv ab' \equiv 1$ , luego $b \equiv b(ab') = (ab)b' \equiv b' \pmod n$ . ∎

Ejemplo 6.21 (Inversión $7$ módulo $26$ )

Desde $\gcd(7, 26) = 1$ , la clase de $7$ es mod invertible $26$ . Euclides ampliado:

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

luego al revé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 lo tanto $7 \times (-11) \equiv 1 \pmod{26}$ , es decir $7^{-1} \equiv -11 \equiv 15 \pmod{26}$ ; comprobar: $7 \times 15 = 105 = 4 \times 26 + 1$ . Con la inversa en mano, cualquier congruencia $7x \equiv c \pmod{26}$ se resuelve en una multiplicación: $x \equiv 15c$ . esto La inversión mecánica es el caballo de batalla de la aritmética modular. y de los protocolos de clave pública mencionados en Observación 6.27, donde los módulos tienen cientos de dígitos pero el algoritmo es exactamente este.

Ejemplo 6.22 (Cuando el coeficiente no es invertible)

Resuelve $12x \equiv 8 \pmod{20}$ . Aquí $\gcd(12, 20) = 4$ , entonces $12$ no es invertible mod $20$ — pero la ecuación sigue siendo manejable. El congruencia dice $20 \mid 12x - 8$ ; dividiendo el relación completa por $4$ (divisor de los tres ingredientes), es equivalente 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$ ), entonces $x \equiv 4 \pmod 5$ : las soluciones son $x \equiv 4, 9, 14, 19 \pmod{20}$ — clases cuatro mod $20$ , coincidente con el mcd. (Si el lado derecho no hubiera sido divisible por $4$ , digamos $12x \equiv 6 \pmod{20}$ , no habría ninguna solución: el lado izquierdo siempre es $\equiv 0 \pmod 4$ .) Forma general: $ax \equiv b \pmod n$ se puede resolver si $\gcd(a, n) \mid b$ , y luego tiene exactamente clases de solución $\gcd(a, n)$ — divide todo por el mcd e invertir.

Teorema 6.23 (Pequeño teorema de Fermat)

Sea $p$ primo. Por cada $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$ : de hecho, $k!\,(p-k)!\, \binom pk = p!$ y $p$ divide $p!$ pero es de coprimo a $k!(p-k)!$ . (todos los factores son $< p$ ), por lo que el lema de Gauss da $p \mid \binom pk$ .

Ahora demuestre $a^p \equiv a$ para $a \in \N$ por inducción. Verdadero 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,

todos los términos medios desaparecen mod $p$ . Para $a < 0$ , aplique el resultado a $-a$ y separe $p = 2$ (donde $x \equiv -x$ ) de $p$ impar (donde $(-a)^p = -a^p$ ). Finalmente, si $p \nmid a$ , multiplica $a^p \equiv a$ por una inversa de $a$ mod $p$ (Proposición 6.20). ∎

Ejemplo 6.24 (El converso de Fermat falla: $341$ )

El pequeño teorema de Fermat ofrece una prueba composición barata: si $a^{n-1} \not\equiv 1 \pmod n$ para algunos $a$ coprimo a $n$ , entonces $n$ no es primo. ¿Podría la prueba también certificar la primalidad? No: tome $n = 341 = 11 \times 31$ , compuesto y $a = 2$ . desde $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 composite $341$ pasa el test de Fermat para la base $2$ (es el más pequeño como pseudoprime). La base $3$ la desenmascara ( $3^{340} \not\equiv 1$ ) y pruebas prácticas de primalidad. por lo tanto ejecuta la prueba en varias bases, además de mejoras — las versiones industriales de esta idea son las que certifican la gran primos de Observación 6.27. Moraleja: una implicación y sus conversos viven vidas separadas (Observación 1.10), incluso para teoremas.

Ejemplo 6.25 (Cálculos prácticos de congruencia)

¿Cuál es el resto de $7^{2026}$ mod $11$ ? Por Fermat, $7^{10} \equiv 1 \pmod{11}$ . Desde $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: reducir el exponente módulo orden proporcionada por Fermat, luego reducir las potencias intermedias en cada paso.

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

Dividir una congruencia. De $ac \equiv bc \pmod n$ no se puede concluir $a \equiv b$ salvo que $\gcd(c, n) = 1$ : $6 \equiv 2 \pmod 4$ pero $3 \not\equiv 1 \pmod 4$ . La regla correcta usa el divisor y el módulo: $ac \equiv bc \pmod n \iff a \equiv b \pmod{n/\gcd(c,n)}$ .
Mal uso del lema de Euclides. $a \mid bc$ implica $a \mid b$ o $a \mid c$ solo para $a$ primo (o coprimo a un factor): $6 \mid 4 \times 9$ todavía $6$ divide ninguno de los factores.
coprime is a relation, not a property. “ $8$ y $9$ son coprimo” es cierto, aunque tampoco lo es primo; “coprimo por pares” es más fuerte que “globalmente coprimo” ( $\gcd(6, 10, 15) = 1$ pero no hay ningún par). coprimo).
Los exponentes no viven mod $n$ . En $a^k \bmod n$ , el exponente sólo se puede reducir en módulo orden de $a$ (por ejemplo $p - 1$ cuando se aplica Fermat), nunca módulo $n$ : $2^{10} \bmod 11$ es $1$ , no $2^{10 \bmod 11} = 2^{10}$ — la reducción que funciona es la que Ejemplo 6.25 realiza.

Observación 6.27 (Dónde se utiliza este capítulo)

Este capítulo es tanto una plantilla como una caja de herramientas. toda la cadena — División euclidiana, mcd, Bézout, Gauss, factorización única — se reproduce palabra por palabra para polinomios en Capítulo 8, donde "grado" juega el papel de valor absoluto; comparando el dos capítulos uno al lado del otro es la mejor manera de entender ambos. el El cálculo congruencia se convierte en el anillo $\Z/n\Z$ en Capítulo 7, cuyos elementos invertibles (Proposición 6.20) forman el primer ejemplo no trivial de un grupo de unidades. Las valoraciones regresan en el problema del fin de semana a continuación (fórmula de Legendre) y potenciar las pruebas de irracionalidad de Capítulo 10. Más allá de este volumen, mod de inversión Bézout $n$ es el motor de la criptografía de clave pública, y el pequeño El teorema es el abuelo de las pruebas de primalidad que certifican la primos grande usado allí.

Observación 6.28 (Interludio: $\Z$ como plantilla)

Aléjese de los teoremas individuales y observe la arquitectura del capítulo: una herramienta (división euclidiana) produjo una clasificación (subgrupos $n\Z$ ), que produjo una teorema de existencia (mcd, Bézout), que produjo un divisibilidad cálculo (Gauss), que produjo una factorización única — cada suelo apoyándose únicamente en el de abajo. El mismo edificio será Se levantan dos veces más en este volumen con diferentes plantas bajas: en Capítulo 8, donde la división por grados reemplaza a la división por talla y todo lo anterior se repite literal; y, en miniatura, dentro de cada $\Z/n\Z$ de Capítulo 7, donde las preguntas de invertibilidad (las de este capítulo) Proposición 6.20) se vuelven estructurales enunciados aproximadamente anillos y campos. Al reconocer un argumento como "el argumento $\Z$ , trasplantado” es la forma más rápida de aprender esos capítulos — y la primera prueba del hábito central del álgebra, demostrar teoremas sobre axiomas en lugar de sobre objetos.

Filas 0a7 del triángulo de Pascal con extraño entradas completadas: la fila n contiene 2s_2(n) de ellas, donde s_2(n) es el número de unos en 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 probabilidades" genera dos copias de sí mismo — es el teorema de Kummer en forma de imagen, demostrado en el problema del fin de semana a continuación. — Filas $0$ a $7$ del triángulo de Pascal con *extraño* entradas completadas: la fila $n$ contiene $2^{s_2(n)}$ de ellas, donde $s_2(n)$ es el número de unos en 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 probabilidades" genera dos copias de sí mismo — es el teorema de Kummer en forma de imagen, demostrado en el problema del fin de semana a continuación.

6.5 Ceremonias

Ejercicio 6.1 ★

Calcular $\gcd(1\,001, 777)$ por el algoritmo euclidiano y un Bézout par para ello.

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$ . entonces $\gcd(1001, 777) = 7$ . al revé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 .

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

Ejercicio 6.2 ★

Demuestre las reglas divisibilidad en la base $10$ : un número entero es congruente mod $9$ a la suma de sus dígitos, y mod $11$ a la suma alterna de sus dígitos. ¿Qué es $123\,456\,789$ mod $9$ y mod $11$ ?

Solución

Solución de Ejercicio 6.2.

Desde $10 \equiv 1 \pmod 9$ : $10^k \equiv 1$ , entonces $\sum_k d_k 10^k \equiv \sum_k d_k \pmod 9$ . Dado que $10 \equiv -1 \pmod{11}$ : $10^k \equiv (-1)^k$ , el número entero es congruente con la suma alterna $\sum_k (-1)^k d_k$ mod $11$ (a partir del dígito unidades con signo $+$ ).

$123\,456\,789$ : suma de dígitos $45 \equiv 0 \pmod 9$ . Suma alterna de las unidades: $9 - 8 + 7 - 6 + 5 - 4 + 3 - 2 + 1 = 5$ , por lo que el número es $\equiv 5 \pmod{11}$ .

Ejercicio 6.3 ★

Resuelva en $\Z$ : $91x \equiv 1 \pmod{237}$ (Euclides ampliado).

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$ . al revé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.

Entonces $91 \times 112 \equiv 1 \pmod{237}$ : las soluciones son $x \equiv 112 \pmod{237}$ . (Compruebe: $91 \times 112 = 10\,192 = 43 \times 237 + 1$ .)

Ejercicio 6.4 ★

Encuentra todos los pares $(x, y) \in \Z^2$ con $17x + 39y = 1$ ; entonces 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 al revé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 del ecuación homogénea $17x + 39y = 0$ : $x = 39k$ , $y = -17k$ (ya que $17 \mid 39y$ y $\gcd(17,39) = 1$ fuerza $17 \mid y$ — Lema de Gauss). Por lo tanto

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

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

Ejercicio 6.5 ★★

Demuestre que para $a, b \in \N^*$ : $\gcd(a,b) \times \operatorname{lcm}(a,b) = ab$ . (Use the valuation formulas of Proposición 6.16 and $\min(\alpha,\beta) + \max(\alpha,\beta) = \alpha + \beta$ .)

Solución

Solución de Ejercicio 6.5.

Por cada 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 números enteros positivos con la misma valoración en cada primo son iguales (Proposición 6.16), entonces $\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$ . Calcule $\gcd(a, b)$ , $\operatorname{lcm}(a,b)$ y el número de divisores positivos de $a$ . (Prove the divisor-count formula $\prod_i (\alpha_i + 1)$ .)

Solución

Solución de Ejercicio 6.6.

Valoraciones: $\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$ .

Recuento 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 opciones son independiente, por lo que hay divisores $\prod_i (\alpha_i + 1)$ . Para $a$ : $(10+1)(4+1)(2+1) = 165$ .

Ejercicio 6.7 ★★

Demuestre que $\sqrt p$ es irracional para cada primo $p$ , usando Valoraciones: comparar $v_p$ de ambos lados de $p q^2 = r^2$ .

Solución

Solución de Ejercicio 6.7.

Supongamos $\sqrt p = \frac rq$ con $r, q \in \N^*$ , es decir, $p q^2 = r^2$ . Aplicar $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 número entero no puede tener pares ni impares. $p$ -valoración de una vez: contradicción. Entonces $\sqrt p \notin \Q$ .

Ejercicio 6.8 ★★

(Problema del resto chino) Encuentra todos los números enteros $x$ con

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

Demuestre en el camino que para coprimo $m, n$ , el par de congruencias $x \equiv a \ (m)$ , $x \equiv b\ (n)$ siempre tiene una solución, única mod $mn$ .

Solución

Solución de Ejercicio 6.8.

Hecho generalizado. Con $\gcd(m,n) = 1$ , Bézout regala $mu + nv = 1$ . Establezca $x_0 = b\,mu + a\,nv$ . Luego $x_0 \equiv a\,nv \equiv a(1 - mu) \equiv a \pmod m$ y de manera similar $x_0 \equiv b \pmod n$ : existencia. si $x$ y $x'$ son dos soluciones, $m$ y $n$ dividen $x - x'$ , entonces $mn \mid x - x'$ (Teorema 6.8 (2)): mod de unicidad $mn$ .

Numéricamente: $m = 7$ , $n = 11$ : $7 \times (-3) + 11 \times 2 = 1$ . Entonces $x_0 = 5 \times 7 \times (-3) + 2 \times 11 \times 2 = -105 + 44 = -61 \equiv 16 \pmod{77}$ . Verificar: $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 ★★

Calcule $3^{1000}$ mod $7$ , y los dos últimos dígitos decimales de $7^{100}$ (mod $100 = 4 \times 25$ : use Ejercicio 6.8).

Solución

Solución de Ejercicio 6.9.

Mod $7$ : Fermat regala $3^6 \equiv 1$ y $1000 = 6 \times 166 + 4$ , entonces $3^{1000} \equiv 3^4 = 81 \equiv 4 \pmod 7$ .

Últimos dos dígitos de $7^{100}$ : mod de trabajo $4$ y mod $25$ . Mod $4$ : $7 \equiv -1$ , entonces $7^{100} \equiv 1$ . Mod $25$ : $7^2 = 49 \equiv -1$ , entonces $7^4 \equiv 1$ y $7^{100} = (7^4)^{25} \equiv 1$ . Por los chinos teorema del resto (Ejercicio 6.8), $7^{100} \equiv 1 \pmod{100}$ : los dos últimos dígitos son $01$ .

Ejercicio 6.10 ★★★

Para $m, n \in \N^*$ , demuestre que $\gcd(2^m - 1,\, 2^n - 1) = 2^{\gcd(m,n)} - 1$ . Hint: show first that the remainder of $2^m - 1$ mod $2^n - 1$ is $2^r - 1$ where $r$ is the remainder of $m$ mod $n$ ; then follow the algoritmo euclidiano.

Solución

Solución de Ejercicio 6.10.

Escriba $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 $2^{nq} - 1 = (2^n - 1)(2^{n(q-1)} + \dots + 1)$ . Entonces mod $2^n - 1$ , $\;2^m - 1 \equiv 2^r - 1$ , y desde $0 \leq 2^r - 1 < 2^n - 1$ , este is es el resto euclidiano.

Por lo tanto el algoritmo euclidiano en el par $(2^m - 1, 2^n - 1)$ refleja, exponente por exponente, el algoritmo de $(m, n)$ : cada uno El paso de división reemplaza $(m, n)$ por $(n, r)$ arriba y $(2^m - 1, 2^n - 1)$ por $(2^n - 1, 2^r - 1)$ abajo. El algoritmo de arriba termina en $\gcd(m,n)$ , por lo que abajo termina en $2^{\gcd(m,n)} - 1$ .

Ejercicio 6.11 ★★★

(Teorema de Wilson) Sea $p$ un primo. demostrar que

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

emparejando cada factor de $(p-1)!$ con su mod inverso $p$ y identificar los factores autoemparejados (resolver $x^2 \equiv 1 \pmod p$ primero). Verifique lo contrario: si $n \geq 2$ no es primo, entonces $(n-1)! \not\equiv -1 \pmod n$ .

Solución

Solución de Ejercicio 6.11.

Primero resuelva $x^2 \equiv 1 \pmod p$ : $p \mid (x-1)(x+1)$ , entonces por 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)$ , cada El factor $a$ es mod $p$ invertible, y su inverso $a^{-1}$ es nuevamente uno de los factores (Proposición 6.20). Empareje cada $a$ con $a^{-1}$ : los pares se multiplican a $1$ , excepto que los factores autoemparejados ( $a = a^{-1}$ , es decir, $a^2 \equiv 1$ ) son independientes — y estos son exactamente $1$ y $p - 1$ . Por lo tanto

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

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

Conversar. Sea $n \geq 2$ compuesto, $n = ab$ con $1 < a \leq b < n$ . Si $a < b$ , ambos aparecen como factores distintos de $(n-1)!$ , entonces $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$ , por lo que $n = a^2 \mid a \times 2a \mid (n-1)!$ , misma conclusión; 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$ .

Demuestre que $F_0 F_1 \cdots F_{n-1} = F_n - 2$ para $n \geq 1$ (inducción).
Deduzca que los números de Fermat son coprimo por pares.
Deducir una segunda prueba, independiente de Teorema 6.14, 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 .$
Dejemos $m < n$ y $d = \gcd(F_m, F_n)$ . Por (1), $F_m$ divide $F_n - 2$ , entonces $d$ divide tanto $F_n$ como $F_n - 2$ , por lo tanto divide $2$ . Pero todo número de Fermat es impar, por lo que $d = 1$ .
Cada $F_n \geq 3$ tiene un divisor primo $p_n$ (El primer paso de Teorema 6.14). Si $m \neq n$ , entonces $p_m \neq p_n$ , ya que un primo común dividir $\gcd(F_m, F_n) = 1$ . La aplicación $n \mapsto p_n$ es por lo tanto inyectivo de $\N$ al primos: hay infinitos primos.

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

Problema 6.1

¿Con cuántos ceros termina la escritura decimal de $1000!$ — y, más profundamente, ¿Cuál es la potencia exacta de un primo $p$ dividiendo $n!$ , o dividiendo un coeficiente binomial? Las respuestas completas son dos joyas de 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 teorema de kummer: $v_p\binom{m+n}m$ cuenta el lleva al sumar $m$ y $n$ en la base $p$ . Este problema prueba ambos, los comprueba. unos contra otros numéricamente, y cosecha el clásico consecuencias — ceros a la derecha, la paridad del triángulo de Pascal, y un primer límite en la dirección del teorema número primo. En todo momento, $p$ es primo, $\floor{x}$ es la parte entera y $s_p(n)$ denota la suma de los dígitos de $n$ escritos en base $p$ .

Parte I — Floors, valuations, and Legendre’s formula.

Calentamiento: calcule $10!$ y lea su número de ceros; calcular $v_2(10!)$ y $v_5(10!)$ directamente desde el factorización de cada factor $1, 2, \dots, 10$ .
Demuestre que para $x \in \R$ y $n \in \N^*$ , $\bigl\lfloor \lfloor x \rfloor / n \bigr\rfloor = \lfloor x/n \rfloor$ .
Demuestre que $v_p(a + b) \geq \min\bigl(v_p(a), v_p(b)\bigr)$ para todos los $a, b \in \N^*$ , con igualdad siempre que $v_p(a) \neq v_p(b)$ .
Demuestre que el número de múltiplos de $m$ en $\intint1n$ es $\lfloor n/m \rfloor$ .
Demuestre La fórmula de Legendre.: por cada $n \in \N^*$ ,

$v_p(n!) = \sum_{k=1}^{\infty} \Bigl\lfloor \frac{n}{p^k} \Bigr\rfloor$

(una suma finita: los términos desaparecen una vez $p^k > n$ ). Count, for each $k$ , the factors of $\intint1n$ divisible by $p^k$ : each contributes exactly one unit per level it reaches.

Parte II — The digital form and trailing zeros.

Calcule $v_5(1000!)$ y $v_2(1000!)$ y concluya: ¿cómo ¿Cuántos ceros terminan en $1000!$ ?
Demuestre la forma digital de la fórmula de Legendre: escribiendo $n = \sum_i a_i p^i$ en la base $p$ ,

$v_p(n!) = \frac{n - s_p(n)}{p - 1} .$
Dos consecuencias para $p = 2$ : demostrar que $2^n$ nunca divide $n!$ , y que $2^{n-1}$ divide $n!$ exactamente cuando $n$ es una potencia de $2$ .
Limita el defecto: muestra $\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 largo plazo, una proporción $\frac1{p-1}$ de un factor $p$ se acumula por unidad.
Sea $Z(n) = v_5(n!)$ el número de ceros finales de $n!$ . Muestra $Z(n) - Z(n-1) = v_5(n)$ , deduce que $Z$ se salta el valor $5$ por completo (calcule $Z(24)$ y $Z(25)$ ), y Demuestre que ningún factorial termina exactamente en cinco ceros.

Parte III — Kummer’s theorem.

Demuestre que $\lfloor x + y \rfloor - \lfloor x \rfloor - \lfloor y \rfloor \in \{0, 1\}$ para todos los $x, y \in \R$ , y deducir 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, cada uno igual a $0$ o $1$ .
Demuestre teorema de kummer: el $k$ -ésimo término de esa suma es igual a $1$ exactamente cuando la suma de $m$ y $n$ en la base $p$ produce un acarreo a la posición $k$ ; por lo tanto $v_p\binom{m+n}m$ es el número total de acarreos. (Write $m = p^km_1 + m_0$ and $n = p^kn_1 + n_0$ with $0 \leq m_0, n_0 < p^k$ and inspect $\lfloor (m_0 + n_0)/p^k \rfloor$ .)
Deduzca eso para $0 < j < p^k$ :

$v_p\binom{p^k}{j} = k - v_p(j) ,$

contando los acarreos en la suma $j + (p^k - j)$ . (En particular $p \mid \binom p j$ para $0 < j < p$ : el paso clave de Teorema 6.23, recuperado).
Demuestre que $v_2\binom{2n}n = s_2(n)$ . Deducir que el central coeficiente binomial siempre es par, y eso $\binom{2n}n \equiv 2 \pmod 4$ exactamente cuando $n$ es una potencia de $2$ .
Show, usando la identidad de Vandermonde (Ejercicio 2.7) y la pregunta 13, que $\binom{2p}p \equiv 2 \pmod p$ por cada primo $p$ .
Calcular $v_3\binom{1000}{500}$ dos veces: una vez por Kummer (escriba $500$ en la base $3$ y cuente los acarreos en $500 + 500$ ), una vez por la forma digital de Legendre (calcule $s_3(500)$ y $s_3(1000)$ ); comprueba que ambos dan el mismo valor.

Parte IV — The parity of Pascal’s triangle, and a prime-density bound.

Demuestre el criterio de dígitos: $\binom nk$ es extraño si y sólo si cada dígito binario de $k$ es como máximo el dígito correspondiente de $n$ . Enuncie y demuestre lo análogo. criterio para $p \nmid \binom nk$ en la base $p$ .
Deduzca que la fila $n$ del triángulo de Pascal contiene exactamente $2^{s_2(n)}$ entradas impares; verifique en las filas $4$ y $5$ .
Deduzca que todas las entradas interiores $\binom nk$ ( $0 < k < n$ ) son pares si y sólo si $n$ es una potencia de $2$ .
Demuestre que cada potencia primo que divide a $\binom{m+n}m$ está en más $m + n$ : si $p^a \mid \binom{m+n}m$ entonces $p^a \leq m + n$ . (¿Cuántos términos distintos de cero puede tener la suma de pregunta 11 tiene?)
Deduce que $\binom{2n}n$ divide $\operatorname{lcm}(1, 2, \dots, 2n)$ y combinar con el límite inferior $\binom{2n}n \geq \frac{4^n}{2n+1}$ (lo cual comprobarás: la entrada central es la más grande de las entradas $2n + 1$ de la fila $2n$ ) para obtener

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

los múltiplos comunes de los primeros números enteros crecen exponencialmente — un primer vistazo cuantitativo de la abundancia de primos.

Part V — Synthesis.

Encuentre el $n$ más pequeño tal que $n!$ termine en al menos $2026$ ceros. (Estimate $Z(n) \approx n/4$ , then adjust using the exact formula.)
Una última verificación cruzada: muestre que $7$ divide no $\binom{100}{50}$ , primero escribiendo $50$ en la base $7$ y comprobando que la adición $50 + 50$ no tenga acarreo, luego calculando $v_7(100!)$ y $v_7(50!)$ con Legendre fórmula.
¿Dónde se utilizó exactamente el problema? (i) único factorización; (ii) la descomposición por división euclidiana $n = p^k n_1 + n_0$ ; (iii) un argumento de conteo de Capítulo 2? Una frase cada uno.
Síntesis, en un breve párrafo: La fórmula de Legendre gira una pregunta divisibilidad en aritmética de dígitos, y El teorema de Kummer lee la respuesta de los acarreos de uno Además — comentar sobre esta traducción, sobre los controles de pregunta 16, y sobre lo que sugiere el límite de la pregunta 21 sobre primos (el enunciado completo, el número primo teorema, está mucho más allá de este volumen; el polinomio Un análogo del conjunto de herramientas de este capítulo es Capítulo 8).

Solución

Solución de Problema 6.1.

1. $10! = 3\,628\,800$ : dos ceros finales. Valoraciones factor por factor: las potencias de $2$ provienen de $2, 4 = 2^2, 6, 8 = 2^3, 10$ , totalizando $v_2(10!) = 1 + 2 + 1 + 3 + 1 = 8$ ; poderes de $5$ de $5$ y $10$ : $v_5(10!) = 2$ . Ceros finales $= \min(v_2, v_5) = 2$ , consistentes.

2. Escribe la división euclidiana $\lfloor x\rfloor = nq + r$ , $0 \leq r \leq n - 1$ . Luego $x = nq + r + \{x\}$ con $0 \leq r + \{x\} < n$ , entonces $\lfloor x/n \rfloor = q = \bigl\lfloor \lfloor x \rfloor / n \bigr\rfloor$ .

3. Sea $\alpha = v_p(a) \leq \beta = v_p(b)$ (intercambiar si necesario) y escriba $a = p^\alpha a'$ , $b = p^\beta b'$ con $p \nmid a', b'$ . Luego $a + b = p^\alpha\bigl(a' + p^{\beta - \alpha}b'\bigr)$ , entonces $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 valoración es exactamente $\alpha$ .

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

5. Por factorización única, $v_p(n!) = \sum_{j=1}^{n} v_p(j)$ . Cuente de manera diferente: cada $j$ contribuye con $v_p(j) = \#\{k \geq 1 : p^k \mid j\}$ , por lo que

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 — Fórmula de Legendre. La suma es finita: términos con $p^k > n$ desaparecen.

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$ , por lo que hay $\min(994, 249) = 249$ de ellos.

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}$ (trunca la base- $p$ expansión). Sumando $k \geq 1$ e intercambiando los dos finitos sumas:

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)$ . Desde $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 $s_2(n) = 1$ si $n$ es un poder de $2$ .

9. $n$ tiene $\lfloor \log_p n \rfloor + 1$ base- $p$ dígitos, cada uno como máximo $p - 1$ , por lo que $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 conteo de ceros finales salta $v_5(n)$ en cada múltiplo de $5$ y es constante en el medio. $Z(24) = \lfloor24/5\rfloor = 4$ y $Z(25) = 5 + 1 = 6$ : en $n = 25$ el conteo salta de $4$ directamente a $6$ ( $v_5(25) = 2$ ), y dado que $Z$ no es decreciente con $Z \leq 4$ antes y $Z \geq 6$ después, el valor $5$ nunca se alcanza: no El factorial termina exactamente en cinco ceros.

11. Escribe $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 el último piso. $0$ o $1$ . Luego, por Legendre aplicado 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$ s y $1$ s (aplicar la primera afirmación a $x = m/p^k$ , $y = n/p^k$ ).

12. Corrija $k \geq 1$ y escriba $m = p^km_1 + m_0$ , $n = p^kn_1 + n_0$ con $0 \leq m_0, n_0 < p^k$ (división euclidiana: $m_0$ es el número formado por los dígitos bajos $k$ 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 es $1$ si es $m_0 + n_0 \geq p^k$ y $0$ en caso contrario. Pero $m_0 + n_0 \geq p^k$ dice precisamente que agregar los dígitos bajos $k$ de $m$ y $n$ se desborda a la posición $k$ — un acarreo a la posición $k$ en el algoritmo de suma de libros escolares. Resumiendo $k$ : $v_p\binom{m+n}m$ es el número de acarreos en la base- $p$ Además $m + n$ . (Kummer, 1852.)

13. Aplicar Kummer a $m = j$ , $n = p^k - j$ , suma $p^k = (1\underbrace{0\cdots0}_{k})_p$ . Sea $a = v_p(j)$ , entonces la base- $p$ Los dígitos de $j$ en las posiciones $0, \dots, a-1$ son $0$ y el dígito en la posición $a$ es distinto de cero. Los dígitos de $p^k - j$ 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$ , los dos dígitos distintos de cero deben sumar $p$ (dígito de resultado $0$ ): uno lleva; en cada posición $a+1, \dots, k-1$ , dígitos más el suma de acarreo entrante a $p$ (dígito de resultado $0$ nuevamente): el acarreo se propaga. Total: $k - a$ lleva, por lo que $v_p\binom{p^k}j = k - v_p(j)$ . Para $k = 1$ : $v_p\binom pj = 1$ para $0 < j < p$ , el divisibilidad utilizado en Teorema 6.23.

14. Mediante la forma digital (pregunta 7), utilizando $s_2(2n) = s_2(n)$ (agregando un dígito 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 un 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), entonces $\binom pj^2 \equiv 0 \pmod p$ ; los términos finales dan $1 + 1$ : $\binom{2p}p \equiv 2 \pmod p$ .

16. Base $3$ : $500 = 486 + 9 + 3 + 2$ , dígitos (bajo a alto) $(2, 1, 1, 0, 0, 2)$ , entonces $s_3(500) = 6$ ; y $1000 = 729 + 243 + 27 + 1$ , dígitos $(1, 0, 0, 1, 0, 1, 1)$ , entonces $s_3(1000) = 4$ . Kummer: agrega $500 + 500$ en la base $3$ : posición $0$ : $2 + 2 = 4$ , dígito $1$ lleva $1$ ; posición $1$ : $1 + 1 + 1 = 3$ , dígito $0$ llevar $1$ ; posición $2$ : $1 + 1 + 1 = 3$ , dígito $0$ lleva $1$ ; posición $3$ : $0 + 0 + 1 = 1$ , sin acarreo; posición $4$ : $0$ ; posición $5$ : $2 + 2 = 4$ , dígito $1$ lleva $1$ ; posición $6$ : tierras de acarreo: dígito $1$ . Cuatro acarreos: $v_3\binom{1000}{500} = 4$ . Leyenda: $v_3(1000!) = \frac{1000 - 4}2 = 498$ y $v_3(500!) = \frac{500 - 6}2 = 247$ , entonces $v_3\binom{1000}{500} = 498 - 2\times247 = 4$ . Los dos cálculos concuerdan — y el Los dígitos de suma $(1, 0, 0, 1, 0, 1, 1)$ reproducen $1000$ , tal como debe.

17. Por Kummer ( $p = 2$ , $m = k$ , $n' = n - k$ ): $\binom nk$ es impar si la suma $k + (n - k)$ en la base $2$ tiene sin acarreo, si en cada posición los dígitos satisfacen $k_i + (n - k)_i = n_i$ ; en ese caso $k_i \leq n_i$ para todos los $i$ . Por el contrario, si $k_i \leq n_i$ para todos los $i$ , entonces el número con dígitos $n_i - k_i$ es $n - k$ y la suma no tiene acarreo. Misma prueba en base. $p$ : $p \nmid \binom nk$ si cada dígito de base $p$ de $k$ está en más el dígito correspondiente de $n$ .

18. Contando el $k \in \intint0n$ cuyos dígitos obedecen $k_i \leq n_i$ : cada dígito de $k$ se elige de forma independiente entre Valores $n_i + 1$ , que dan opciones a $\prod_i (n_i + 1)$ ; en la base $2$ Este es $2^{\#\{i : n_i = 1\}} = 2^{s_2(n)}$ . Fila $4 = (100)_2$ : $2^1 = 2$ entradas impares — de hecho $1, 4, 6, 4, 1$ tiene entradas impares entradas sólo en los extremos. Fila $5 = (101)_2$ : $2^2 = 4$ — de hecho $1, 5, 10, 10, 5, 1$ .

19. Todas las entradas interiores, incluso $\iff$ , la fila tiene exactamente $2$ entradas impares (los dos extremos siempre son impares) $\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 término $k$ desaparece como tan pronto como $p^k > m + n$ (los tres pisos son entonces iguales, de hecho el primero es $0$ cuando $p^k > m+n$ ; más simplemente cada término es $0$ ). Por lo tanto, como máximo los términos $\lfloor \log_p(m+n)\rfloor$ son distintos de cero, cada uno vale $1$ : $a = v_p\binom{m+n}m \leq \log_p(m+n)$ , es decir $p^a \leq m + n$ .

21. Por cada primo $p$ , $v_p\bigl(\operatorname{lcm}(1, \dots, 2n)\bigr) = \lfloor\log_p(2n)\rfloor$ (la mayor potencia de $p$ no superior a $2n$ aparece entre $1, \dots, 2n$ ). Pregunta 20 con $m = n$ da $v_p\binom{2n}n \leq \lfloor\log_p(2n)\rfloor$ por cada $p$ : por Proposición 6.16, $\binom{2n}n \mid \operatorname{lcm}(1, \dots, 2n)$ . Para el tamaño: la proporción $\binom{2n}{k+1}/\binom{2n}k = \frac{2n-k}{k+1} \geq 1$ exactamente para $k < n$ , por lo que la entrada central es la más grande de $2n + 1$ entradas 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 hubiera pocos primos debajo de $2n$ , el mcm no podría ser este grande: el crecimiento exponencial del mcm es una traza cuantitativa de la abundancia de primos.

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

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

Dado que $Z$ es constante entre múltiplos de $5$ y $Z(8119) = Z(8115) = 2025$ , el $n$ más pequeño con al menos $2026$ al final ceros es $n = 8120$ .

23. Base $7$ : $50 = 49 + 1$ , dígitos (de menor a mayor) $(1, 0, 1)$ . Añadiendo $50 + 50$ : posición $0$ : $1 + 1 = 2 < 7$ , sin acarreo; posición $1$ : $0 + 0 = 0$ ; posición $2$ : $1 + 1 = 2 < 7$ , no llevar. Sin transporte, por Kummer $v_7\binom{100}{50} = 0$ : $7 \nmid \binom{100}{50}$ . Legendre está de acuerdo: $v_7(100!) = \lfloor 100/7 \rfloor + \lfloor 100/49 \rfloor = 14 + 2 = 16$ y $v_7(50!) = 7 + 1 = 8$ , entonces $v_7\binom{100}{50} = 16 - 2\times8 = 0$ .

24. (i) La factorización única subyace a la misma definición de $v_p$ y su aditividad, de ahí la fórmula de Legendre y cada conclusión divisibilidad (Proposición 6.16). (ii) División euclidiana producida la identidad de truncamiento de la pregunta 2 y la división $m = p^km_1 + m_0$ que aísla el acarreo (pregunta 12). (iii) Conteo: el recuento de múltiplos de $m$ (pregunta 4), el producto de elección de dígitos (pregunta 18) y el límite de suma de filas $4^n \leq (2n+1)\binom{2n}n$ (pregunta 21) son todos XXXP0506Argumentos estilo XXX.

25. Legendre convierte “qué poder de $p$ divide $n!$ ” en aritmética de dígitos base $p$ ; Kummer comprime el respuesta para coeficientes binomiales en los acarreos de un solo Además — divisibilidad, aparentemente una propiedad global de enorme números, se lee localmente, cifra a cifra. La pregunta 16 es la paradigma: cuatro acarreos, calculados a mano, determinan la cantidad exacta potencia de $3$ en un número con cientos de dígitos. Y la pregunta 21 muestra el mismo círculo de ideas rozando aguas profundas: una El límite inferior exponencial para $\operatorname{lcm}(1, \dots, 2n)$ es un primer paso completamente elemental hacia el teorema número primo, cuya prueba se encuentra mucho más allá de este volumen. Todo el kit de herramientas — división, mcd, valoraciones — se repite para polinomios en Capítulo 8, donde el análogo de una expansión de dígitos es ampliación de poderes de $(X - a)$ .