Calculation of Large Exponents Modulo a Prime

[Vespero]

Homework Statement

In my Number Theory class, we learned how to calculate the value of large exponents modulo primes using Euler's Theorem. I understand how to do this with exponents larger than the value of the totient function of the prime, which is p-1, but what about when the exponent is actually smaller than that value? For example, if I have $95^{65}\ mod\ 131$, I don't see how I can reduce the exponent the way I would for something like $95^{261} \equiv 95^{2(130)+1} \equiv 95\ (mod\ 131)$.

Homework Equations

$x^{p-1} \equiv 1\ (mod\ p)$

and the more general form for a composite number. Also, any basic properties of exponents and moduli that I'm missing.

The Attempt at a Solution

I'm just not sure where to begin. Obviously, 65 is half of 130, and we know that $95^{130} \equiv 1\ (mod\ 131)$, but how can I use that?

 

[SammyS]

Homework Statement

In my Number Theory class, we learned how to calculate the value of large exponents modulo primes using Euler's Theorem. I understand how to do this with exponents larger than the value of the totient function of the prime, which is p-1, but what about when the exponent is actually smaller than that value? For example, if I have $95^{65}\ mod\ 131$, I don't see how I can reduce the exponent the way I would for something like $95^{261} \equiv 95^{2(130)+1} \equiv 95\ (mod\ 131)$.

Homework Equations

$x^{p-1} \equiv 1\ (mod\ p)$

and the more general form for a composite number. Also, any basic properties of exponents and moduli that I'm missing.

The Attempt at a Solution

I'm just not sure where to begin. Obviously, 65 is half of 130, and we know that $95^{130} \equiv 1\ (mod\ 131)$, but how can I use that?

You have pretty nearly answered your own question.

You have that $95^{65\cdot2}\equiv1 (\text{mod} 131)\,.$ Then $95^{65\cdot2} - 1\equiv0 (\text{mod} 131)\,.$

Use the fact that $95^{65\cdot2}=(95^ {65})^2\,.$

Factor the difference of squares and see where that leads you.

 

[I like Serena]

Hi Vespero!

The generic method is to do this:
$$95^{65} \equiv 95^{2\cdot 32+1} \equiv (95^2)^{32} \cdot 95 \equiv (95^2 \textrm{ mod } 131)^{32} \cdot 95 (\textrm{mod } 131)$$
Repeat, until you are done.

If you want, you can factor 95 first into 5 x 19 to get easier calculations.

This is quite a bit of work, although you can recycle some of your work.

@SammyS: I believe your method leads to 2 solutions...