I'm trying to solve the following exercise: $$2017^{2016^{2015}} \mod 1000,$$
here's what I've already come up with:
Using Euler's conrgruence, one finds that $$2017^{2016^{2015}} \equiv 2017^{2016^{2015}\mod \phi(1000)}\mod 1000,$$
where $\phi$ is the Euler function, with $\phi(1000) = 400.$ Because $\gcd(400,2016) \neq 1$, Euler isn't directly applicable. Instead, I did this (I've found this method somewhere online, so I don't know if this is correct):
$$2016^{2015} \mod 400 = (2016^{2015 \mod \phi(25)} \mod 25) \mod 400,$$ and therefore, $$2016^{2015} \mod 400 = (2016^{15} \mod 25) \mod 400.$$
However, I don't have any idea on how to continue further. Any thoughts?
Thanks!
Best Answer
As $\displaystyle2017\equiv17\pmod{1000},2017^m\equiv17^m$ for any integer $m$
Use Carmichael function, $\lambda(1000)=100$
$$\implies17^{(2016^{2015})}\equiv17^{(2016^{2015})\pmod{100}}\pmod{1000}$$
Now $2016\equiv16\implies2016^{2015}\equiv16^{2015}\pmod{100}$
As $(16,100)=4$ let use find $16^{2015-1}\pmod{100/4}$
$16^{2014}=(2^4)^{2014}=2^{8056}$
As $\displaystyle\lambda(25)=\phi(25)=20$ and $8056\equiv16\pmod{20},2^{8056}\equiv2^{16}\pmod{25}$
$2^8=256\equiv6\pmod{25}\implies2^{16}\equiv6^2\equiv11$
$\implies16^{2014}\equiv11\pmod{25}$
$\implies16^{2014+1}\equiv11\cdot16\pmod{25\cdot16}\equiv176\pmod{400}\equiv76\pmod{100}$
$$\implies17^{(2016^{2015})}\equiv17^{76}\pmod{1000}$$
Now $$17^{76}=(290-1)^{38}=(1-290)^{38}\equiv1-\binom{38}1290+\binom{38}2290^2\pmod{1000}$$
Now $\displaystyle38\cdot29=(40-2)(30-1)\equiv2\pmod{100}\implies\binom{38}1290\equiv20\pmod{1000}$
and $\displaystyle\binom{38}229^2=\dfrac{38\cdot37}2(30-1)^2\equiv3\pmod{10}$
$\displaystyle\implies\binom{38}2290^2\equiv3\cdot100\pmod{10\cdot100}$