Mod-ladder

Studying $17^{17^{17}} \pmod{25}$ , we can work mod $\phi(25)=20$ in the first exponent and mod $\phi(20)=8$ in the top exponent. Thus $17^{17^{17}}\equiv 17^{17}\equiv 17^{-3}\equiv (17^{-1})^3\equiv 3^3\equiv 2 \pmod{25}$ . Clearly, $17^{17^{17}}\equiv 1 \pmod{4}$ . Examining 2, 27, 52, and 77, we find that $17^{17^{17}}\equiv \boxed{77} \pmod{100}$

First let ${ 17 }^{ 17 }\equiv y$ mod $x$ such that ${ 17 }^{ x }\equiv 1$ mod $100$ .

Then for some $z$ we have ${ 17 }^{ 17 }=y+xz\quad$ .

Then ${ 17 }^{ { 17 }^{ 17 } }\equiv { 17 }^{ y+xz }\equiv { 17 }^{ y }\times { 17 }^{ xz }\equiv { 17 }^{ y }$ mod $100$ .

We have ${ 17 }^{ x }=1+100k$ for some $k$ .

We have unit digit R.H.S of above equation as $1$ and L.H.S can have unit digit as $1$ only if $x=4a$ for some $a$ .

So ${ 17 }^{ 4a }\equiv { 21 }^{ a }\equiv 1$ mod $100$ .

We can easily see $a=5$ is smallest positive solution which give $x=20$ .

So ${ 17 }^{ 17 }\equiv y$ mod $20$ $\Rightarrow y=17$ .

Finally ${ 17 }^{ { 17 }^{ 17 } }\equiv { 17 }^{ y }\equiv { 17 }^{ 17 }\equiv 77$ mod $100$ .

I was just thinking about these towers and solution like this came up.I know there is solution from eulers theorem but still posted this.

We apply Euler's theorem here. 17 and 100 are coprime, so we find phi(100)=40. 17^40=1(mod100) Now we need to find the remainder of 17^17 when divided by 40. By euler's theorem again, phi(40)=16, implies 17^16=1(mod40) 17^17=17(mod40) so 17^(17^17)=17^17(mod100) which can be easily found to be 77.

By means of the Little Fermat Theorem $17^{40}$ $\equiv$ $1$ $\pmod{100}$ thus we have to calculate $17^{17}$ $\pmod{40}$ , using the same thorem we have that $17^{16}$ $\equiv$ $1$ $\pmod{40}$ $\rightarrow$ $17^{17}$ $\equiv$ $17^{1}$ = $1$ $\pmod{40}$ then it's easier to calculate $17^{17}$ $\pmod{100}$ $17^{17}$ $=$ $17*17^{2*8}$ $=$ $17*289^{8}$ $\equiv$ $17*89^{8}$ $\pmod{100}$ $=$ $17*89^{2*4}$ $=$ $17*7921^{4}$ $\equiv$ $17*21^{4}$ $\pmod{100}$ $=$ $3306177$ $\equiv$ $77$ $\pmod{100}$

$|17^{1\ }=17|\ \ \ \ \ \ \ \ \ \ |17^{2\ }=..89|\ \ \ \ \ \ \ \ \ |17^{3\ }=..13|\ \ \ \ \ \ \ \ \ \ |17^{4\ }=..21| \\ |17^{5\ }=57|\ \ \ \ \ \ \ \ \ \ |17^{6\ }=..69|\ \ \ \ \ \ \ \ \ |17^{7\ }=..73|\ \ \ \ \ \ \ \ \ \ |17^{8\ }=..41| \\ |17^{9\ }=97|\ \ \ \ \ \ \ \ \ \ |17^{10}=..49|\ \ \ \ \ \ \ \ |17^{11}=..33|\ \ \ \ \ \ \ \ \ \ |17^{12 }=..61| \\ |17^{13 }=37|\ \ \ \ \ \ \ \ \ \ |17^{14 }=..29|\ \ \ \ \ \ \ \ |17^{15 }=..93|\ \ \ \ \ \ \ \ \ \ |17^{16 }=..81| \\ {\color{#D61F06}{ |17^{17}=77 | } } \ \ \ \ \ \ \ \ \ |17^{18 }=..09|\ \ \ \ \ \ \ \ \ |17^{19}=..53|\ \ \ \ \ \ \ \ \ \ |17^{20}=..01| \\ \therefore\ \Large 17^{17^{17}}=17^{77\ \equiv\ 17\ mod\ 20}=17^{17}=\Huge \color{#3D99F6}{77}$

Note:- On a simple scientific calculator, only the following is sufficient.
$|17^{1\ }=17|\ \ \ \ \ \ \ \ \ \ |17^{2\ }=..89|\ \ \ \ \ \ \ \ \ |17^{3\ }=..13|\ \ \ \ \ \ \ \ \ \ |17^{4\ }=..21| \\ |17^{5\ }=57|\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ |17^{8\ }=..41| \\ .........................................\ \ \ \\ .........................................\ \ \ \\ {\color{#D61F06}{ |17^{17}=77 | } }\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ |17^{20}=..01|$
Reason.:-
1] Unit cycle has a period of 4.
2] First column unit is 7.
Tenth digit in first column increase by 4.
.........(a) So after adding 17-1=16, we will have 17 as exponent. This is 5th row, first column.
.........(b)This would be in row 5 column 1. So the tenth digit is = 1+(4-1)=1+(4 increment of 4) =17. Unit digit of the Tenth digit is 7, So last two digit, 77. That is to say (17^{17}=.....77 3]In the cycle, only if last two digits are 01, the next row same column would give use the initial last to digits.
Unit 1 appear in the fourth column.
Its increment in tenth digit is 2. So in four more columns , {2+(4 2)}=10, there is zero at the end for tenth digit.
So the the cycle of tenth digit is, 4+4 4=20.

The above would be helpful if the exponents are big. The rules given above are derived from the 4X5 table given above.
The method can solve TOWER problem with the help only of a simple scientific calculator and no knowledge of Theory of Numbers.

Can someone please explain how they got that 17^17 is congruent to 77 (mod 100)?

The last digit repeats with period 4, it is 1 for powers 4k, 7 for 4k+1 etc.

Looking for 01 to find the period for the last 2 digits; it will have to be one of those ending with 1 so 4k-th power. k=1: 21, k=2: 21*21 ends with 41; then 61, 81 and with k=5 we get 01 so the period is 20.

Now we need to 17^17 mod 20. 17^16 ends with 81, so 17^17 ends with 77. Therefore the answer is 17 : 17^17 = 20k + 17 .

17^17^17 = 17 ^ (20k + 17); because of the cycle with perod 20 the last two digits are the same as of 17^17, so 77.

For similar problems, check Towers of Powers of 17 or Time for 7

I tried Euler - Fermat and then repeated squaring method:

a. Euler - Fermat:

Since $gcf(17, 100) = 1$ and $17^{17} \equiv 17 \mod \varphi(100)$ , then $17^{17^{17}}\equiv17^{17}\mod 100$ .

b. Repeated squaring method:

$17^{17} \equiv 17(17^{16} \mod 100)$

$\phantom{17^{17}}\equiv 17 (17^2 \mod 100)^{8}$

$\phantom{17^{17}}\equiv 17 (89^2 \mod 100)^4$

$\phantom{17^{17}}\equiv 17 (21^2 \mod 100)^2$

$\phantom{17^{17}}\equiv 17 (41^2 \mod 100)$

$\phantom{17^{17}}\equiv 17(81 \mod 100)$

$\phantom{17^{17}}\equiv 77$