# Nested powers remainder problem.

I'm struggling a little with a question concerning power towers.

I have this number $$2018^{\large {2017}^{\Large 16050464}}\!$$ and I want to find the remainder when it is divided by 1001.

I have managed to reduce it down to $$16^{\large {2017}^{\Large 224}}$$ but I can't get any further past this point. I feel like I need to reduce $$2017^{224}$$ to an integer but I am unsure of how to do this.

Just a side note: I have to do it without the Chinese remainder theorem.

Any help is welcome, thanks.

• Take a look at my answer on this question - math.stackexchange.com/questions/3081806/finding-remainders/… – user626177 Jan 22 at 18:42
• @someone is it possible to do without the Chinese remainder theorem? – user637295 Jan 22 at 18:51
• Chinese remainder theorem is not used in that answer. Feel free to ask if something is not clear. – user626177 Jan 22 at 18:54
• @someone The method you use there is in fact one form of CRT. – Bill Dubuque Jan 22 at 19:15
• @BillDubuque Well the fact that I didn't even know about that shows that you don't have to be familiar with CRT to be able to do that calculation, right ? – user626177 Jan 22 at 19:53

$$16^{\large 3}\!\equiv 1$$ mod $$7\,\&\,13;\,$$ $$16^{\large 5}\!\equiv 1\pmod{\!11}\,$$ so $$\,16^{\large\color{#0a0}{15}}\!\equiv 1\,$$ mod $$7,11,13$$ so also mod their lcm $$=1001$$.
Thus $$\bmod 1001\!:\ 2018^{\large 2017^{\Large 4N}}\!\!\!\equiv 16^{\large 2017^{\Large 4N}\!\!\bmod\color{#0a0}{15}}\!\!\equiv 16^{\large \color{#c00}7^{\Large\color{#c00} 4N}\!\!\bmod\color{#0a0}{15}}\!\!\equiv 16^{\large\color{#c00} 1^{\Large N}}\!\!\equiv 16$$
with the expt calculation: $$\bmod\color{#0a0}{15}\!:\,\ 2017\equiv 7,\$$ and $$\ \color{#c00}7^{\large\color{#c00}4}\! \equiv 4^{\large 2}\!\equiv\color{#c00} 1$$
• Could you just explain what you have done on the first line, so where the $16^{3}$ etc have come from? Have you chosen $16^{3}$ and $16^{5}$ because they are congruent to 1 and if so how did you know that start with? Thanks – user637295 Jan 22 at 22:12
• @LittleRichard They are the order of $16$ mod $p$, i.e. the least $n>0$ such that $\,16^n\equiv 1\pmod{\! p}$, e.g. mod $\,p = 7\!:\ 16^3\equiv 2^3\equiv 1$. By Fermat $\,16^{p-1}\equiv 1\pmod{p>2}\,$ so the order must divide $\,p-1.$ – Bill Dubuque Jan 22 at 22:14