1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Calculation of Large Exponents Modulo a Prime

  1. Oct 29, 2011 #1
    1. The problem statement, all variables and given/known data

    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].

    2. Relevant 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.

    3. 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?
  2. jcsd
  3. Oct 29, 2011 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    You have pretty nearly answered your own question.

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

    Use the fact that [itex]95^{65\cdot2}=(95^ {65})^2\,.[/itex]

    Factor the difference of squares and see where that leads you.
  4. Oct 30, 2011 #3

    I like Serena

    User Avatar
    Homework Helper

    Hi Vespero! :smile:

    The generic method is to do this:
    [tex]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)[/tex]
    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...
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook