Using Fermat's Little Theorem: 18^{802}(mod29) Calculation

  • Thread starter bendaddy
  • Start date
  • Tags
    Theorem
In summary, Fermat's Little Theorem is a mathematical theorem that states that for a prime number p and an integer a not divisible by p, a^(p-1) - 1 is divisible by p. It is used in calculations to find the remainder when a number is divided by a prime number. The term "mod" is used to specify the remainder after division, and it allows for the simplification of the calculation using Fermat's Little Theorem. To calculate a^(p-1) mod p, the exponent can be broken down into smaller parts using the property (a*b) mod n = (a mod n * b mod n) mod n. However, this theorem only applies to prime numbers and cannot be
  • #1
bendaddy
4
0

Homework Statement


Use Fermat's Little Theorem to calculate 18[itex]^{802}[/itex](mod29)


Homework Equations


Fermat's Little Theorem: a[itex]^{p-1}[/itex][itex]\equiv[/itex]1(modp)
where in this case, a=18 and p=29


The Attempt at a Solution


By FLT, I found that 18[itex]^{28}[/itex][itex]\equiv[/itex]1(mod29)
So, 18[itex]^{802}[/itex][itex]\equiv[/itex](18[itex]^{28}[/itex])[itex]^{28.5}[/itex]*18[itex]^{4}[/itex](mod29)[itex]\equiv[/itex]18[itex]^{4}[/itex](mod29)[itex]\equiv[/itex]25(mod29)

So my solution is 25(mod29).
However, the solution my professor posted is 4(mod29) (**NOT -4(mod29)**). Pretty confused here... Is there something wrong in my logic?
 
Physics news on Phys.org
  • #2
hi bendaddy! :smile:
bendaddy said:
By FLT, I found that 18[itex]^{28}[/itex][itex]\equiv[/itex]1(mod29)
So, 18[itex]^{802}[/itex][itex]\equiv[/itex](18[itex]^{28}[/itex])[itex]^{28.5}[/itex]*18[itex]^{4}[/itex](mod29)[itex]\equiv[/itex]18[itex]^{4}[/itex](mod29)[itex]\equiv[/itex]25(mod29)

isn't 1814 minus 1 ? :confused:
 

1. What is Fermat's Little Theorem?

Fermat's Little Theorem is a mathematical theorem that states that for a prime number p, if a is any integer not divisible by p, then a^(p-1) - 1 is divisible by p. In other words, it provides a method for calculating the remainder when a number is divided by a prime number.

2. How is Fermat's Little Theorem used in this calculation?

In this calculation, we are using Fermat's Little Theorem to find the remainder when 18^(802) is divided by 29. By applying the theorem, we will be able to simplify the calculation and find the remainder without performing the entire exponentiation.

3. What is the significance of using mod in this calculation?

The term "mod" stands for modulo, which represents the remainder after division. In this calculation, we are using mod29 to specify that we want to find the remainder when 18^(802) is divided by 29. This allows us to use Fermat's Little Theorem to simplify the calculation.

4. How do you calculate 18^(802) mod 29?

To calculate 18^(802) mod 29, we first apply Fermat's Little Theorem. We know that 29 is a prime number, so we can rewrite the calculation as 18^(28*28+2) mod 29. From there, we can use the property that (a*b) mod n = (a mod n * b mod n) mod n to break down the exponent into smaller parts. Finally, we can use a calculator or perform the calculation by hand to find the remainder, which in this case is 4.

5. Can Fermat's Little Theorem be applied to any number and prime number combination?

No, Fermat's Little Theorem only applies to prime numbers. If the divisor is not a prime number, then the theorem does not hold. Additionally, the divisor must not be a factor of the base number. If these conditions are not met, then Fermat's Little Theorem cannot be used to simplify the calculation.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
1
Views
907
  • General Math
Replies
1
Views
1K
  • Nuclear Engineering
Replies
7
Views
2K
Replies
5
Views
1K
  • General Math
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
117
  • Linear and Abstract Algebra
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
Back
Top