# Thread: How do I simplify this mod question further?

1. ## How do I simplify this mod question further?

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

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

$43743747=4000\times 10935 + 3747$

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

reduces to just:

$457^{3747}~mod~4001$

How can I reduce things further without taking all day?

Thanks.

2. ## Re: How do I simplify this mod question further?

Do I just need to keep taking out factors of 3747 and computing the smaller numbers mod 4001 until I have reduced it? The largest exponent I can raise 457 to that doesn't produce a number in scientific notation with my calculator is 3 :S