Calculate modulo solution of a number with a high exponent I need some help calculating the solution for the following equation:
$ 4^{217} = x \text{ (mod 391)} $
Using power rules ($4^{217} = 2^{434}$) and Eulers theorem ($\phi(391) = 352$) I was able to reduce the term to:
$ 2^{82} = x \text{ (mod 391)} $
This is where my search for a solution comes to a halt. I have been able to further reduce this term to
$ (3^6 * (31^2)^3 * 2^4) = x \text { mod (391)} $
but that is where I got stuck, because I feel like there should be a far more elegant way than the brute force attempt I took from $2^{82}$.
What other tricks can I use to find the correct solution for this equation?
 A: Separating this out into $\bmod 17$ and $\bmod 23$ problems, we have:
$\begin{cases}
x\equiv 2^{434} \equiv 2^{2} \equiv 4 \bmod 17 \\
x\equiv 2^{434} \equiv 2^{16} \equiv 16^4 \equiv (-7)^4 \equiv 49^2 \equiv 3^2 \equiv 9 \bmod 23
\end{cases}$
Then $17k+4\equiv 9 \bmod 23$
so $17k\equiv -6k\equiv 5\bmod 23$
and since $6\cdot 4 \equiv 1 \bmod 23$
we have $k\equiv -4\cdot 5 =-20 \equiv 3 \bmod 23$.
Then $x\equiv 3\cdot 17 + 4 \equiv 55 \bmod 391$.
A: Using the Chinese remainder theorem allows for a shorter computation by hand: you can easily check that $2$ has order $8$ mod. $17$ and order $11$ mod. $23$, hence it has order $88=\operatorname{lcm}(8,11)$ mod. $391$. So 
$$2^{82}\equiv 2^{-6}\mod 391.$$
Now it's easy to compute the inverse  of $2^{6}\mod 391$  with the extended Euclidean algorithm:
\begin{array}{rrrr}
r_i&u_i&v_i&q_i\\
\hline
391&0&1\\
64&1&0&6 \\
\hline
7&-6&1&\quad9\\
1&\color{red}{55}&-9\\
\hline
\end{array}
A: typing 
    python -c 'print pow(4,217,391)' 
on a better computer yields 55
