¿Cuáles son los dos últimos dígitos de $77^{17}$?

Question

Estoy tratando de resolver la tarea actual hace referencia a la siguiente pero me quedé en $\displaystyle77^{17}\equiv x\pmod{100}$. Como se describe en el enlace de arriba se utiliza el Teorema del Binomio. Pero he leído mucho sobre el teorema, resulta difícil de averiguar. Podría usted por favor, que me explique paso por paso cómo se resuelve el teorema del binomio.

Answer 1

La idea es darse cuenta de que $77=7\times 10+7$. ¿Por qué es esto importante en la presente pregunta? De hecho, es una pregunta sobre el teorema del binomio, se dice que :

$$(a+b)^n=\sum_{k=0}^n\begin{pmatrix}n\\k\end{pmatrix}a^kb^{n-k} $$

Ahora la aplicación de este con $a:=7\times 10$, $b:=7$ y $n=17$ tenemos que :

$$77^{17}=\sum_{k=0}^{17}\begin{pmatrix}17\\k\end{pmatrix}7^k10^k7^{17-k} $$

$$77^{17}=7^{17}\sum_{k=0}^{17}\begin{pmatrix}17\\k\end{pmatrix}10^k $$

Ahora si $k\geq 2$ $\begin{pmatrix}17\\k\end{pmatrix}10^k$ es divisible por $100$ por lo tanto, mod $100$ usted tiene :

$$77^{17}=7^{17}\sum_{k=0}^{1}\begin{pmatrix}17\\k\end{pmatrix}10^k\text{ mod } 100 $$

$$77^{17}=7^{17}(1+17\times 10)\text{ mod } 100 $$

$$77^{17}=7^{17}+7^{18}.10\text{ mod } 100 $$

Ahora $7^{18}=(-3)^{18}=(-1)^9=-1=9$ mod $10$ por lo tanto :

$$77^{17}=7^{17}+90\text{ mod } 100 $$

Finalmente, $7^2=50-1$ por lo tanto mod $100$ tenemos $(7^2)^8=(50-1)^8=1$ (aquí he utilizado de nuevo el teorema del binomio). Esto significa que $7^{17}=7$ dónde :

$$77^{17}=97\text{ mod } 100 $$

Edit: se preguntó cómo hacerlo con el teorema del binomio, así que esto es una respuesta con este teorema binomial. Sin embargo la respuesta de azimut utilizando dicotómica de expansión es (en la situación actual) más eficiente...

Answer 2

Sugiero calcular el valor por iterada de cuadratura. $$ 77^2 \equiv (-23)^2 = 529 \equiv 29 \mod 100 \\ 77^4 = (77^2)^2 \equiv 29^2 = 841 \equiv 41 \mod 100 \\ 77^8 = (77^4)^2 \equiv 41^2 = 1681 \equiv 81 \mod 100 \\ 77^{16} = (77^8)^2 \equiv 81^2 \equiv (-19)^2 = 361 \equiv 61 \mod 100 $$ Ahora $$ 77^{17} = 77^{16} \cdot 77 \equiv 61 \cdot 77 \equiv (-39)\cdot (-23) = 897 \equiv 97 \mod 100 $$

Answer 3

El Uso De Un Binomio:

$$77^{17} = (80-3)^{17} = \sum_{k=0}^n{17 \choose k}80^{17-k}(-3)^k \equiv (-3)^{17}+17\cdot80\cdot(-3)^{16} \\ \equiv (17\cdot80-3)\cdot 3^{16} \equiv 57 \cdot 3^{16}\equiv 57 \cdot 81^{4} \equiv 57 \cdot 19^{4} \equiv 57 \cdot 61^{2} \equiv 97 \mod 100$$

---

El Uso De Carmichael:

Otro método es usar el teorema de Carmichael, esto da $77^{20} \equiv 1 \mod 100$. Ahora queremos multiplicar instante por el inverso multiplicativo de a $77$ mod 100, que es de 13, por lo $$77^{17} = 77^{20}(77^{-3}) \equiv 13^3 = 2197 \equiv 97 \mod 100$$

Answer 4

$100=4\cdot25$

$77\equiv1\pmod4\implies77^n\equiv1^n\equiv1\ \ \ \ (1)$

$77\equiv2\pmod{25}\implies77^{17}\equiv2^{17}$

Ahora $2^{20}\equiv1\pmod{25}\implies2^{17}\equiv2^{-3}\equiv-3\equiv22 \ \ \ \ (2)$

Aplicar CRT en $(1),(2)$

O por observación, $77^{17}\equiv97\pmod{4\cdot25}$

Answer 5

Como $77^2\equiv29\pmod{100}\equiv30-1$

$77^{17}=77(77^2)^8\equiv77(-1+30)^8\pmod{100}$

Ahora $(-1+30)^8\equiv(-1)^8+\binom81(-1)^730^1\pmod{100}\equiv-239\equiv61$

$61\cdot77=(60+1)(70+7)\equiv420+70+7\equiv97\pmod{100}$