What are the last two digits of $77^{17}$?

Question

I'm trying to solve current task referenced the following but I stuck at $\displaystyle77^{17}\equiv x\pmod{100}$. As it is described on above link it uses Binomial Theorem. But I read a lot about the theorem, find it hard to figure out. Could you please explain to me step by step how to solve it by the binomial theorem.

Answer 1

The idea is to realize that $77=7\times 10+7$. Why is this important in the present question? It is indeed a question about the binomial theorem, it says that :

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

Now applying this with $a:=7\times 10$, $b:=7$ and $n=17$ we have that :

$$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 $$

Now if $k\geq 2$ then $\begin{pmatrix}17\\k\end{pmatrix}10^k$ is divisible by $100$ hence, mod $100$ you have :

$$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 $$

Now $7^{18}=(-3)^{18}=(-1)^9=-1=9$ mod $10$ Hence :

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

Finally $7^2=50-1$ hence mod $100$ we have $(7^2)^8=(50-1)^8=1$ (here I used again the binomial theorem). This means that $7^{17}=7$ whence :

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

Edit: you asked how to do it with the binomial theorem so this is an answer with this binomial theorem. However the answer from azimut using dichotomic expansion is (in the present situation) more efficient...

Answer 2

I suggest computing the value by iterated squaring. $$ 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 $$ Now $$ 77^{17} = 77^{16} \cdot 77 \equiv 61 \cdot 77 \equiv (-39)\cdot (-23) = 897 \equiv 97 \mod 100 $$

Answer 3

Using Binomial:

$$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$$

---

Using Carmichael:

Another approach is using the Carmichael theorem, this gives $77^{20} \equiv 1 \mod 100$. Now we want to multiply trice by the multiplicative inverse of $77$ mod 100, which is 13, so $$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}$

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

Apply CRT on $(1),(2)$

Or by observation, $77^{17}\equiv97\pmod{4\cdot25}$

Answer 5

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

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

Now $(-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}$

Answer 6

As $77=7\cdot11,77^{17}=7^{17}\cdot11^{17}$

Now $11^{17}=(1+10)^{17}\equiv1^{17}+\binom{17}11^{16}10^1\pmod{100}\equiv1+17\cdot10\equiv71$

and $7^2=50-1\implies7^4=(50-1)^2\equiv1\pmod{100}$

$\implies7^{17}=7(7^4)^4\equiv7\cdot1^4\pmod{100}\equiv7$

$\implies77^{17}\equiv71\cdot7\equiv497$