A.6 · Congruencias, divisibilidad y funciones aritméticas

Preparación de GRE para grado universitario. Objetivos locales dentro del alcance revisado de ETS; esto es enseñanza original, no una prueba oficial ni un predictor de puntuación.

Prerrequisitos: algoritmo de Euclides, factores primos y aritmética modular.

• Resolver congruencias lineales usando condiciones de mcd
• Combinar congruencias coprimas con el teorema chino del resto
• Aplicar el teorema de Euler solo a residuos invertibles
• Usar divisibilidad de exponentes primos para encontrar enteros admisibles mínimos

congruencia: Igualdad de residuos porque el módulo divide su diferencia.

totiente: La cuenta de residuos coprimos al entero positivo módulo.

La ecuación ax≡b módulo n tiene solución exactamente cuando d=mcd(a,n) divide a b. Si lo hace, divide a, b, n por d para obtener una ecuación con coeficiente invertible. Tiene una solución de residuo módulo n/d y d soluciones distintas módulo n. Dividir el coeficiente pero dejar el módulo original generalmente pierde soluciones. La factorización prima proporciona otra herramienta de divisibilidad: si n^k debe ser divisible por un producto de potencias primas p^a, cada exponente primo en n debe ser al menos ceil(a/k). Estos exponentes mínimos producen independientemente el menor entero admisible positivo n. Para n⁴ divisible por 2⁷·3⁵, n debe contener 2² y 3², así que el valor mínimo es 36. Esta es una condición de exponentes primos, no una congruencia resuelta por división modular.

El algoritmo extendido de Euclides expresa gcd(a,n) como ua+vn. Cuando el mcd es 1, u es un inverso de a módulo n. Elige un representante en el rango requerido tras la reducción. Para 7 y 26, 1=15·7−4·26, por lo que 15 es el inverso de 7 módulo 26; verifica el producto para detectar errores de signo.

Para módulos positivos coprimos m,n, el teorema chino del resto da exactamente una solución módulo mn para cada par de condiciones de residuo. Sustituye x=r+mk en la segunda congruencia y resuelve para k. Si los módulos no son coprimos, sus valores de residuo deben coincidir módulo gcd(m,n); cuando son consistentes, la unicidad es módulo el mínimo común múltiplo, no el producto.

El totiente de Euler phi(n) cuenta los residuos coprimos a n. Para divisores primos distintos p, phi(n)=n veces el producto de (1−1/p). El teorema de Euler da a^phi(n)≡1 solo cuando gcd(a,n)=1. El caso primo es el pequeño teorema de Fermat. Reduce exponentes solo después de verificar esta condición; un no-unitario puede volverse cero bajo potencias repetidas en cambio.

Resuelve 6x≡9 módulo 15. El mcd es 3 y divide a 9. Divide las tres cantidades para obtener 2x≡3 módulo 5; el inverso de 2 es 3, así que x≡9≡4 módulo 5. Las soluciones originales módulo 15 son 4,9,14. Para x≡2 módulo 4 y x≡3 módulo 7, escribe x=2+4k; entonces 4k≡1 módulo 7, dando k≡2. Por tanto x≡10 módulo 28.

La expresión a^phi(n)≡1 es falsa para a arbitrario. Por ejemplo 2 no es invertible módulo 8 y 2^4 es cero módulo 8.

Resuelve $8x\equiv12\pmod{20}$ completamente. Encuentra un inverso de 7 módulo 20. Explica por qué el teorema de Euler no puede usarse para reemplazar $2^8$ por 1 módulo 20.

Solución resuelta

El MCD es cuatro y divide 12. Dividir los tres números da $2x\equiv3\pmod5$, así que $x\equiv4\pmod5$. Módulo 20 las cuatro respuestas son $4,9,14,19$; la sustitución da residuo 12 cada vez. Dado que $7\cdot3=21$, el inverso de 7 es 3. Aunque $\phi(20)=8$, el teorema de Euler requiere una unidad. El MCD de 2 y 20 es dos, y $2^8=256\equiv16$, no 1.

Resolver $x\equiv2\pmod6$, $x\equiv5\pmod9$ o demostrar inconsistencia. Indicar el módulo para la unicidad. Encontrar el menor n positivo tal que $2^5\cdot3^7$ divida a $n^3$.

Verificar después de intentar

Los residuos coinciden módulo el mcd tres. Colocar $x=2+6k$: entonces $6k\equiv3\pmod9$, por consiguiente $2k\equiv1\pmod3$ y $k\equiv2\pmod3$. Así $x\equiv14\pmod{18}$. El módulo es el mcm, no 54. Para el problema de divisibilidad, escribir los exponentes primos en n. Deben satisfacer $3a\ge5$, $3b\ge7$, por lo tanto $a\ge2$, $b\ge3$. El menor n es $2^2\cdot3^3=108$; otros factores primos solo pueden aumentarlo.