Intentando utilizar el lema de Eulers para encontrar residuos cuadráticos

Question

Creo que debo estar haciendo algo mal (o eso o no estoy llevando bien el cálculo). Estoy intentando acostumbrarme a utilizar el criterio de Euler , es decir, que $a$ es un residuo cuadrático de $p$ si y sólo si $a^{p-1/2}\equiv1\mod p$ . Sigo recibiendo no $\pm1$ números, así que sé que estoy cometiendo un error.

Digamos que queremos ver si $31$ es un residuo cuadrático de $71$ Aquí es cómo he estado tratando de hacerlo (sé que debería añadir en $\bmod71$ en lo que sigue, pero se da por sentado que cada cálculo es $\bmod71$ )

$31^{(71-1)/2}\equiv31^{35}\equiv (31^2)^{16}31^3\equiv (38)^{16}31^3\equiv(38)^831^3\equiv(24)^831^3\equiv (24^2)^431^3\equiv (58)^431^3\equiv(58^2)^231^3\equiv6^231^3\equiv36.31^3\equiv30\equiv69.31\equiv9\mod71$

¿Puede alguien decirme qué estoy haciendo mal?

Answer 1

$24^{2}\equiv 8\pmod {71}$ Así que $(24^2)^{4}31^3\equiv 8^4\cdot31^3\pmod {71}$ en lugar de $(24^2)^431^3\equiv (58)^431^3\pmod {71}$ .

Answer 2

Calculándolo por el camino largo... $$31^{35}\equiv(31^5)^7\equiv 34^7\equiv -1\pmod{71}$$ Vale sí, he utilizado más pasos intermedios que eso. Pero, usted utiliza el mismo truco de estilo más adelante en su secuencia. $38^2\equiv 24 \bmod 71$ para los pasos de reducción de 2,8, $24^2\equiv 8\bmod 71$ para la reducción de 2,4 , $8^2\equiv 64\bmod 71$ en la reducción de 2,2, $64^2\equiv 49\bmod 71$ así que $49(42)\equiv -1\bmod 71$ Tuve que corregirme, varias veces, para escribirlo.