Find the remainder that gives $2^{3^{5^{7^{11}}}}$ when divided by $2016$ using Euler's totient function. $$$$ I've tried with the property: $$ 11 \equiv 11 \mod \phi^4(2016) \iff 11 \equiv 11 \mod 32 $$ $$ \implies 7^{11} \equiv 7^{11} \mod \phi^3(2016) \iff 7^{11} \equiv 23 \mod 64 $$ $$ \implies 5^{7^{11}} \equiv 5^{23} \mod \phi^2(2016) \iff 5^{7^{11}} \equiv 173 \mod 192 $$ $$ \implies 3^{5^{7^{11}}} \equiv 3^{173} \mod \phi(2016) \iff 3^{5^{7^{11}}} \equiv 3^{173} \mod 576, $$ but $\gcd(3, 576) = 3 \ne 1$ so I can't use this property. Even if it somehow passes, then $\gcd(2, 2016) = 2 \ne 1$, so I again have the same problem. Any help is appreciated.
1 Answer
In order to work out $2^{3^{5^7}}$ mod $2016$, you should first work out what it is mod $32$ and mod $63$. Then (by the Chinese remainder theorem) that is enough to deduce the answer.
Now $2^{3^{5^7}}\equiv 0$ mod $32$, so the problem reduces to finding it mod $63$. We know that $2^{36}\equiv 1$ mod $63,$ so now you need to work out $3^{5^7}$ mod $36$. You can use the same approach here: split $36$ into two appropriate factors and deal with them separately.
-
$\begingroup$ I understand it now. So remainder is 512. Thank you $\endgroup$ Jun 21, 2017 at 11:23