1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What I would do is to compute $a$ where $17^{17} \equiv a (\mod 100)$ and then compute $a^{17} (\mod(100))$ $\endgroup$ – Idonknow Dec 15 '13 at 7:16
  • $\begingroup$ maybe you want to say "we had to find $\cdots$" in your first sentence. $\endgroup$ – mathlove Dec 15 '13 at 7:20
  • 1
    $\begingroup$ 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$. $\endgroup$ – Jyrki Lahtonen Dec 15 '13 at 7:21
  • $\begingroup$ @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})}$. $\endgroup$ – Jyrki Lahtonen Dec 15 '13 at 7:26
  • $\begingroup$ 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. $\endgroup$ – alex.jordan Dec 15 '13 at 7:29
11
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What function is $\varphi(100)$? $\endgroup$ – Newb Dec 15 '13 at 7:34
  • 1
    $\begingroup$ 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$). $\endgroup$ – alex.jordan Dec 15 '13 at 7:41
  • $\begingroup$ Very minor improvement: $41^2=(40+1)^2=1600+80+1$, slightly simpler (in my mind) than $(50-9)^2$ that you have there. $\endgroup$ – Asaf Karagila Dec 15 '13 at 10:13
  • $\begingroup$ Also, we could have used $\varphi(40)=16$ to make the first step (the reduction modulo 40) even shorter. $\endgroup$ – alex.jordan Dec 15 '13 at 19:01
0
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.