Use the fact that 4001 is a prime to compute $\displaystyle r \equiv 457^{43743747}~mod~4001$, and find an integer k such that $\displaystyle r^k\equiv 457~mod~4001$.

So I used Fermat's little theorem to reduce the problem initially:

$\displaystyle 43743747=4000\times 10935 + 3747$

$\displaystyle \therefore 457^{4000\times 10935}457^{3747}~mod~4001$

reduces to just:

$\displaystyle 457^{3747}~mod~4001$

How can I reduce things further without taking all day?

Thanks.