Calcular $11^{35} \pmod{71}$

Question

Calcular $11^{35} \pmod{71}$

Lo he hecho:
$= (11^5)^7 \pmod{71}$
$=23^7 \pmod{71}$

Y no estoy muy seguro de qué hacer a partir de este punto..

Answer 1

Utilizando El pequeño teorema de Fermat :

$11^{70}=(11^{35})^2\equiv 1 \mod(71)$ ,

por lo que sólo necesitamos encontrar elementos en $\mathbb{Z}_{71}$ que es cuadrado a 1. Como 71 es un primo, $\mathbb{Z}_{71}$ es un campo, por lo que los únicos elementos que cuadran a 1 son 1 y -1. Podemos descartar la posibilidad de $11^{35}\equiv 1 \mod(71)$ utilizando reciprocidad cuadrática .

Answer 2

A partir del pequeño teorema de Fermat (y del hecho de que los polinomios cuadráticos tienen como máximo dos raíces mod un primo), se puede concluir que $11^{35} \equiv \pm 1\mod 71$ . El criterio de Euler puede reducir esto a la respuesta correcta de -1, pero si todavía no has estudiado la reciprocidad cuadrática la técnica muy útil de cuadratura repetida ofrece una aproximación más discreta al cálculo de este exponente.

En el módulo 71 tenemos

$$\begin{align*} 11^1 &\equiv 11\\ 11^2 &\equiv 50\\ 11^4 &\equiv (50)^2 \equiv 15\\ 11^8 &\equiv (15)^2 \equiv 12\\ 11^{16} &\equiv (12)^2 \equiv 2\\ 11^{32} &\equiv 4. \end{align*}$$

Son tantas potencias de $11$ como necesitamos: $$11^{35} \equiv 11^{32}11^2 11^1 \equiv 4\cdot 50 \cdot 11 \equiv 70 \mod 71$$

Answer 3

Si sabes que $11^{4} \equiv 15 \bmod 71$ (tomada del usuario7530 más arriba), entonces:

$$ 11^{35} \equiv (-60)^{35} \equiv -(4 \cdot 15)^{35} \equiv -(2^2 \cdot 11^4)^{35} \equiv -(2 \cdot 11^2)^{70} \equiv -1 \bmod 71 $$