fast modular exponentation doubt Compute $3^{1048576} \pmod 7$ using fast modular exponentiation.
I found that $1048576=2^{20},$ so I got $3^{2^{20}} \pmod 7$
fast modular algorithm is to reduce the powers. 
Please guide me the initial steps to follow the question. 
 A: $\pmod 7, 3^1 \equiv 3, 3^2 \equiv 2, 3^3 \equiv 6$ therefore $3$ is a primitive root $\bmod 7$. Therefore it has a cycle of 6 (you can continue to check all powers if you prefer, until $3^6\equiv 1\bmod 7$).
The exponent here, $1048576 \equiv 4 \bmod 6$. So $3^{1048576} \equiv 3^4 \bmod 7$ and $3^4\equiv 4 \bmod 7$.
Therefore $3^{1048576} \equiv 4 \bmod 7$
A: Using Fermat's Theorem, $3^{7-1}\equiv1\pmod7$
Now $2\equiv-1\pmod3\implies2^{19}\equiv(-1)^{19}\equiv-1$
$\implies2^{20}\equiv-1\cdot2\equiv-2\equiv4\pmod6$
So, $3^{2^{20}}\equiv3^4\pmod7\equiv4$
A: ${\rm mod}\ 7\!:\,$ repeatedly squaring $\,3\overset{\large x^2}\to 2\overset{\large x^2}\to \color{}4\overset{\large x^2}\to 2\overset{\large x^2}\to 4\to \cdots\, $ is cyclic via $\,x^4\equiv x\,$ for $\,x\equiv 2,4.$ 
Alternatively, $ $ notice that $\ \color{#0a0}{3^4\equiv 4},\ \color{#c00}{4^{\large 4}\equiv 4}\,\Rightarrow\, (\color{#0a0}{3^{\,\large 4}})^{\large\, {4^{\rm N}}}\!\equiv \color{#0a0}4^{\large\,\color{#c00}{4^{\rm\large{N}}}}\color{#c00}{\equiv 4}$
