Matemáticas de secundaria · Grades 10–12

29Aritmética

La aritmética estudia el números enteros: divisibilidad, numeros primos, restos. Considerada durante mucho tiempo la más pura de las matemáticas puras, ahora protege todas las aplicaciones en línea. pago: el criptosistema RSA se basa en los teoremas de Bézout, Gauss y Fermat lo demostró en este capítulo.

29.1 Divisibilidad y división euclidiana

Definición 29.1 (Divisibilidad)

Deje $a, b \in \Z$ . Decimos $b$ divide $a$ , escrito $b \mid a$ , si existe $k \in \Z$ con $a = kb$ . También decimos que $a$ es un múltiple de $b$ .

Proposición 29.2

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

Demostración. Escriba $a = kc$ , $b = lc$ : luego $au + bv = (ku + lv)c$ . Los otros puntos seguir desde $\abs{a} = \abs{k}\,\abs{b}$ con $\abs k \geq 1$ cuando $b = ka \neq 0$ . ∎

Teorema 29.3 (división euclidiana)

Sean $a \in \Z$ y $b \in \N^*$ . Existe un par único $(q, r) \in \Z \times \N$ tal que

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

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

Demostración. Existencia. El conjunto de múltiplos de $b$ que no exceden $a$ tiene un elemento más grande $bq$ (no está vacío y es delimitado arriba); establezca $r = a - bq$ . Por maximalidad, $b(q+1) > a$ , entonces $0 \leq r < b$ . Unicidad. Si $bq + r = bq' + r'$ con $0 \leq r, r' < b$ , entonces $b(q - q') = r' - r$ y $\abs{r' - r} < b$ : un múltiplo de $b$ de absoluto valor menor que $b$ debe ser $0$ , por lo tanto $r = r'$ y $q = q'$ . ∎

29.2 Congruencias

Definición 29.4 (congruencia)

Deje $n \in \N^*$ . Dos números enteros $a, b$ son módulo congruente $n$ , escrito $a \equiv b \pmod n$ , si $n \mid (a - b)$ — de manera equivalente, si $a$ y $b$ tienen el mismo resto en euclidiano división por $n$ .

Proposición 29.5 (Compatibilidad con operaciones)

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

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

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

Método 29.6 (Módulo de potencias de cálculo $n$ )

Para calcular $a^k \bmod n$ , reduzca el módulo base $n$ , luego busque una pequeña potencia de $a$ congruente con $\pm1$ y utilícela para colapsar el exponente. Para instancia $2^{100} \bmod 7$ : desde $2^3 = 8 \equiv 1 \pmod 7$ y $100 = 3\times33 + 1$ ,

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

29.3 MCD, Bézout y Gauss

Definición 29.7 (MCD)

Sea $a, b$ números enteros, no ambos cero. El mayor común divisor $\gcd(a, b)$ es el entero más grande que divide ambos $a$ y $b$ . Cuando se dice que $\gcd(a,b) = 1$ , $a$ y $b$ son coprimo.

Proposición 29.8 (algoritmo de Euclides)

Si $a = bq + r$ ( $b \neq 0$ ), entonces $\gcd(a, b) = \gcd(b, r)$ . Iterando el división euclidiana por lo tanto calcula $\gcd(a,b)$ : el mcd es el último resto distinto de cero.

Demostración. Cualquier divisor común de $a$ y $b$ divide $r = a - bq$ (Proposición 29.2), por lo tanto es un divisor común de $b$ y $r$ ; y viceversa, desde $a = bq + r$ . Los dos pares tienen el mismo común divisores, por lo que lo mismo mcd. El algoritmo termina porque los restos forme estrictamente un decreciente secuencia de números enteros no negativo. ∎

Ejemplo 29.9

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

Teorema 29.10 (Identidad de Bézout)

Sea $a, b$ números enteros, no cero, y $d = \gcd(a,b)$ . existen $u, v \in \Z$ tal que

au + bv = d .

En particular, $a$ y $b$ son coprimo si y sólo si $au + bv = 1$ para algunos números enteros $u, v$ .

Demostración. Ejecute algoritmo de euclides al revés: cada resto es una combinación entero de los dos anteriores, y los datos iniciales $a, b$ son combinaciones de ellos mismos; mediante sustitución descendente, el último resto distinto de cero $d$ es un entero combinación de $a$ y $b$ . (En Ejemplo 29.9: $18 = 54 - 36 = 54 - (198 - 3\times54) = 4\times54 - 198 = 4(252 - 198) - 198 = 4\times252 - 5\times198$ .)

Para la equivalencia: si $\gcd(a,b) = 1$ , Bézout proporciona $u, v$ ; por el contrario, cualquier divisor común de $a$ y $b$ divide $au + bv = 1$ , forzando $\gcd(a,b) = 1$ . ∎

Teorema 29.11 (Lema de Gauss)

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

Demostración. Bézout da $au + bv = 1$ ; multiplicar por $c$ : $acu + bcv = c$ . Ambos términos de el lado izquierdo son múltiplos de $a$ (el segundo porque $a \mid bc$ ), por lo tanto también lo es $c$ . ∎

Corolario 29.12

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

Demostración. Escribe $c = ak$ . De $b \mid ak$ y $\gcd(a,b)=1$ , Gauss da $b \mid k$ , digamos $k = bl$ ; luego $c = abl$ . ∎

29.4 numeros primos

Definición 29.13 (Principal)

Un entero $p \geq 2$ es principal si es solo Los divisores positivos son $1$ y $p$ .

Proposición 29.14

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

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

Teorema 29.15 (Euclides)

Hay infinitos primos.

Demostración. Dada cualquier lista finita $p_1, \dots, p_k$ de primos, considere $N = p_1 p_2 \cdots p_k + 1$ . Algunos principal $p$ divide $N$ ; pero no $p_i$ divide $N$ (el resto es $1$ ), por lo que $p$ es un principal que no está en la lista. No La lista finita agota el primos. ∎

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

Cada entero $n \geq 2$ es un producto de primos, y esta factorización es único hasta el orden de los factores:

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

Demostración. Existencia, por inducción fuerte: $n$ principal es su propia factorización; de lo contrario $n = de$ con $2 \leq d, e < n$ , y ambos factorizan por la inducción hipótesis. Unicidad: supongamos $p_1\cdots p_s = q_1 \cdots q_t$ (primos, con repeticiones permitidas). Por lema de Euclides, $p_1$ divide algunos $q_j$ , y siendo principal, $p_1 = q_j$ ; cancelar y repetir. Las dos factorizaciones coinciden término por término. ∎

Teorema 29.17 (Pequeño teorema de Fermat)

Sea $p$ principal y $a \in \Z$ con $p \nmid a$ . entonces

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

Por cada $a \in \Z$ (no se asume coprimalidad), $a^p \equiv a \pmod p$ .

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

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

Desde $p$ divide ninguno de $1, \dots, p-1$ , uso repetido del lema de Euclides permite cancelar $(p-1)!$ , dejando $a^{p-1} \equiv 1$ . la segunda forma sigue multiplicando por $a$ (y es trivial cuando $p \mid a$ ). ∎

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

El teorema de Fermat hace que el módulo de exponenciación $n$ sea reversible cuando el los exponentes se eligen adecuadamente: el corazón del criptosistema RSA. Con $p, q$ grande primos y $n = pq$ , se publica $n$ y un exponente $e$ ; El cifrado es $x \mapsto x^e \bmod n$ . Descifrar requiere un exponente $d$ con $ed \equiv 1 \pmod{(p-1)(q-1)}$ , que solo alguien conoce $p$ y $q$ pueden calcular — y recuperar $p, q$ de $n$ significa factorización a número de cientos de dígitos, algo que ningún algoritmo conocido hace en términos razonables. tiempo.

29.5 Ceremonias

Ejercicio 29.1 ★

Calcule el cociente y el resto de división euclidiana de $2026$ mediante $17$ , y de $-2026$ por $17$ .

Solución

Solución de Ejercicio 29.1.

$17 \times 119 = 2023$ , entonces $2026 = 17 \times 119 + 3$ : cociente $119$ , resto $3$ . Para $-2026$ : $-2026 = 17\times(-120) + 14$ (de hecho $17 \times 120 = 2040$ y $2040 - 2026 = 14$ ): cociente $-120$ , resto $14$ (el resto debe estar en $\intco{0}{17}$ , por lo que es no $-3$ ).

Ejercicio 29.2 ★

¿Cuál es el resto de $7^{100}$ módulo $10$ ? (¿Cuál es el último dígito de $7^{100}$ ?)

Solución

Solución de Ejercicio 29.2.

Módulo $10$ : $7^2 = 49 \equiv 9 \equiv -1$ . Por lo tanto $7^{100} = \left(7^2\right)^{50} \equiv (-1)^{50} = 1 \pmod{10}$ : el último El dígito de $7^{100}$ es $1$ .

Ejercicio 29.3 ★

Usando algoritmo de euclides, calcule $\gcd(1071, 462)$ y encuentre números enteros $u, v$ con $1071u + 462v = \gcd(1071, 462)$ .

Solución

Solución de Ejercicio 29.3.

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

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

Ejercicio 29.4 ★

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

Solución

Solución de Ejercicio 29.4.

Cada entero es $\equiv 0, 1, 2$ o $3 \pmod 4$ , y elevando al cuadrado: $0^2 \equiv 0$ , $1^2 \equiv 1$ , $2^2 = 4 \equiv 0$ , $3^2 = 9 \equiv 1$ . entonces $n^2 \equiv 0$ o $1 \pmod 4$ . Entonces una suma de dos cuadrados es congruente con $0 + 0$ , $0 + 1$ o $1 + 1$ , i.e. a $0$ , $1$ o $2 \pmod 4$ — nunca a $3$ .

Ejercicio 29.5 ★★

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

Solución

Solución de Ejercicio 29.5.

Divisibilidad por $2$ : entre $n$ y $n + 1$ , uno está par. Divisibilidad por $3$ : si $n \equiv 0$ , entonces $3 \mid n$ ; si $n \equiv 1 \pmod 3$ , entonces $2n + 1 \equiv 3 \equiv 0$ ; si $n \equiv 2$ , entonces $n + 1 \equiv 0$ . en total casos $3$ divide el producto. Desde $\gcd(2,3) = 1$ , Corolario 29.12 da $6 \mid n(n+1)(2n+1)$ . (Esto también vuelve a probar que $\frac{n(n+1)(2n+1)}{6}$ , la suma de los cuadrados de Ejercicio 20.1, es un entero).

Ejercicio 29.6 ★★

Resuelva en $\Z$ el congruencia $5x \equiv 3 \pmod{11}$ . (Pista: encuentre el inverso de $5$ módulo $11$ .)

Solución

Solución de Ejercicio 29.6.

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

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

Las soluciones son números enteros $x = 5 + 11k$ , $k \in \Z$ . (Compruebe: $5\times5 = 25 \equiv 3 \pmod{11}$ .)

Ejercicio 29.7 ★★

Resuelve en $\Z \times \Z$ el Diofantino ecuación

17x - 40y = 1,

luego describa todas las soluciones de $17x - 40y = 6$ .

Solución

Solución de Ejercicio 29.7.

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

Solución general de $17x - 40y = 1$ : restando la relación particular, $17(x + 7) = 40(y + 3)$ ; desde $\gcd(17, 40) = 1$ , Gauss da $40 \mid x + 7$ , entonces $x = -7 + 40k$ y luego $y = -3 + 17k$ , $k \in \Z$ (todos los cuales verifican).

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

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

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

Ejercicio 29.8 ★★

Demuestre que $\sqrt2$ es irracional, utilizando la unicidad de principal factorización (compare el exponente de $2$ en ambos lados de $a^2 = 2b^2$ ).

Solución

Solución de Ejercicio 29.8.

Supongamos $\sqrt2 = \frac ab$ con $a, b \in \N^*$ ; luego $a^2 = 2b^2$ . en el principal factorización de un cuadrado, todo exponente es par; entonces el exponente de $2$ en $a^2$ es par, mientras que en $2b^2$ es impar (uno más que un par número). Dos factorizaciones del mismo entero con diferentes exponentes de $2$ contradice la unicidad en Teorema 29.16. Por lo tanto no hay tal existe fracción: $\sqrt2 \notin \Q$ .

Ejercicio 29.9 ★★★

Sea $p$ un principal.

Muestre eso para $1 \leq k \leq p - 1$ , $p$ divide $\dbinom{p}{k}$ . (Sugerencia: utilice $k\binom pk = p\binom{p-1}{k-1}$ , Ejercicio 27.7, y el lema de Gauss.)
Deduzca, por inducción sobre $a \geq 0$ , otra prueba de la pequeña teorema en la forma $a^p \equiv a \pmod p$ .

Solución

Solución de Ejercicio 29.9.

1. De $k\binom pk = p \binom{p-1}{k-1}$ , $p$ divide $k\binom pk$ . Para $1 \leq k \leq p-1$ , $p \nmid k$ y $p$ principal proporcione $\gcd(p, k) = 1$ , por lo que el lema de Gauss produce $p \mid \binom pk$ .

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

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

todos los términos medios desaparecen módulo $p$ por el punto 1. Por inducción hipótesis, $(a+1)^p \equiv a + 1 \pmod p$ . Esto prueba $a^p \equiv a$ para todo $a \in \N$ , y el caso $a < 0$ sigue por escrito $a \equiv a + kp$ para un representante positivo adecuado.

Ejercicio 29.10 ★★★

(Problema del resto chino). Encuentra todos los números enteros $n$ tales que

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

(Pista: resuelva las dos primeras condiciones, luego incorpore la tercera; Bézout los coeficientes ayudan.)

Solución

Solución de Ejercicio 29.10.

$n \equiv 2 \pmod 3$ y $n \equiv 3 \pmod 5$ : escriba $n = 2 + 3s$ ; entonces $2 + 3s \equiv 3 \pmod 5$ , i.e. $3s \equiv 1 \pmod 5$ . lo inverso de $3$ módulo $5$ es $2$ ( $3\times2 = 6 \equiv 1$ ), por lo que $s \equiv 2 \pmod 5$ , digamos $s = 2 + 5t$ y $n = 8 + 15t$ : las dos primeras condiciones significar $n \equiv 8 \pmod{15}$ .

Agregando $n \equiv 2 \pmod 7$ : $8 + 15t \equiv 2 \pmod 7$ , y $15 \equiv 1 \pmod 7$ , entonces $t \equiv -6 \equiv 1 \pmod 7$ , digamos $t = 1 + 7u$ . Por lo tanto $n = 23 + 105u$ :

n \equiv 23 \pmod{105}.

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

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

Problema 29.1

Problema de fin de semana — las congruencias protegen cada código de barras y tarjeta de crédito, y el pequeño teorema de Fermat ejecuta el bloquear los secretos del mundo

G. H. Hardy se jactaba en 1940 de que la teoría de números era "inmaculada" por aplicaciones. Ochenta años después, cada código de barras emite un pitido, cada pago con tarjeta de crédito y cada mensaje cifrado lo contradice — exactamente con las herramientas de este capítulo: congruencias (Proposición 29.5), Bézout inversas (Teorema 29.10) y el pequeño teorema de Fermat (Ejercicio 29.9). Este problema verifica los códigos, rompe un versión de juguete de la cerradura y aprende por qué la cerradura real se mantiene firme.

Parte I — Congruencia fluency.

Calcular $2026 \bmod 7$ ; luego el último dígito de $7^{100}$ (encontrar el ciclo de potencias del módulo $7$ $10$ ).
Exponenciación rápida (Método 29.6): calcular $5^{117} \bmod 13$ (comenzar desde $5^2 \equiv -1$ ).
Resuelve $3x \equiv 5 \pmod 7$ .
Ejecute algoritmo de euclides en $(97, 35)$ , sustitución hacia atrás para encontrar números enteros $u, v$ con $97u + 35v = 1$ , y deducir el inverso de $35$ módulo $97$ .
Indique precisamente cuando $a$ es módulo invertible $n$ , y cuyo teorema entrega lo inverso.

Parte II — Check digits.

ISBN-10: los diez dígitos $d_1 \dots d_{10}$ de un libro el código debe satisfacer $10d_1 + 9d_2 + \dots + 2d_9 + 1d_{10} \equiv 0 \pmod{11}$ . Verificar el ISBN real $0\,306\,40615\,2$ .
Demostrar que el esquema ISBN detecta cada Error de un solo dígito: si un dígito cambia por $d \not\equiv 0$ , la suma ponderada cambia en $w d$ con $1 \leq w \leq 10$ — ¿por qué esto nunca puede ser? $\equiv 0 \pmod{11}$ (Teorema 29.11)?
Demuestre que también detecta cada transposición de dos dígitos adyacentes (distintos). Luego explica el diseño. secreto: qué propiedad de $11$ hizo que ambas pruebas funcionaran, ¿Y qué podría salir mal con módulo $10$ ?
Los códigos de barras EAN-13 pesan los dígitos $1, 3, 1, 3, \dots$ módulo $10$ . Calcular el dígito de control completando $978\,2940199\,05$ . ¿Qué transposiciones adyacentes hacen EAN fallar para detectar? (Cuando es $2(a - b) \equiv 0 \pmod{10}$ ?)
Las tarjetas de crédito utilizan el esquema de Luhn: desde la derecha, doble cada segundo dígito (restando $9$ cuando el doble excede $9$ ), suma todo y requiere un múltiplo de $10$ . Verificar el número de prueba $4539\,1488\,0343\,6467$ .
En una frase: ¿qué compró el ISBN principal módulo? que EAN y Luhn, encadenados a $10$ , no pueden tener?

Parte III — Fermat’s lock.

Una trampa ante el tesoro: computar $2^{10} \bmod 341$ , deducir $2^{340} \bmod 341$ — y luego factorice $341$ . ¿Qué significa este ejemplo (un Fermat pseudoprime) dicen sobre el uso de Fermat ¿Pequeño teorema como prueba de primalidad?
RSA en miniatura: tome $p = 3$ , $q = 11$ , entonces $n = 33$ y $(p-1)(q-1) = 20$ ; el exponente público es $e = 3$ . Encuentra el exponente privado $d$ con $3d \equiv 1 \pmod{20}$ (método de la pregunta 4).
Cifrar el mensaje $m = 4$ : calcular $c = m^3 \bmod 33$ .
Descifrar: calcular $c^d \bmod 33$ (usar $c \equiv -2 \pmod{33}$ ) y recuperar el mensaje.
Por qué el descifrado siempre funciona: demuestre que $m^{21} \equiv m$ tanto el módulo $3$ como el módulo $11$ (El pequeño teorema de Fermat en cada mundo), y concluir módulo $33$ (Teorema 29.11 pega los dos congruencias). ¿De dónde surgió el formulario especial de $21 = ed$ ? $1 + 20k$ entrar?
La seguridad de la cerradura: todos conocen $n$ y $e$ ; recuperar $d$ requiere $(p-1)(q-1)$ , de ahí los factores de $n$ . Nuestros factores $33$ a la vista — ¿por qué hace lo mismo? esquema, con $n$ de seiscientos dígitos, protege el los bancos del mundo? (Una frase sobre la asimetría entre multiplicando y factorización.)

Parte IV — Classics.

El viejo conde de soldados chinos (compárese Ejercicio 29.10): salen varios soldados resto $2$ cuando se clasifica por $3$ y resto $3$ cuando Clasificado por $5$ . Encuentre todos los recuentos posibles y explique por qué la respuesta es módulo único $15$ .
Por fin pruebas de una línea: de $10 \equiv 1 \pmod 9$ , demostrar que todo número es congruente con la suma de sus dígitos módulo $9$ ; de $10 \equiv -1 \pmod{11}$ , derivar el regla de suma alterna para $11$ . (La escuela secundaria El volumen demostró esto con álgebra explícita — admirar la compresión.)
Final — Hardy contra el código de barras: recapitula el kit de herramientas del capítulo (congruencia aritmética, Bézout inversas, pequeño teorema de Fermat, pegado coprimo módulos) y dónde cada uno encajó en su lugar en este problema; luego dé el veredicto moderno sobre “inmaculado”.

Solución

Solución de Problema 29.1.

1. $2026 = 289 \times 7 + 3$ : $2026 \equiv 3 \pmod 7$ . Potencias de $7$ mod $10$ : $7, 9, 3, 1$ , ciclo de longitud $4$ ; $100 \equiv 0 \pmod 4$ : último dígito de $7^{100}$ es $1$ .

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

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

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

5. $a$ es módulo invertible $n$ exactamente cuando $\gcd(a, n) = 1$ : Bézout proporciona $au + nv = 1$ , es decir $au \equiv 1$ ; por el contrario, una inversa obliga al mcd a dividirse $1$ .

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

7. La suma cambia en $wd$ con $1 \leq w \leq 10$ y $1 \leq \abs d \leq 9$ : ya que $11$ es principal y divide ningún factor, no puede dividir el producto (Teorema 29.11 / Proposición 29.14): la suma modificada nunca más será $\equiv 0$ : cada dígito error activa la alarma.

8. Intercambio de dígitos adyacentes $a, b$ (pesos $w + 1, w$ ) cambia la suma por $(w+1)b + wa - (w+1)a - wb = b - a \not\equiv 0$ para $a \neq b$ : detectado. El secreto es el primalidad de $11$ : módulo $10$ , productos como $5 \times 2$ desaparecen con ni factor cero, por lo que un error de peso- $5$ de $\pm 2$ (o un transposición desafortunada) podría pasar desapercibida.

9. Suma ponderada de los doce dígitos: $119$ ; el dígito de control debe completarlo a un múltiplo de $10$ : $1$ (completo código $978\,2940199\,051$ ). EAN pierde transposiciones adyacentes con $2(a - b) \equiv 0 \pmod{10}$ , es decir $\abs{a - b} = 5$ : intercambiar un $2$ y un $7$ , digamos, pasa invisible — el precio del amigable módulo $10$ .

10. Duplicar cada segundo dígito desde la derecha y plegado ( $16 \to 7$ , etc.), la suma llega a $80 \equiv 0 \pmod{10}$ : la tarjeta de prueba valida.

11. Con un principal módulo cada peso es invertible, entonces todo errores únicos y todo adyacentes se atrapan las transposiciones — lujo del ISBN; esquemas mod- $10$ mantenga dígitos amigables para los humanos y acepte un punto ciego corto.

12. $2^{10} = 1024 = 3 \times 341 + 1 \equiv 1 \pmod{341}$ , por lo tanto $2^{340} = \left(2^{10}\right)^{34} \equiv 1$ . Sin embargo, $341 = 11 \times 31$ es compuesto: pasa la prueba de Fermat. prueba en la base $2$ sin ser principal. Moraleja: Fermat congruencia es necesario, no suficiente — pruebas de primalidad necesita herramientas más afiladas (y las consigue, en la universidad) volúmenes).

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

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

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

16. Módulo $3$ : si $3 \nmid m$ , $m^2 \equiv 1$ (Fermat), entonces $m^{21} = m \cdot \left(m^2\right)^{10} \equiv m$ ; si $3 \mid m$ , ambos lados son $\equiv 0$ . Módulo $11$ : $m^{10} \equiv 1$ o $11 \mid m$ , y $m^{21} = m \cdot \left(m^{10}\right)^2 \equiv m$ . Ambos $3$ y $11$ dividen $m^{21} - m$ , y siendo coprimo su producto $33$ también lo hace (Gauss): $m^{21} \equiv m \pmod{33}$ . el exponente $ed = 21 = 1 + 20k$ fue construido de manera que tanto Fermat los exponentes ( $2$ y $10$ , dividiendo $20$ ) desaparecen.

17. Multiplicar dos dígitos $300$ primos toma un microsegundo; recuperarlos de su producto derrota todos los algoritmo conocido y todas las computadoras del mundo — la cerradura es una calle de un solo sentido. (Nuestro $n = 33$ es la calle a escala de juguete, transitable en ambas direcciones).

18. Residuos de prueba (o edificio con Bézout): $n \equiv 8 \pmod{15}$ : los conteos $8, 23, 38, 53, \dots$ Módulo de unicidad $15$ : dos soluciones se diferencian por un múltiplo de $3$ y de $5$ , por tanto de $15$ ( $3$ y $5$ coprimo, Gauss). El general con soldados $1000$ anuncia “ $8$ ” a las tres alineaciones rápidas: el antiguo truco del recuento.

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

20. Congruencias convirtió los restos en una aritmética (Parte I); Bézout acuñó las inversas que resuelven linealmente congruencias y $d$ de RSA (preguntas 4, 13); El pequeño de Fermat teorema abrió y cerró la cerradura (preguntas 15-16); pegando coprimo módulos contaron soldados y terminaron la prueba. (preguntas 16, 18). Veredicto sobre Hardy: el teorema más puro que él sabía ahora guarda cada compra — la pureza, con el tiempo, es la lo más aplicable que existe.