- #1
yavanna
- 12
- 0
If [itex]p[/itex] is a prime and [itex]a[/itex] an integer coprime with [itex]p[/itex], why is
[itex]a^{\frac{p-1}{2}}\equiv -1 mod p[/itex] ?
[itex]a^{\frac{p-1}{2}}\equiv -1 mod p[/itex] ?
Proof of a^{\frac{p-1}{2}}=-1 mod p
- Thread starter yavanna
- Start date
-
- Tags
- Arithmetic
In summary, the conversation discusses the relationship between prime numbers, co-prime integers, and primitive roots. It is noted that the statement given is not always true and only works with primitive roots. The use of Fermat's little theorem and the definition of primitive roots is suggested to explain why this is the case. It is also mentioned that the period of a co-prime integer will always be a divisor of (p-1) and for primitive roots, the period is exactly (p-1).
- #2
- 22,183
- 3,321
It's not true. Consider p=5 and a=4.
- #3
yavanna
- 12
- 0
Yes, i was trying some examples and I think it only works with primitive roots... But why?
- #4
- 22,183
- 3,321
Are you aware of Fermat's little theorem?? Try to use that...
- #5
I like Serena
Homework Helper
MHB
- 16,336
- 258
Hah, that's basically the definition of a primitive root. 
Any co-prime "a" has a "period" indicating how soon it gets to "1".
Fermat's little theorem guarantees that (p-1) will bring it back to "1".
The actual period will be a divider of (p-1).
Only for primitive roots, the period is exactly (p-1).
Any co-prime "a" has a "period" indicating how soon it gets to "1".
Fermat's little theorem guarantees that (p-1) will bring it back to "1".
The actual period will be a divider of (p-1).
Only for primitive roots, the period is exactly (p-1).
1. What is "Proof of a^{\frac{p-1}{2}}=-1 mod p"?
The statement "Proof of a^{\frac{p-1}{2}}=-1 mod p" is a mathematical proof that relates to the properties of prime numbers. It states that for any prime number p and any integer a that is not divisible by p, the expression a^{\frac{p-1}{2}} is congruent to -1 modulo p.
2. Why is this proof important?
This proof is important because it is a fundamental result in number theory and has many applications in cryptography and other areas of mathematics. It also helps to deepen our understanding of prime numbers and their properties.
3. What is the significance of the exponent \frac{p-1}{2} in this proof?
The exponent \frac{p-1}{2} is significant because it is half of the value p-1, which is the Euler totient function of p. This function represents the number of positive integers less than p that are coprime to p. In other words, it represents the number of elements in the multiplicative group of integers modulo p.
4. Can this proof be extended to non-prime moduli?
No, this proof is specifically for prime moduli. The statement is not true for non-prime moduli, as there may not exist a primitive root that satisfies the congruence relation.
5. How is this proof related to Fermat's little theorem?
This proof is related to Fermat's little theorem, which states that for any prime number p and any integer a, a^{p-1} is congruent to 1 modulo p. This proof can be seen as a generalization of Fermat's little theorem, as it shows that a^{\frac{p-1}{2}} is congruent to -1 modulo p for any non-zero integer a, rather than just for a=1.
Similar threads
-
Linear and Abstract Algebra
-
Linear and Abstract Algebra
-
Linear and Abstract Algebra
-
Linear and Abstract Algebra
-
Precalculus Mathematics Homework Help
-
Linear and Abstract Algebra
-
Precalculus Mathematics Homework Help
-
Precalculus Mathematics Homework Help
-
Calculus and Beyond Homework Help
-
Precalculus Mathematics Homework Help