Last two digits of $17^{17^{17}}$

Question

For a problem set, we had two find the final two digits of 17^17^17

So what I did was find the last digit of 17^17 and then take 17^of that last digit of 17 and then find the last two digits of that number. I got the last two digits as 17.

Is my method correct, if not, what is the method and what is your answer? Thanks

Answer 1

You get to use arithmetic modulo $100$ when all you care about is the last two digits. Also, since $\varphi(100)=40$ and $17$ is relatively prime to $100$, you get to do arithmetic modulo $40$ in exponents.

So you can first focus on $17^{17}$ modulo $40$: $$\begin{align} 17^{17}&\equiv17\cdot289^8&\mod40\\ &\equiv17\cdot9^8&\mod40\\ &\equiv17\cdot81^4&\mod40\\ &\equiv17\cdot1^4&\mod40\\ &\equiv17&\mod40\\ \end{align}$$

So we have that $$17^{17^{17}}\equiv17^{17}\mod100$$

$$\begin{align} 17^{17^{17}}&\equiv17^{17}&\mod100\\ &\equiv17\cdot289^8&\mod100\\ &\equiv17\cdot89^8&\mod100\\ &\equiv17\cdot(-11)^8&\mod100\\ &\equiv17\cdot121^4&\mod100\\ &\equiv17\cdot21^4&\mod100\\ &\equiv17\cdot441^2&\mod100\\ &\equiv17\cdot41^2&\mod100\\ &\equiv17\cdot(50-9)^2&\mod100\\ &\equiv17\cdot(2500-900+81)&\mod100\\ &\equiv17\cdot81&\mod100\\ &\equiv17\cdot(-19)&\mod100\\ &\equiv-\left(18^2-1\right)&\mod100\\ &\equiv-323&\mod100\\ &\equiv77&\mod100\\ \end{align}$$

Answer 2

We essentially need to find $$17^{17^{17}}\pmod{100}$$

The usage of Carmichael function is more useful than the Euler Totient function if the modulus is composite like $100,20$ below.

We have $\lambda(100)=20$

$\displaystyle\implies 17^{17^{17}}\equiv 17^{17^{17}\pmod{20}}\pmod{100}$

Again, $\displaystyle \lambda(20)=4\implies17^4\equiv1\pmod{20}$

$\displaystyle\implies17^{17}=17\cdot(17^4)^4\equiv17\cdot1^4\equiv17\pmod{20}$

$\displaystyle\implies 17^{17^{17}}\equiv 17^{17} \pmod{100}$

Now, $\displaystyle17=20-3,\implies 17^{17}=(20-3)^{17}=-3^{17}+\binom{17}1\cdot3^{16}\cdot20\pmod{100}$ as the higher terms contains $20^2$ hence divisible by $100$

Now, as $\displaystyle3\equiv-1\pmod5, 3^{16}\equiv(-1)^{16}\equiv1\pmod5$

As $a\equiv b\pmod m\implies a\cdot n\equiv b\cdot n\pmod{m\cdot n},$

So, $\displaystyle\binom{17}1\cdot3^{16}\cdot20\equiv17\cdot1\cdot20\pmod{5\cdot20}\equiv40$

$\displaystyle\implies 17^{17}\equiv-3^{17}+40\pmod{100}$

Again, $\displaystyle3^{17}=3\cdot9^8$

But, $\displaystyle(10-1)^8=1-\binom8110\pmod{100}\equiv-79$

$\displaystyle\implies 3^{17}\equiv3(-79)\pmod{100}\equiv-237\equiv-37$

$\displaystyle\implies 17^{17}\equiv40-(-37)\pmod{100}\equiv77$

Answer 3

I thought maybe someone would be interested in another method very similar to what Alex and Lab presented. It needs another number-theory Theorem but uses smaller numbers:

We factor $100=4 \cdot 25$. Then as gcd(4,25)=1 and $17 \equiv 1 \mod 4$ by Chinese Remainder Theorem it suffices to calculate $$17^{17^{17}} \mod 25.$$ We calculate $\varphi(25)=4\cdot 5=20$. Using Fermat's Little Theorem, stating that $17^{\varphi(25)}\equiv 1 \mod 25$ we want to calculate $$17^{17} \mod 20.$$ We may do that the way Alex did. Alternatively we calculate $\varphi(\varphi(25))=\varphi(20)=2\cdot 4=8$ and apply Little Fermat a second time, getting $$17\equiv1 \mod \varphi(\varphi(25)) \\ \Rightarrow 17^{17} \equiv 17^{17 \mod \varphi(\varphi(25))} \equiv 17 \mod \varphi(25) \\ \Rightarrow 17^{17^{17}} \equiv 17^{17^{17} \mod \varphi(25)}\equiv 17^{17} \mod 25 .$$ Now in this special case we are lucky that it is easy to find $17 \cdot 3 \equiv 1 \mod 25$, that is $17^{-1} \equiv 3 \mod 25$. Thus, using Fermat again we may calculate $$17^{17} \equiv 17^{20-3} \equiv 17^{20}17^{-3}\equiv 17^{-3} \equiv 3^3 \equiv 27 \equiv 2 \mod 25.$$

So if $17^{17^{17}}\equiv x \mod 100$ is our final result, we have $$x\equiv 1 \mod 4 \\ x\equiv 2 \mod 25.$$ There is a standard algorithm to solve congruences of this type: Check multiples of 25 to find $$25 \equiv 1 \mod 4\\25 \equiv 0 \mod 25$$ and $$76 \equiv 0 \mod 4 \\76 \equiv 1 \mod 25.$$ Thus, the final result is $$x\equiv 1 \cdot 25 + 2\cdot 76 \equiv 77 \mod 100.$$