• Support PF! Buy your school textbooks, materials and every day products Here!

Calculation of Large Exponents Modulo a Prime

  • Thread starter Vespero
  • Start date
  • #1
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?
 

Answers and Replies

  • #2
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,264
977

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?
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.
 
  • #3
I like Serena
Homework Helper
6,577
176
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...
 

Related Threads on Calculation of Large Exponents Modulo a Prime

  • Last Post
Replies
1
Views
2K
Replies
4
Views
3K
Replies
0
Views
9K
Replies
0
Views
2K
Replies
2
Views
1K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
3
Views
10K
Replies
9
Views
3K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
2
Views
819
Top