Fermats little theorem question

  • Thread starter Bob19
  • Start date
  • Tags
    Theorem
Bob are discussing how to solve the equation x^6 \ \equiv 24 \ \mathbf{mod} \ 68 using a method called "Repeated squaring". Alex shares a helpful link for solving the equation using this method. In summary, Alex and Bob are discussing the use of "Repeated squaring" to solve an equation and Alex provides a link for further assistance.
  • #1
Bob19
71
0
Repeated squaring

Hi
I have tasked with solving the following equation:
[tex] x^6 \ \equiv 24 \ \mathbf{mod} \ 68[/tex]
I'm told now that I need to use a method called "Repeated squaring to solve the equation above".
Any hints/idears on how I do this will be appriciated very much !
/Bob
 
Last edited:
Physics news on Phys.org
  • #2
Bob19 said:
Hi
I have tasked with solving the following equation:
[tex] x^6 \ \equiv 24 \ \mathbf{mod} \ 68[/tex]
I'm told now that I need to use a method called "Repeated squaring to solve the equation above".
Any hints/idears on how I do this will be appriciated very much !
/Bob
This should help:

http://web.usna.navy.mil/~wdj/book/node27.html

Alex
 
Last edited by a moderator:

1. What is Fermat's Little Theorem?

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, a^p is congruent to a modulo p.

2. Who discovered Fermat's Little Theorem?

The theorem was first stated by the French mathematician Pierre de Fermat in the 17th century. However, it was not proven until much later by other mathematicians.

3. What are the applications of Fermat's Little Theorem?

Fermat's Little Theorem has various applications in number theory, cryptography, and computer science. It is used in the RSA encryption algorithm, which is widely used for secure communication over the internet. It is also used in primality testing and generating pseudorandom numbers.

4. Can Fermat's Little Theorem be extended to non-prime moduli?

Yes, there is a generalization of Fermat's Little Theorem called Euler's Theorem, which states that for any positive integers a and n that are relatively prime, a^φ(n) is congruent to 1 modulo n, where φ(n) is the Euler totient function.

5. What are some examples of using Fermat's Little Theorem?

One example is checking if a number is a Carmichael number. These are composite numbers that satisfy Fermat's Little Theorem for all values of a that are relatively prime to the number. Another example is the Chinese remainder theorem, which uses Fermat's Little Theorem to find a unique solution to a system of congruences.

Similar threads

Application of Fermat's Little Theorem
    • Calculus and Beyond Homework Help
Replies
6
Views
1K
Chinese remainder theorem (CRT) question, flat shapes
    • Calculus and Beyond Homework Help
Replies
1
Views
1K
Congruence identities using Fermat's Little Theorem
    • Calculus and Beyond Homework Help
Replies
3
Views
2K
Divergence Theorem in Curvilinear Coordinates: Questions & Explanations
    • Calculus and Beyond Homework Help
Replies
1
Views
871
Proving Divisibility Using Fermat's Theorem
    • Calculus and Beyond Homework Help
Replies
4
Views
2K
I Noether's second theorem: two questions
    • Special and General Relativity
Replies
7
Views
1K
Test Tomorrow .Help Fermat's Little Theroem
    • Calculus and Beyond Homework Help
Replies
17
Views
3K
Fermat's Little Theorem and Exponential Congruences
    • Calculus and Beyond Homework Help
Replies
6
Views
2K
Green's Theorem vs Fundamental
    • Calculus and Beyond Homework Help
Replies
2
Views
2K
Doing Chi-square independence test in SPSS?
    • Calculus and Beyond Homework Help
Replies
2
Views
1K

Hot Threads

Recent Insights

Back
Top