# Calculation of Large Exponents Modulo a Prime

• Vespero
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).
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?

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

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.

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

• Calculus and Beyond Homework Help
Replies
2
Views
96
• Calculus and Beyond Homework Help
Replies
4
Views
949
• 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
767
• Calculus and Beyond Homework Help
Replies
10
Views
2K