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

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

• What I would do is to compute $a$ where $17^{17} \equiv a (\mod 100)$ and then compute $a^{17} (\mod(100))$ Commented Dec 15, 2013 at 7:16
• maybe you want to say "we had to find $\cdots$" in your first sentence. Commented Dec 15, 2013 at 7:20
• Because $\phi(100)=40$, you know that $17^{40}\equiv1\pmod{100}$. (Using Carmichael function instead we could conclude the same with 20 instead of 40, but you may not have covered that bit of theory). So you first need to calculate the remainder of $17^{17}$ modulo $40$. Say that you get $17^{17}=k\cdot40+r$. Then $$17^{17^{17}}=17^{40k+r}=(17^{40})^k\cdot17^r\equiv17^r\pmod{100}.$$ As $\phi(40)=16$ we know that $17^{16}\equiv1\pmod{40}$, so $r=17$. Commented Dec 15, 2013 at 7:21
• @Idonknow: That's wrong. You are calculating the remainder of $(17^{17})^{17}=17^{17\cdot17}$. The question was about the remainder of $17^{17^{17}}=17^{(17^{17})}$. Commented Dec 15, 2013 at 7:26
• To be fair, "17^17^17" seems ambiguous. Written that way, following the "order of operations" and reading left to right, it would be $(17^{17})^{17}$. But since that is so easily written in another way, the convention is that we execute carets from right to left, and 17^17^17 is $17^{17^{17}}$ by convention. Commented Dec 15, 2013 at 7:29

## 3 Answers

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}

• What function is $\varphi(100)$?
– Newb
Commented Dec 15, 2013 at 7:34
• It's Euler's totient function. For any $n$, if $a$ is relatively prime to $n$, then $a^{\varphi(n)}\equiv1\mod n$. Understanding this well requires group theory. To compute it, you break $n$ down into its prime power factors ($25\cdot4$), compute each $p^k-p^{k-1}$ and multiply them together ($20\cdot2$). Commented Dec 15, 2013 at 7:41
• Very minor improvement: $41^2=(40+1)^2=1600+80+1$, slightly simpler (in my mind) than $(50-9)^2$ that you have there. Commented Dec 15, 2013 at 10:13
• Also, we could have used $\varphi(40)=16$ to make the first step (the reduction modulo 40) even shorter. Commented Dec 15, 2013 at 19:01

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

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$