Congruencias, divisibilidad y funciones aritméticas
Introducido| English | Significado |
|---|---|
| congruence/ˈkɒŋɡruːəns/ | congruencia |
| Chinese remainder theorem/tʃaɪˈniːz rɪˈmeɪndə ˈθɪərəm/ | Teorema chino del resto |
| totient/ˈtəʊʃənt/ | función totiente |
Cuando los ciclos se alinean
- Un engranaje se repite cada $4$ minutos, otro cada $7$. Estar en la posición $2$ del primer ciclo y en la posición $3$ del segundo significa encontrar un tiempo $x$ tal que $x\equiv2\pmod4$ y $x\equiv3\pmod7$.
- Las congruencias describen posiciones repetidas. El teorema chino del resto las combina; las pruebas de gcd, inversos modulares y exponentes primos indican cuáles pasos algebraicos son válidos.
Congruencia significa divisibilidad
- Una congruencia es una afirmación de que dos enteros tienen el mismo residuo módulo un entero positivo especificado. Aquí todas las variables son enteros y los módulos satisfacen $n\geq2$; $a\equiv b\pmod n$ significa exactamente que $n$ divide a $a-b$.
- Para $ax\equiv b\pmod n$, establezca $d=\gcd(a,n)$. Cualquier solución proporciona $ax-b=kn$ para algún entero $k$. Dado que $d$ divide tanto a $a$ como a $n$, debe dividir a $b$; si $d\nmid b$, no hay solución.
Por qué el mdc también cuenta soluciones
- La condición $d\mid b$ es suficiente también. Bézout da enteros $u,v$ con $ua+vn=d$; multiplicar por $b/d$ muestra que $x=u(b/d)$ es una solución de la congruencia original.
- Si $d<n$, divida el coeficiente, el objetivo y el módulo por $d$. El coeficiente reducido es invertible módulo $n/d$, dando una clase $x\equiv x_0\pmod{n/d}$. Sus elevaciones son $x_0+k(n/d)$ para $k=0,\ldots,d-1$: exactamente $d$ residuos distintos módulo $n$. El caso $d=n$ se maneja separadamente a continuación.
How many solutions modulo 20 does $8x \equiv 12 \pmod{20}$ have?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
The gcd is 4 and divides 12, so there are four residues modulo 20. Reducing gives 2x ≡ 3 (mod 5), hence x ≡ 4 (mod 5). The four lifts are 4, 9, 14 and 19 modulo 20.
Reducir, resolver y elevar
- Para $6x\equiv9\pmod{15}$, el mdc es $3$ y divide $9$. Divida los tres números por $3$ para obtener $2x\equiv3\pmod5$. Dado que $2^{-1}\equiv3\pmod5$, la solución reducida es $x\equiv4\pmod5$.
- Suba al módulo original sumando $5$: los residuos son $4,9,14$ módulo $15$. Sustituyéndolos da $24,54,84$, cada uno congruente con $9$ módulo $15$; el conteo de soluciones es $3$, no $1$.
Which congruence is equivalent to $6x\equiv9\pmod{15}$ after dividing by the gcd?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
The gcd is 3, so the coefficient 6, target 9 and modulus 15 all divide by 3. The reduced class modulo 5 lifts to three classes modulo 15.
Cancelación y coeficiente cero
- Dividir solo el coeficiente y el objetivo cambia el problema: reemplazar $6x\equiv9\pmod{15}$ por $2x\equiv3\pmod{15}$ daría solo $x\equiv9\pmod{15}$ y perdería las otras dos soluciones. El módulo debe reducirse durante el paso de división.
- Si $n\mid a$, entonces $ax\equiv0\pmod n$ para todo $x$. Hay todos los $n$ residuos soluciones cuando $n\mid b$, y ninguno de lo contrario. Así $0x\equiv0\pmod6$ tiene seis soluciones, mientras que $0x\equiv1\pmod6$ no tiene ninguna; no se necesita inverso módulo $1$.
¿Cuántas soluciones hay?
Utilice gcd(a, n) para contar las soluciones de ax ≡ b (mod n).
How many residue classes modulo $6$ satisfy $0x\equiv0\pmod6$?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
Every residue 0, 1, 2, 3, 4 and 5 works. The gcd is gcd(0, 6) = 6, which divides the target 0.
Solve $18x\equiv30\pmod{42}$ and list every residue solution modulo $42$. Explain why your list is complete.
El mcd es $\gcd(18,42)=6$, que divide a 30. Divida el coeficiente, el objetivo y el módulo por 6 para obtener $3x\equiv5\pmod7$. Dado que el inverso de 3 módulo 7 es 5, esto da $x\equiv25\equiv4\pmod7$. Los seis levantamientos módulo 42 son $4,11,18,25,32,39$. Cada levantamiento satisface la congruencia original. Hay exactamente seis levantamientos distintos porque el período reducido es 7 y el módulo original es 42.
Encontrar inversos mediante Euclides extendido
- El inverso de $a$ módulo $n$ existe exactamente cuando $\gcd(a,n)=1$. Para $7$ y $26$, Euclides da $26=3\cdot7+5$, luego $7=5+2$, luego $5=2\cdot2+1$; el último residuo no nulo es $1$.
- Dado que $2=7-5$, sustitución hacia atrás da $1=3\cdot5-2\cdot7$. Use siguiente $5=26-3\cdot7$ para obtener $1=3\cdot26-11\cdot7$. De ahí $7^{-1}\equiv-11\equiv15\pmod{26}$; verifique que $7\cdot15=105\equiv1\pmod{26}$.
Find the inverse of 5 modulo 13 (between 1 and 12).
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
We need 5x ≡ 1 (mod 13). 5 · 8 = 40 = 3 · 13 + 1, so the inverse is 8. (The Euclidean algorithm finds it systematically.)
Combinar ciclos coprimos
- El teorema chino del resto es el resultado de que las congruencias con módulos pairwise coprimos tienen exactamente una clase común residuo módulo el producto de sus módulos. Para dos módulos, sustituya $x=r+mk$ en $x\equiv s\pmod n$; el coeficiente $m$ es invertible módulo $n$.
- En el ejemplo de engranajes, escriba $x=2+4k$. La segunda condición se convierte en $4k\equiv1\pmod7$, así que $k\equiv2\pmod7$ y $x\equiv10\pmod{28}$. El tiempo positivo menor es $10$; todo el conjunto de soluciones es $10+28t$ para entero $t$.
Find the least positive $x$ with $x \equiv 1 \pmod 3$ y $x \equiv 4 \pmod 5$.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
List numbers ≡ 4 (mod 5): 4, 9, 14, … The first, 4, already leaves remainder 1 when divided by 3, so x = 4. By the CRT the solution is unique mod 15.
Módulos no coprimos: probar compatibilidad
- Para $x\equiv r\pmod m$ y $x\equiv s\pmod n$, una solución existe exactamente cuando $\gcd(m,n)$ divide $s-r$. Sustituyendo $x=r+mk$ da $mk\equiv s-r\pmod n$, así la prueba lineal mdc aplica. Un sistema compatible da una clase módulo $\operatorname{lcm}(m,n)$.
- Para $x\equiv1\pmod4$ y $x\equiv3\pmod6$, sustituya $x=1+4k$ para obtener $4k\equiv2\pmod6$. Reduzca a $2k\equiv1\pmod3$, dando $k\equiv2\pmod3$ y $x\equiv9\pmod{12}$. Pero los residuos $0$ módulo $4$ y $3$ módulo $6$ son incompatibles: uno requiere un número par, el otro impar.
Find the least positive integer $x$ with $x\equiv3\pmod8$ y $x\equiv7\pmod{12}$.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
The gcd is 4, which divides the difference 7 − 3. Put x = 3 + 8k. Then 8k ≡ 4 (mod 12), so 2k ≡ 1 (mod 3) and k ≡ 2 (mod 3). Thus x ≡ 19 (mod 24), with least positive member 19.
El período y la solución positiva menor
- Dos soluciones del mismo sistema difieren en un múltiplo de ambos módulos, y por tanto en su mcm. Inversamente, añadir el mcm a una solución preserva ambas condiciones. Esto demuestra el período afirmado y la unicidad de la clase de residuos.
- Un representante no negativo mínimo no necesariamente es positivo. Para $x\equiv0\pmod4$ y $x\equiv0\pmod6$, la clase es $0$ módulo $12$; su miembro positivo más pequeño es $12$, no $0$. Lee el rango solicitado antes de elegir el representante final.
Solve $x\equiv2\pmod6$, $x\equiv8\pmod{10}$. Give the full residue class and least positive solution. Then explain what changes if the first residue is changed to $1$.
El mcd es 2 y divide $8-2=6$, por lo que el primer sistema es compatible. Escriba $x=2+6k$; luego $6k\equiv6\pmod{10}$, de modo que $3k\equiv3\pmod5$ y $k\equiv1\pmod5$. En consecuencia $x\equiv8\pmod{30}$, donde $30=\operatorname{lcm}(6,10)$. Su menor solución positiva es 8. Si el primer residuo se convierte en 1, la diferencia requerida es $8-1=7$, que no es divisible por el mcd 2. Alternativamente, las dos congruencias exigen paridad impar y par, por lo que no existe solución.
Función totiente: cuenta los residuos invertibles
- El totiente es el número de clases de residuos coprimas con el módulo. Para $n\geq2$, escribe esta cuenta como $\varphi(n)$. Si los divisores primos distintos son $p$, entonces $\varphi(n)=n\prod_{p\mid n}(1-1/p)$: cada primo entra en el producto una sola vez, independientemente de su exponente en $n$.
- Dado que $36=2^2\cdot3^2$, obtenemos $\varphi(36)=36\cdot\dfrac12\cdot\dfrac23=12$. Para una potencia de primo, $\varphi(p^k)=p^k-p^{k-1}$, porque exactamente los múltiplos de $p$ no son coprimos con $p^k$.
$\varphi(36)$ equals
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
$36 \cdot \tfrac12 \cdot \tfrac23$.
Euler y Fermat requieren las condiciones adecuadas
- Si $\gcd(a,n)=1$, el teorema de Euler da $a^{\varphi(n)}\equiv1\pmod n$. La multiplicación por $a$ permuta los residuos invertibles; comparar sus productos y cancelar el producto invertible demuestra el resultado.
- Para un primo $p$ y $p\nmid a$, esto se convierte en el teorema de Fermat $a^{p-1}\equiv1\pmod p$. La forma $a^p\equiv a\pmod p$ se cumple para todo entero $a$, incluidos los múltiplos de $p$. Por ejemplo, $\varphi(10)=4$ y $3^{100}=(3^4)^{25}\equiv1\pmod{10}$.
What is $7^{222} \bmod 10$?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
φ(10) = 4, 222 ≡ 2 mod 4, 7² = 49.
For integers $a$ y $n\geq2$, $a^{\varphi(n)}\equiv1\pmod n$ holds whenever $\gcd(a,n)=1$.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
True. Euler’s theorem requires coprimality. For example, 2 and 8 are not coprime, and $2^4\equiv0\pmod8$ rather than 1.
Reducir exponentes solo para unidades
- Para un exponente no negativo $e$ y $\gcd(a,n)=1$, reducir $e$ módulo $\varphi(n)$ preserva $a^e$ módulo $n$. Sin coprimaridad esto puede fallar: reducir $10$ módulo $\varphi(8)=4$ sustituiría erróneamente $2^{10}$ por $2^2\equiv4\pmod8$.
- El método de elevación al cuadrado sucesivo funciona sin asumir coprimaridad. Aquí $2^2\equiv4$, $2^4\equiv0$ y $2^8\equiv0\pmod8$. Dado que $10=8+2$, el residuo real es $2^{10}\equiv0\pmod8$. Reduce los productos intermedios en lugar de invocar el teorema de Euler para un no unidad.
Since $\varphi(8)=4$, reducing the exponent proves $2^{10}\equiv2^2\pmod8$.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Euler exponent reduction requires an invertible base. The actual residues are 2¹⁰ ≡ 0 (mod 8) and 2² ≡ 4 (mod 8), so they differ.
Compute $5^{123}\bmod12$ y $6^{18}\bmod9$. Explain why the same exponent-reduction shortcut does not apply to both.
Para la primera potencia, $\gcd(5,12)=1$ y $\varphi(12)=4$. Dado que $123\equiv3\pmod4$, Euler proporciona $5^{123}\equiv5^3\equiv5\pmod{12}$. Para la segunda, $\gcd(6,9)=3$, por lo que la reducción de Euler no está justificada. En su lugar $6^2=36\equiv0\pmod9$, en consecuencia $6^{18}=(6^2)^9\equiv0\pmod9$. Reducir 18 módulo $\varphi(9)=6$ reemplazaría erróneamente la potencia por $6^0=1$.
La divisibilidad se convierte en desigualdades de exponentes primos
- Para un entero positivo $M$, sea $v_p(M)$ el exponente del primo $p$ en su factorización. Un entero positivo $D$ divide exactamente a $M$ cuando $v_p(D)\leq v_p(M)$ para todo primo $p$.
- Si $N^k$ debe ser divisible por $D$, con entero positivo $k$, requiere $k\,v_p(N)\geq v_p(D)$. Elige $v_p(N)=\lceil v_p(D)/k\rceil$ para los primos que dividen $D$, y cero para otros primos. Cada $N$ admisible es múltiplo de esta elección, por lo que es el menor positivo.
El menor entero cuyo cuadrado contiene 360
- Factoriza $360=2^3\cdot3^2\cdot5$. Para que $N^2$ sea divisible por $360$, los exponentes de $2,3,5$ en $N$ deben ser al menos $2,1,1$. Así, la elección mínima es $N=2^2\cdot3\cdot5=60$.
- Verifica $60^2=3600=10\cdot360$. El exponente de $2$ en $N$ se redondea desde $3/2$ hacia arriba hasta $2$; no debe redondearse hacia abajo. Primos adicionales o exponentes mayores aumentan $N$ y no pueden mejorar el mínimo.
What is the least positive integer $N$ such that $108$ divides $N^2$?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
Since 108 = 2²·3³, N needs at least one factor of 2 and two factors of 3. The least N is 2·3² = 18, and 18² = 324 = 3·108.
Rellenar un producto para hacer una potencia perfecta
- Para convertir $24N$ en un cubo perfecto, comienza con $24=2^3\cdot3$. Todo exponente primo en el producto debe ser múltiplo de $3$. El exponente de $2$ ya es adecuado, pero el exponente de $3$ necesita dos copias más, así que el menor multiplicador es $N=3^2=9$.
- Verifique $24\cdot9=216=6^3$. Esto utiliza congruencias de exponentes: $v_p(24)+v_p(N)\equiv0\pmod3$. El problema anterior de divisibilidad cuadrada usó desigualdades en su lugar. Elija la condición que coincida con el enunciado del problema.
¿Funciona el paso propuesto?
Verificar los supuestos detrás de la reducción de exponentes, períodos del TCR y mínimos exponentes.
What is the least positive integer $N$ such that $18N$ is a perfect cube?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Factor 18 = 2·3². To make all product exponents multiples of 3, add two factors of 2 and one factor of 3. Thus N = 2²·3 = 12 and 18·12 = 216 = 6³.
Find the least positive integer $N$ such that $540$ divides $N^2$ y $40N$ is a perfect cube. Prove minimality using prime exponents.
Escriba $540=2^2\cdot3^3\cdot5$ y $40=2^3\cdot5$. Sea a, b y c los exponentes de 2, 3 y 5 en N. La divisibilidad de N² requiere $a\geq1$, $b\geq2$ y $c\geq1$. La condición de cubo exige que $a+3$, b y $c+1$ sean múltiplos de 3. Por tanto, los exponentes mínimos son $a=3$, $b=3$ y $c=2$, dando como resultado $N=2^3\cdot3^3\cdot5^2=5400$. No se necesita ningún primo adicional. Todo N admisible tiene al menos estos exponentes, por lo que ninguno puede ser menor. Verifique que $5400^2/540=54000$ sea un entero y $40\cdot5400=216000=60^3$.
Verifique existencia, periodo y minimalidad
- Para una congruencia lineal, verifique el mcd, reduzca los tres números y eleve cada residuo. Para un sistema, verifique la compatibilidad y use el mcm como su periodo; una respuesta positiva mínima puede diferir del representante no negativo mínimo.
- Use Euler solo para residuos invertibles. Para problemas de divisibilidad de enteros mínimos, factorice primero y traduzca cada requisito en una desigualdad o congruencia para cada exponente primo.