# Solve 99^99 congruent to (mod 47) using Fermat's Theorem

• pivoxa15
In summary, to compute 99^{99} \equiv (mod 47) using Fermat's theorem, you can first use Fermat's little theorem to reduce the exponent to 99^7 (mod 47). Then, by repeatedly squaring and reducing modulo 47, you can find 99^4 (mod 47) quickly, making the overall calculation easier and faster. Ultimately, you can use this method to find 99^{99} \equiv (mod 47) by reducing the exponent to smaller and smaller numbers until you reach a manageable calculation.
pivoxa15
The question is

Use Fermat's Theorem to compute the following:

$$99^{99} \equiv (mod 47)$$

I spent over an hour on it but could only reduce it to $$99^7 \equiv (mod 47)$$

I think I am missing something. So if you can help, it would be great. Please provide an explanation as well.

Thanks

pivoxa15 said:
The question is

Use Fermat's Theorem to compute the following:

$$99^{99} \equiv (mod 47)$$

I spent over an hour on it but could only reduce it to $$99^7 \equiv (mod 47)$$

I think I am missing something. So if you can help, it would be great. Please provide an explanation as well.
You are missing something
99=64+32+2+1
find
99^1 (mod 47)
99^2 (mod 47)
99^4 (mod 47)
99^8 (mod 47)
99^16 (mod 47)
99^32 (mod 47)
99^64 (mod 47)
by repeated squaring
then find
(99^64)(99^32)(99^2)(99^1) (mod 47)
recall that at each step you may reduce mod 47 so in no step do you need to compute with a number larger than 46.

I now see the part about Fermats Theorem. Fermat had many theorems, I assume you mean Fermats little theorem.
So by Fermats little theorem
99^47=99 (mod 47)
99^99=(99^47)^2(99^5)=99^7 (mod 47) then the method I listed abouve can be used, but now less squares are needed
7=1+2+4
find
99^1 (mod 47)
99^2 (mod 47)
99^4 (mod 47)
then multiply them and reduce modulo 47
again making reductions modulo 47 as needed.

lurflurf, yes I meant Fermat's little theorem but how would you do 99^4 (mod 47) quickly?

Thanks

pivoxa15 said:
lurflurf, yes I meant Fermat's little theorem but how would you do 99^4 (mod 47) quickly?

Thanks
By repeated squaring with reduction modulo 47 as needed.
all bellow is mod 47
99^1=2*47+5=5
99^2=5^2=25
99^4=25^2=625=13*47+14=14
or even easier
99^4=5^3*5=125*5=(2*47+31)*5=31*5=155=14+3*47=14

remember that in mod arithmetic you cah reduce any numver mod whatever anytime you need to. 99=5 mod 47, that should be your first step.

## 1. What is Fermat's Theorem?

Fermat's Theorem, also known as Fermat's Little Theorem, is a mathematical theorem that states that if p is a prime number, then for any integer a, the number a^p - a is an integer multiple of p. In other words, it states that a^p is congruent to a (mod p).

## 2. How is Fermat's Theorem used to solve congruence equations?

Fermat's Theorem is used to solve congruence equations by reducing the exponent of the base number to a smaller number. For the equation 99^99 congruent to (mod 47), we can use Fermat's Theorem to reduce the exponent 99 to a smaller number, such as 2 or 3, which makes the calculation easier.

## 3. How does Fermat's Theorem help solve 99^99 congruent to (mod 47)?

Fermat's Theorem helps solve 99^99 congruent to (mod 47) by reducing the exponent 99 to a smaller number. In this case, we can reduce it to 2, since 47 is a prime number. This means that 99^99 is congruent to 99^2 (mod 47). We can then use modular arithmetic to solve for 99^2 congruent to (mod 47).

## 4. What is modular arithmetic?

Modular arithmetic is a branch of mathematics that deals with numbers in a cyclic pattern, or modules. It is often used in solving congruence equations, where the remainder of a division is the main focus rather than the quotient. In this case, we are using modular arithmetic to solve for 99^2 congruent to (mod 47).

## 5. Can Fermat's Theorem be used for all congruence equations?

No, Fermat's Theorem can only be used for congruence equations where the modulus is a prime number. If the modulus is not a prime number, then we cannot apply Fermat's Theorem. In this case, since 47 is a prime number, we can use Fermat's Theorem to solve 99^99 congruent to (mod 47).

• Engineering and Comp Sci Homework Help
Replies
1
Views
1K
• Math Proof Training and Practice
Replies
93
Views
10K
• Math Proof Training and Practice
Replies
80
Views
4K
• General Math
Replies
1
Views
1K
• General Math
Replies
1
Views
2K
• Math Proof Training and Practice
Replies
102
Views
7K
• Math Proof Training and Practice
Replies
52
Views
9K
• Math Proof Training and Practice
Replies
60
Views
8K
• General Math
Replies
26
Views
3K
• Math Proof Training and Practice
Replies
107
Views
15K