1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ I think the idea that you found online is this: to calculate $x^y$ mod $400$, you calculate $x^y$ mod $25$ (which is equal to $x^{y \mod \phi(25)}$ mod $25$), and $x^y$ mod $16$ (which is equal to $x^{y \mod \phi(16)}$ mod $16$). Then combine them (easy in your case, because $x = 0$ mod $16$). $\endgroup$ – TonyK Aug 23 '15 at 11:53
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I can't work out where the final answer is supposed to be here, but $17^{76}$ mod $1000$ is equal to $281$. $\endgroup$ – TonyK Aug 23 '15 at 11:50
  • $\begingroup$ So my whole approach was wrong? That's disappointing. $\endgroup$ – Drive Aug 23 '15 at 11:52
  • $\begingroup$ And thanks TonyK $\endgroup$ – Drive Aug 23 '15 at 11:53
  • $\begingroup$ @TonyK, Have you find anything wrong here? $\endgroup$ – lab bhattacharjee Aug 23 '15 at 12:00
  • $\begingroup$ $\binom{38}229^2$ mod $10$ is equal to $3$, not $8$. (Also you have $\binom{8}{1}$ and $\binom{8}{2}$ as misprints for $\binom{38}{1}$ and $\binom{38}{2}$, which made it hard for me to work out where your real mistake was.) $\endgroup$ – TonyK Aug 23 '15 at 12:17

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.