$2017^{2016^{2015}} \mod 1000$

Question

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!

Answer 1

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

Answer 2

As $2017$ is coprime to $1000$, we have $2017^{2016^{2015}}\equiv2017^{2016^{2015}\bmod\varphi(1000)}\mod 1000$.

• As $\varphi(1000)=\varphi(2^3\cdot 5^3)=400$, we first have to compute $2016^{2015}\bmod 400=16^{2015}\bmod 400$.

Now $16$ divides $400$, so we can't reduce the exponent modulo $400$. We'll use the Chinese Remainder theorem for the computation. From $400=16\cdot25$ and the factors are coprime, we know that $$\mathbf Z/400\mathbf Z\simeq\mathbf Z/16\mathbf Z\times\mathbf Z/25\mathbf Z.$$ Hence if we know $16^n\bmod 16$ (which is $0$) and $16^n\bmod 25$, the reverse isomorphism will give us $16^n\bmod400$. Now this reverse isomorphism is derived from a Bézout relation between $16$ and $25$. Such a relation is obtained from the Extended Euclidean algorithm and we have: $$11\cdot 16-7\cdot 25=1.$$ The reverse isomorphism is then given by: $$(\alpha,\beta)\longmapsto \beta\cdot 11\cdot 16+\alpha\cdot(-7)\cdot25.$$ In the present case, $\alpha=0$, hence $16^n\equiv(16^n\bmod25)\cdot176\mod400$.

Observe $16$ has order $5$ modulo $25$: indeed $\;16^2=256\equiv 6\mod 25$, hence $\;16^4\equiv 6^2\equiv 11\mod25$, and finally $\;16^5\equiv 11\cdot 16\equiv 1\mod25$ Consequently, $16^{2015}=\bigl(16^5\bigr)^{403}\equiv 1\mod 25$.

Thus $\;2016^{2015}\bmod 400\equiv 16^{2015}\equiv 176\mod 400$

• Let's go back to the initial problem: $2017^{2016^{2015}}\equiv 17^{2016^{2015}\bmod400}\equiv17^{176}\mod 1000$.

We will use again the Chinese Remainder theorem: as $17\equiv 1\mod 8$, $\;17^{176}\equiv \color{red}{1}\mod8$ too.

Modulo $125$, $\;17^{176}\equiv17^{176\bmod\varphi(125)}=17^{76}$. The fast exponentiation algorithm results in $\;17^{176}\equiv \color{red}{31}\mod 125$. As a Bézout's relation between $8$ and $125$ is: $$47\cdot 8-3\cdot 125=1,$$ we obtain that $$17^{176}\equiv \color{red}{31}\cdot 47\cdot8- \color{red}{1}\cdot3\cdot 125=31\cdot376-375=281 \mod 1000. $$