# Math Help - Exponents and Fermat's Little Theorem

1. ## Exponents and Fermat's Little Theorem

I am attempting to solve two problems. The first is to compute, in linear time, a^(b^c) mod p. The hint is to use Fermat's Little Theorem to simplify the problem.

The second problem is to simplify 5^596 mod 599.

These problems seem so easy, and yet their solutions esacape me.

In the first problem, I cannot simplify a^(b^c) mod p using Fermat's Little Theorem. Somehow I need to manipulate the problem to the form of:

( a^(p-1) * a^(p-1) * ... * a^x) mod p

Can anyone offer suggestions or guidance on these two problems?

Thank you in advance for your help.

2. In regards to the simplification problem (5^596 mod 599): I know the answer is 24, and I also know I can simplify 5^596 to:

5^596
= 5^(598-2)
= 5^598 * 5^-2

The problem (5^598 * 5^-2) mod 599 becomes (1* 5^-2) mod 599. But this simplified problem does not equal 24. Does anyone know what I'm doing wrong?

3. But this simplified problem does not equal 24.
Yes, it does. Find $5^{-1}\pmod{599}$ and then find its square.

4. I'm sorry, but I still don't see how this works. 5^-1 mod 599 equals 120.

5. 5^-1 mod 599 equals 120.
And $120^2=14400\equiv24\pmod{599}$ (can be checked by direct calculation).