I am attempting to solve the following congruence: $420292^{257} \equiv x \pmod {481391}$ The main method that I know to simplify this power is to use powers of $2$ so $257^2 = 66049$, however this is less than the modulus and is congruent to itself, and the numbers keep increasing incredibly large that I feel this is not the correct method.
I have also been considering Euclid's algorithm, but the problem with the power still remains.
What other approach can I try to simplify this congruence?
On
Let $a = 420292$. Repeated squaring will give you $a^2\mod 481391, a^4 \mod 481391, a^8 \mod 481391, \ldots, a^{256} \mod 481391$. Then $a^{257} = a \cdot a^{256}$.
But I hope you're not doing the computations by hand, so you might as well just ask the computer for the whole thing.
Hint: factor $481391$ and then use Chinese Remainder Theorem.