My homework question asks me to compute $2^{1386}\mod1387$ without factoring or directly determining whethere 1387 is prime or not; and only use paper, pencil and a basic calculator
I used fast exponential method and was able to determine $i=1,3,5,6,8,10$ but unable to find a way to calculate $2^{2^i} \mod 1387$ when $2^{2^i}$ becomes so large, should I apply fast exponetiation again?
Performing this calculation by hand is somewhat tedious, but not exceptionally difficult:
$$2^2=4,\ 2^{2^2}=16,\ 2^{2^3}=256$$
By hand, this would be the point where the guess-and-check work starts:
$$\begin{align} 2^{2^4}&=65536 \\ &=50*1387-k=69350-k \\ &=47*1387+m \\ &=69350-4161+m \\ &=65189+m \\ \implies m&=347 \\ 2^{2^5}\equiv 347^2&=350^2-699-697-695 \\ &=122500-2091=120409 \\ &=90*1387-k \\ &=138700-13870-k=120409+4421-k \\ &=87*1387-k=138700-13870-4161-k \\ &=120409+260-k \\ \implies k&=260 \\ 2^{2^6}\equiv (-260)^2&=67600 \\ &=48*1387+k \\ &=65189+1387+k \\ &=66576+k \\ \implies k&=1024 \\ 2^{2^7}\equiv 1024^2&=2^{20} \\ &=2^4\cdot 2^{16}\equiv 4\cdot 4\cdot 347 \\ &=4\cdot 1388\equiv 2^{2^1}\cdot 1\end{align}$$
So now we have completed six steps and found that the calculation loops back to the beginning, we know that the next three steps are duplications of previous steps. In particular, we know that
$$2^{2^8}\equiv 2^{2^2}=16,\ 2^{2^{10}}\equiv 2^{2^4}\equiv 347\pmod{1387}$$
Now the calculation resolves to
$$2^{2^1}\cdot 2^{2^3}\cdot 2^{2^5}\cdot 2^{2^6}\cdot 2^{2^8}\cdot 2^{2^{10}}$$
Wait, we just showed that $2^{2^8}\equiv 2^{2^2}$ and also $2^{2^{10}}\equiv 2^{2^4}$, so this means that the calculation is actually
$$2^{2^1}\cdot 2^{2^2}\cdot 2^{2^3}\cdot 2^{2^4}\cdot 2^{2^5}\cdot 2^{2^6}$$
$$=2^{2+2^2+2^3+2^4+2^5+2^6}=2^{2^7-2}={2^{2^7}}\cdot 4^{-1}\equiv 4\cdot 4^{-1}=1\pmod{1387}$$
Now the question arises: the "aha!" moment where we found that instead of
$$2^{2^1}\cdot 2^{2^3}\cdot 2^{2^5}\cdot 2^{2^6}\cdot 2^{2^8}\cdot 2^{2^{10}}$$
we actually only needed to calculate
$$2^{2^1}\cdot 2^{2^2}\cdot 2^{2^3}\cdot 2^{2^4}\cdot 2^{2^5}\cdot 2^{2^6}$$
was very fortunate. Is it the case that $1387$ is a special number in this way, or is it possible that more numbers will exhibit this property?
