Calculation of Large Exponents Modulo a Prime

In summary, the two solutions are as follows: The first solution has 95^{65}=-1 (\textrm{mod} 131) and the second solution has 95^{65}=1 (\textrm{mod} 131).
  • #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?
 
Physics news on Phys.org
  • #2
Vespero said:

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

1. How do you calculate large exponents modulo a prime number?

The calculation of large exponents modulo a prime number involves using the basic rules of modular arithmetic, such as the Chinese Remainder Theorem and Euler's Theorem.

2. What is the purpose of calculating large exponents modulo a prime number?

Calculating large exponents modulo a prime number is useful in fields such as cryptography and number theory, as it allows for more efficient and secure computations.

3. What is the significance of using a prime number in modulo calculations?

Using a prime number in modulo calculations ensures that the results are unique, as every number can be uniquely represented in terms of its prime factors.

4. Can large exponents be calculated without using a prime number in the modulo operation?

Yes, large exponents can be calculated without using a prime number in the modulo operation, but the results may not be unique and may not have the same level of security.

5. Are there any limitations to calculating large exponents modulo a prime number?

Yes, there are limitations to calculating large exponents modulo a prime number, as the computation can become extremely time-consuming and complex for very large exponents.

Similar threads

  • Calculus and Beyond Homework Help
Replies
4
Views
929
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
16
Views
2K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
16
Views
1K
  • Calculus and Beyond Homework Help
Replies
11
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
705
  • Calculus and Beyond Homework Help
Replies
10
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
648
Back
Top