- #1
Vespero
- 28
- 0
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 [itex]95^{65}\ mod\ 131[/itex], I don't see how I can reduce the exponent the way I would for something like [itex]95^{261} \equiv 95^{2(130)+1} \equiv 95\ (mod\ 131)[/itex].
Homework Equations
[itex]x^{p-1} \equiv 1\ (mod\ p)[/itex]
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 [itex]95^{130} \equiv 1\ (mod\ 131)[/itex], but how can I use that?