Solving Congruence | Prime Numbers | 11^((p-1)/2) = 1 modp

  • Thread starter regularngon
  • Start date
In summary, Fermat's Little Theorem can be used to find all primes p (as a congruence) such that 11^((p-1)/2) = 1 modp. It appears that this only holds when (p-1)/2 is also a prime. However, it is not immediately clear how Fermat's Little Theorem implies this.
  • #1
regularngon
19
0

Homework Statement


Find all primes p (as a congruence) such that 11^((p-1)/2) = 1 modp

The Attempt at a Solution


I'm new to congruences and I don't really know to approach this. Any help greatly appreciated!
 
Physics news on Phys.org
  • #2
regularngon said:

Homework Statement


Find all primes p (as a congruence) such that 11^((p-1)/2) = 1 modp

The Attempt at a Solution


I'm new to congruences and I don't really know to approach this. Any help greatly appreciated!

That looks like a candidate for Fermat's Little Theorem: ap-1 is congruent to 1 for any prime p and any a not a multple of p. For what prime p is (p-1)/2 also a prime?
 
  • #3
Thanks for the reply. I did a few computations and indeed it seems to only hold for when (p-1)/2 is also a prime. I still don't see how Little Fermat implies this though...
 

FAQ: Solving Congruence | Prime Numbers | 11^((p-1)/2) = 1 modp

What is the significance of solving congruence with prime numbers?

Prime numbers are unique and have special properties that make them useful in mathematical calculations. Solving congruence with prime numbers can help in identifying patterns and relationships between numbers, leading to a better understanding of number theory.

How do you solve congruence equations involving prime numbers?

To solve congruence equations involving prime numbers, you can use various methods such as the Chinese Remainder Theorem, Fermat's Little Theorem, or Euler's Theorem. These methods involve manipulating the congruence equation to simplify it and find the solution.

What is the role of 11^((p-1)/2) = 1 modp in solving congruence with prime numbers?

This equation is known as the Euler Criterion and is used to determine whether a number is a quadratic residue (a number that has a square root modulo p) or not. It plays a crucial role in solving congruence equations involving prime numbers.

Can solving congruence with prime numbers be applied in real-world problems?

Yes, solving congruence with prime numbers has various applications in fields such as cryptography, coding theory, and computer science. Prime numbers are also used in determining the validity of credit card numbers and generating secure passwords.

Are there any limitations to solving congruence with prime numbers?

While prime numbers have many useful properties, they can also be challenging to work with, especially when dealing with large numbers. Additionally, solving congruence with prime numbers may not always lead to unique solutions, and there may be multiple solutions to a congruence equation.

Similar threads

Back
Top