Encontrar $7^{100} \pmod{167}$ el uso de Fermat Poco Teorema de

Question

Entiendo cómo el uso de Fermat Poco teorema, pero sólo en los exponentes que son más grandes que el mod, por lo tanto, no sé cómo hacer esta pregunta por favor ayuda, gracias!

Answer 1

Teorema de Fermat nos dice que $a^{p - 1} \equiv 1 \pmod p$, siempre $p$ es una extraña prime (o una de Fermat pseudoprime a $a$) y $\gcd(a, p) = 1$. Pero usted ya lo sabía.

El bit crucial a su pregunta que casi nunca se menciona es que el $$a^{\frac{p - 1}{2}} = \pm 1 \pmod p.$$ de Un poco de reflexión sobre las propiedades básicas de la exponenciación se muestran por qué debe ser uno de esos dos valores.

Pero, ¿cuál? Me gustaría tener una inteligente respuesta a esta parte. Todavía le ayuda a limitar a dos posibles respuestas.

Si $7^{83} \equiv -1 \pmod{167}$,$7^{100} = -(7^{17} \pmod{167})$. Si en lugar de $7^{83} \equiv 1 \pmod{167}$,$7^{100} \equiv 7^{17} \pmod{167}$.

Computación $7^{17} \pmod{167}$ es más manejable: 7, 49, 9, 63, 107, 81, 66, 128, 61, 93, 150, 48, 2, 14, 98, 18, 126. Así que quizá $7^{100} \equiv 126 \pmod{167}$.

La otra posible solución es $-126 \equiv 41 \pmod{167}$.

Answer 2

No estoy seguro de cómo se puede utilizar de Fermat poco teorema. El método estándar para el cómputo de los poderes es escribir $100$ en base $2$: $100=\mathtt{1100100}_2$. Siguiente (todas las congruencias módulo $167$) \begin{align} 7^2&\equiv 49 \\ 7^4&\equiv 49^2\equiv 63 \\ 7^8&\equiv 63^2\equiv 128 \\ 7^{16}&\equiv 128^2\equiv 18 \\ 7^{32}&\equiv 18^2\equiv 157 \\ 7^{64}&\equiv 157^2\equiv 100 \end{align} y así $$ 7^{100}\equiv 7^{64}\cdot 7^{32}\cdot 7^4 \equiv 100\cdot 157\cdot 63\equiv 126 $$

Uno podría tomar nota de que $7^{100}\cdot 7^{66}\equiv 1$, y \begin{align} 167&=7\cdot23+6\\ 7&=6\cdot 1+1 \end{align} por lo $1=7-(167-7\cdot 23)=7\cdot24-167$. Así $$ 7^{100}=24^{66} $$ Pero uno todavía tiene que calcular $24^{64}$.

Answer 3

Desde $\phi(167) = 166 = 2\cdot 83$, los órdenes posibles de $7$ mod $167$ $2$, $83$ y $166$. Claramente, el orden no es $2$. Si calculamos el símbolo de Legendre

$$\left(\frac{7}{167}\right) = - \left(\frac{167}{7}\right) = -\left(\frac{-1}{7}\right) = 1,$$

vemos que $7$ es una ecuación cuadrática de residuos de mod $167$, y por lo que el orden no puede ser $166.$ (Una raíz primitiva no puede ser una ecuación cuadrática de residuos.) Por lo tanto, el orden de $7$ mod $167$$83.$, por Lo que tenemos

$$7^{100} \equiv 7^{17} \pmod{167}.$$

Siguiente, observe que $7^3 = 343$ está muy cerca de la $2\cdot 167 = 334$, de modo que ha $7^3 \equiv 9 \pmod{167}.$, $2\cdot 9^2 = 162 \equiv -5 \pmod{167}$. A continuación, calculamos:

$$7^{17} \equiv (7^3)^5\cdot 49 \equiv 9^2\cdot 9^2 \cdot 9 \cdot 49 \equiv (80\cdot 9^2 +1\cdot 9^2)\cdot 9 \cdot 49 \equiv (40(-5)+81)\cdot 9 \cdot 49 $$

$$\equiv (-119)\cdot 9 \cdot 49 \equiv -119\cdot 441 \equiv 48 \cdot (-60) \equiv -2880 \equiv 126 \pmod{167}.$$