Cómo resolver esta ecuación cuadrática de congruencia

Question

¿Cómo resolver $x^2+x+1\equiv 0\pmod {11}$?

Sé que en algunas ecuaciones como $ax\equiv b\pmod d$ si $(a,d)=1$ entonces la ecuación tiene una y solo una solución $x\equiv ba^{\phi(d)-1}\pmod d$. Cualquier ayuda será apreciada. ;)

Answer 1

¡Usas la fórmula cuadrática!

No, en serio. Pero necesitas interpretar correctamente los términos: en lugar de "dividir" por $2a$ (aquí, $2$) necesitas multiplicar por un número $r$ tal que $2r\equiv 1\pmod{11}$ (es decir, $r=6). Y en lugar de intentar encontrar una raíz cuadrada, aquí, $\sqrt{b^2-4ac} = \sqrt{1-4} = \sqrt{-3}$, quieres encontrar enteros $y$ tales que $y^2\equiv -3\pmod{11}$. Puede ser imposible hacerlo, pero si puedes encontrarlos, entonces al sustituirlos en la fórmula cuadrática te dará una solución; y si no puedes encontrarlos, entonces no hay soluciones.

Ahora bien, resulta que $-3$ no es un cuadrado módulo $11$; por lo tanto no hay soluciones a $x^2+x+1\equiv 0\pmod{11}$. (Puedes averiguar si $-3$ es un cuadrado usando reciprocidad cuadrática: sabemos que $-1$ no es un cuadrado módulo $11$, ya que $11\equiv 3\pmod{4}$. Y como tanto $3$ como $11$ son congruentes a $3$ módulo $4$, tenemos $$\left(\frac{-3}{11}\right) = \left(\frac{-1}{11}\right)\left(\frac{3}{11}\right) = -\left(-\left(\frac{11}{3}\right)\right) = \left(\frac{11}{3}\right) = \left(\frac{2}{3}\right) = -1,$$ así que $-3$ no es un cuadrado módulo $11$).

(También puedes verificar que esto es cierto sustituyendo $x=1,2,\ldots,10$ y viendo que ninguno satisface la ecuación).

Por otro lado, si tu polinomio fuese, digamos, $x^2+x-1$, entonces la fórmula cuadrática diría que las raíces son $$\frac{-1+\sqrt{1+4}}{2}\qquad\text{y}\qquad \frac{-1-\sqrt{1+4}}{2}.$$ Ahora, $5$ sí es un cuadrado módulo $11$: $4^2 = 16\equiv 5\pmod{11}$. Entonces podemos tomar $4$ como una de las raíces cuadradas, y tomando "multiplicación por $6$" como equivalente a "dividir por $2$" (ya que $2\times 6\equiv 1\pmod{11}$), obtendríamos que las dos raíces son $$\begin{align*} \frac{-1+\sqrt{5}}{2} &= \left(-1+4\right)(6) = 18\equiv 7\pmod{11}\\ \frac{-1-\sqrt{5}}{2} &= \left(-1-4\right)(6) = -30\equiv 3\pmod{11} \end{align*}$$ y de hecho, $(7)^2 + 7 - 1 = 55\equiv 0\pmod{11}$ y $3^2+3-1 = 11\equiv 0\pmod{11}.

---

Definitivamente podemos usar este método cuando $2a$ es relativamente primo al módulo; si el módulo no es un primo, sin embargo, ni una potencia prima impar, entonces puede haber más de $2$ raíces cuadradas para un número dado (o ninguna). Pero para módulos primos impares, funciona como un encanto.

Answer 2

Puedes utilizar la técnica de Completar el Cuadrado.

Supongamos que queremos resolver la congruencia $ax^2+bx+c\equiv 0 \pmod p$, donde $a\not\equiv 0\pmod{p}$, y $p$ es un primo impar. La congruencia es equivalente a $$4a^2x^2+4abx+4ac\equiv 0\pmod{p}.\tag{$1$}$$ Completando el cuadrado, vemos que la congruencia es equivalente a $$(2ax+b)^2-b^2+4ac\equiv 0\pmod{p},$$ o equivalentemente a $$(2ax+b)^2\equiv b^2-4ac\pmod{p}.\tag{$2$}$$

Para resolver esta última congruencia tenemos que (i) intentar resolver la congruencia $y^2 \equiv b^2-4ac\pmod{p}$. Puede que no haya solución, en cuyo caso la congruencia original no tiene solución. Puede que haya una sola solución, si $b^2-4ac\equiv 0\pmod{p}$. En todos los demás casos, habrá dos soluciones. (ii) Después de haber encontrado dicho $y$, resolvemos las congruencias lineales $2ax+b\equiv y\pmod{p}$.

Ahora pasamos a $x^2+x+1\equiv 0\pmod{p}$, y utilizamos la técnica básica, aunque la inspección sería más rápida.

Escribimos como $4x^2+4x+4\equiv 0\pmod{11}$, luego como $(2x+1)^2-1+4\equiv 0\pmod{11}$, y luego como $(2x+1)^2\equiv -3\equiv 8\pmod{11}$.

Por lo tanto, primero intentamos resolver la congruencia $y^2\equiv -3\equiv 8\pmod{11}$. Resulta que no hay soluciones. Hay métodos poderosos para tratar estas preguntas para primos grandes $p$. Para el $11$, solo calcula $1^2$, $2^2$, $3^3=2$, $4^2$ y $5^2$ módulo $11$. Ninguno funciona. El resto no puede funcionar, ya que son esencialmente los negativos de los números que ya hemos comprobado, por lo que sus cuadrados son, módulo $11, los mismos que los cuadrados de los números del $1$ al $5$. Por ejemplo, $6\equiv -5\pmod{11}$, por lo que $6^2\equiv (-5)^2\equiv 5^2\pmod{11}$, y de manera similar $7^2\equiv 4^2$, y así sucesivamente.

Observaciones: $1.$ La congruencia $(2)$ tiene una solución si y solo si la congruencia $y^2\equiv b^2-4ac\pmod{p}$ tiene una solución, es decir, si y solo si $b^2-4ac$ es un cuadrado módulo $p$. Este $b^2-4ac$ es el discriminante familiar del álgebra elemental.

$2.$ La idea general se puede utilizar incluso cuando estamos resolviendo una congruencia cuadrática módulo $m$, donde $m$ no es primo. Pero se necesitan modificaciones significativas. La congruencia $ax^2+bx+c\equiv 0\pmod{m}$ es equivalente a $4a^2x^2+4abx+4ac\equiv 0 \pmod{4am}$, por lo que terminamos examinando $$(2ax+b)^2\equiv b^2-4ac\pmod{4am}.$$ El estudio de la congruencia $y^2\equiv b^2-4ac\pmod{4am}$ es más complicado que cuando el módulo es $p$, y puede haber muchas soluciones. Pero después estamos resolviendo las congruencias lineales $2ax+b\equiv y\pmod{4am}$, y podemos usar el Algoritmo de Euclides Extendido.

Answer 3

Aquí hay una solución alternativa. Supongamos que $x$ es una solución.

Sea $a$ una raíz primitiva módulo 11, así que $x=a^k$ para algún $1 \leq k \leq 10$.

$$x^2+x+1\equiv 0\pmod {11} \Rightarrow x^3 \equiv 1 \mod 11 \Rightarrow a^{3k} \equiv 1 \mod 11 \Rightarrow 10 | 3k $$ $$\Rightarrow 10|k \Rightarrow k =10 \Rightarrow x \equiv a^{10} \equiv 1 \mod 11 \,.$$

Es fácil ver que $x \equiv 1 \mod 11$ no es una solución, y demostramos que es la única solución potencial.

Por lo tanto, la ecuación no tiene solución.

Answer 4

Pista $\rm\ mod\ p\ne 3\!:\ x^2\!+x+1 = 0 \iff x\ne 1,\ x^3 = 1\iff x\ne 1,\,\ x^{\,(3,\,p-1)}\! = 1 $

Por lo tanto, no tiene raíces cuando $\rm\:(3,p\!-\!1) = 1,\:$ por ejemplo, cualquier primo $\rm\:p = 6\,k\!-\!1,\:$ por ejemplo, $\rm\:p = 11.$