1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Take a look at my answer on this question - math.stackexchange.com/questions/3081806/finding-remainders/… $\endgroup$ – user626177 Jan 22 at 18:42
  • $\begingroup$ @someone is it possible to do without the Chinese remainder theorem? $\endgroup$ – user637295 Jan 22 at 18:51
  • $\begingroup$ Chinese remainder theorem is not used in that answer. Feel free to ask if something is not clear. $\endgroup$ – user626177 Jan 22 at 18:54
  • $\begingroup$ @someone The method you use there is in fact one form of CRT. $\endgroup$ – Bill Dubuque Jan 22 at 19:15
  • $\begingroup$ @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 ? $\endgroup$ – user626177 Jan 22 at 19:53
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – user637295 Jan 22 at 22:12
  • $\begingroup$ @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.$ $\endgroup$ – Bill Dubuque Jan 22 at 22:14

Your Answer

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