Calculate modulo solution of a number with a high exponent

Question

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?

Answer 1

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}

Answer 2

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

Answer 3

typing python -c 'print pow(4,217,391)'

on a better computer yields 55