Encontrar todas las soluciones de $7x^2 \equiv 1 \pmod {17}$

Question

Encontrar todas las soluciones de $7x^2 \equiv 1 \pmod {17}$

---

Descubrí toda la raíz primitiva de $U_{17}$ ser : $\{3,5,6,7,10,12,14\}$ .

Para continuar con el cálculo, creo que necesito usar el teorema que es $x^2 \equiv1\pmod{n}$ . Pero no sé cómo relacionarlo con la pregunta.

¡¡Gracias!!

Answer 1

Tenga en cuenta que $5 \cdot 7 \equiv 1 \pmod {17} $ así que estás resolviendo $x^2 \equiv 5 \pmod {17} $ .

Ahora $5$ no es un residuo cuadrático módulo $17$ como $5^{(17-1)/2} = 5^8 \equiv - 1 \pmod {17} $ .

Answer 2

Probablemente primero me desharía del $7$ multiplicando por la inversa de $7$ modulo $17$ . Tenga en cuenta que $(5)(7)=35\equiv 1\pmod{17}$ . Así que nuestra congruencia se puede reescribir como $x^2\equiv 5\pmod{17}$ .

Habrá $0$ o $2$ soluciones. Usted puede buscar, es corto, ya que realmente sólo hay que tratar de $x=1$ à $8$ . Si nada de esto funciona, nada puede funcionar. Y si entre ellas encuentras una $a$ tal que $a^2\equiv 5\pmod{17}$ entonces $-a$ también conocido como $17-a$ será la otra solución.

O puedes utilizar una maquinaria como la Reciprocidad Cuadrática, si ya se ha hecho, y ahorrarte el (pequeño) trabajo de buscar una solución cuando en realidad no la hay.

Si ya dispone de una lista de raíces primitivas, puede observar que $5$ es uno de ellos, por lo que no es un residuo cuadrático. Si se tiene una sola raíz primitiva, se pueden calcular sus potencias pares, y encontrar que $5$ no se produce.

Answer 3

Sugerencia $\rm\ mod\ 17\!:\ 1/7 \equiv 5\:$ no es un cuadrado por Criterio de Euler, desde

$$\rm 5^8 \equiv (25)^4 \equiv (2^3)^4\equiv (2^4)^3 \equiv (-1)^3 \equiv -1 $$

Answer 4

$$7x^2 \equiv 1 \pmod{17} \implies x^2 \equiv 7^{-1} \pmod{17} \implies x^2 \equiv 5 \pmod{17}$$ En $(x,17) = 1$ de little-Fermat, tenemos $$x^{16} \equiv 1 \pmod{17}$$ Pero también necesitamos $x^2 \equiv 5 \pmod{17}$ . Es decir $$x^{16} = {x^2}^8 \equiv 5^8 \pmod{17} \equiv (25)^4 \pmod{17} \equiv 8^4 \pmod{17} \equiv (64)^2 \pmod{17}$$ $$(64)^2 \pmod{17} \equiv 13^2 \pmod{17} \equiv 169 \pmod{17} \equiv -1 \pmod{17}$$ contradiciendo al pequeño Fermat.