Easy Number Theory modular exponentiation

Question

So I was reading through some old questions I found

For the question I was asked to explain why for $\,2018^{\large 2017^{\LARGE n}}\!\!\bmod 1001$

Where n is an integer between 14 million and 17 million

Why are there are only 4 possible values?

So I figured it out through taking 2017$^n$ (mod 720) As 720 = phi(1001)

Using modular exponentiation I noted a few facts

2017$^1$ (mod720) ≡ 577

2017$^2$ (mod720) ≡ 289

2017$^4$ (mod720) ≡ 1

So therefore anything after this point will be congruent to 1 (mod 720)

So for example if I obtain 2017$^{15}$ = 2017$^8$ * 2017$^4$ * 2017$^2$ * 2017$^1$ Well this is just the same as 1 * 1 * 289 * 577 = 433(mod26)

And then I just finished the question by doing 2018$^{433}$ (mod 1001) ≡ 653

Now I just showed this with the 3 other patterns but basically I was wondering if there was a more elegant way to put this?

I feel like i'm there but it's not really a clean answer

Any help is appreciated.

Answer 1

Because of $\ \ \gcd(2018,1001)=1$, we can apply Euler's theorem and reduce the exponent modulo $\varphi(1001)=720$. The exponent is itself a power and because of $$2017^4\equiv 1\mod 720$$ which you found out, we can reduce $n$ modulo $4$. Hence there are only $4$ possible residues.

Answer 2

Below is the Theorem that you are implicitly applying.

Theorem $\ \ \color{#c00}{a^{\large n} \equiv 1}\pmod{\! m},\ \color{#0a0}{b^{\large k}\equiv 1}\pmod {\!n}\,\Rightarrow\, a^{\Large b^{\Large N}}\!\!\!\in \{a,\, a^{\large b},\, a^{\large b^{\Large 2}},\ldots\, a^{\large b^{\Large k-1}}\}\pmod{\!m}$

Proof $\ $ Dividing $\,N\,$ by $\,k\,$ yields $\ N = kq+R\ $ with $\,0\le R\le k-1.\,$

$\!\bmod n\!:\ \ \ b^{ N} =\, b^{\large R+kq} \,=\ b^{ R} (\color{#0a0}{b^{\large k}})^{\large q}\,\equiv\, b^{R}\, \color{#0a0}1^{\large q}\equiv b^{R},\: $ so $\ b^N = b^R\!+ni\ $ thus

$\!\bmod m\!:\ a^{\large b^{\Large N}}\!\!\! = a^{\Large b^{\Large R}\! + ni}\! \equiv a^{\Large b^R}\! (\color{#c00}{a^{\Large n}})^{\Large i}\!\equiv a^{\Large b^R}\! \color{#c00}1^{\Large i}\equiv a^{\Large b^R}$

Corollary $\ a^{\Large b^{\LARGE N}}\!\!\equiv\,\color{#c00}a^{\Large \color{#0a0}b^{\LARGE N\bmod\color{#0a0} k} \!\bmod\color{#c00} n}\!\! \pmod{\!m}$