Solucionar $2^k \equiv 5 \pmod{577}$

Question

Muestran que no hay un $k$ tal que $2^k \equiv 5 \pmod{577}$.

Mi solución: (todo lo que es el modulo $577$)

$577$ es una de las principales con el $\phi(577)=576=2^6 \cdot 3^2$. Primero muestra que el orden de $2$$144$: Tenga en cuenta que $2^{576/2^2}\equiv 1$ pero $2^{576/2^3}\not\equiv1$$2^{576/3}\not\equiv1$, de ello se deduce que el orden de $2$$576/2^2=144$.

Llegamos a la conclusión de que si $2^{k}\not\equiv 5$ $1<k<144$ a continuación, $2^{k}\not\equiv 5$ cualquier $k$. Ahora tenemos que calcular $2^{k} \pmod {577}$$9<k<144$; límite inferior $9$ desde $2^9=512<577$.

El problema con esto es la línea: ahora tenemos que calcular $2^{k} \pmod {577}$$9<k<144$.

Hay un método mejor que evita tratando de tantas posibilidades?

Editar: Siguiendo el comentario a la aceptación de la solución: Si la orden de $2$ no es divisible por orden de $5$, no hay solución. Esto puede no ser obvio, pero es cierto. Multiplicativa orden de $5$ $576$ desde $5^{576/2}\not\equiv 1$$5^{576/3}\not\equiv 1$. Desde $576$ no divide $144$, no hay solución.

Answer 1

Si usted tiene la Reciprocidad Cuadrática a su disposición, usted puede calcular

$$\left(5\over577\right)=\left(577\over5\right)=\left(2\over5\right)=-1$$

También, $577\equiv1$ mod $8$ implica

$$\left(2\over577\right)=1$$

lo que implica

$$\left(2^k\over577\right)=\left(2\over577\right)^k=1$$

por lo $5$ no puede ser congruente a $2^k$ mod $577$ cualquier $k$.

Añadido posterior: Si la Reciprocidad Cuadrática no está disponible (y, de hecho, el OP indica que incluso el símbolo de Legendre es en el siguiente capítulo del libro que estamos trabajando), no veo ninguna alternativa para hacer una buena cantidad de cálculo. Sin embargo, una feliz coincidencia hace que sea posible mantener los cálculos aquí manejable. Así que aquí es una prueba de que $5$ no puede ser de la forma $2^k$ mod $577$ con casi todos los sangrientos computacional detalles:

En primer lugar, vamos a calcular algunos poderes de $2$ mod $577$.

$$\begin{align} 2^2&=4\\ 2^4&=4^2=16\\ 2^8&=16^2=256\\ 2^{16}&=256^2=65536\equiv335\\ 2^{32}&\equiv335^2=112225\equiv287\\ 2^{64}&\equiv287^2=82369\equiv435\\ \end{align}$$

En este punto podemos calcular

$$2^{72}=2^{64}\cdot2^8\equiv435\cdot256=111360\equiv-1$$

Por otro lado,

$$\begin{align} 5^2&=25\\ 5^4&=25^2=625\equiv48=2^4\cdot3\\ \end{align}$$

Ese es nuestro feliz coincidencia, porque

$$5\equiv2^k\implies3\equiv2^{4(k-1)}\implies3^{18}\equiv2^{72(k-1)}\equiv(-1)^{k-1}$$

y ahora podemos calcular

$$\begin{align} 3^2&=9\\ 3^4&=9^2=81\\ 3^8&=81^2=6561\equiv214\\ 3^{16}&\equiv214^2=45796\equiv213\\ \end{align}$$

por lo tanto

$$3^{18}=3^{16}\cdot3^2\equiv213\cdot9=1917\equiv186\not\equiv\pm1$$

Puede haber alguna otra feliz coincidencia que permite incluso el terser prueba, pero tengo la sospecha de que había que tomar un montón de trabajo (o la suerte) para encontrar uno. El mensaje, yo diría, es que la Reciprocidad Cuadrática es una muy potente teorema.