Primitive roots - annoying problem

In summary, if r is a primitive root of a prime number p \geq 3 and p \equiv 1 (mod 4), then -r is also a primitive root of p. This can be proven by showing that the order of -r cannot be lower than (p-1), as this would result in a contradiction with the fact that p is not equal to 2. This follows from the fact that (-r)^[(p-1)/2] is equivalent to r^[(p-1)/2] (mod p) when (p-1)/2 is even. It is also noted that raising r^2 to the power of 1 results in (-r)^2, making -r a
  • #1
Let [tex]r[/tex] be a primitive root of a prime number [tex]p \geq 3[/tex]. Prove that if [tex]p \equiv 1 (mod 4)[/tex], then [tex]-r[/tex] is also a primitive root of [tex]p[/tex].

I've been told it's quite easy, but I can't see why it's true for the life of me :frown:
 
Physics news on Phys.org
  • #2
If r is a primitive root, then r^[(p-1)/2] is not equal to 1. The question is about -r.
 
  • #3
thanks for the reply :smile:
if r is a primitve root then r^[(p-1)/2] is -1 (mod p). However, (-r)^[(p-1)/2] is the same since (p-1)/2 is even, am I right?

Where do we go from here? Maybe I could say that the order of (-r) couldn't be lower than (p-1), because if it was so, ord(-r)|(p-1)/2 and then (-r)^[(p-1)/2]=1(mod p) contradicting the fact that p [tex]\neq[/tex] 2?
Am I on the right track?

Thanks again! :smile:
 
  • #4
Richard Cypher: Am I on the right track?

Sounds O.K. to me. Take, (-r)^2 = r^2, well then what power is necessry to raise r^2 to 1?
 
  • #5
OK, I got it!
Bunch of thanks for your help!:biggrin:
 

1. What are primitive roots?

Primitive roots are numbers that, when raised to different powers, produce all the numbers in a given range. For example, in the range of 1 to 10, the number 3 is a primitive root because 3^1 = 3, 3^2 = 9, 3^3 = 27, and so on, producing all the numbers in the range.

2. Why are primitive roots an annoying problem?

Primitive roots can be considered an annoying problem because there is no known formula or algorithm for finding them for a given range. Instead, they must be found through trial and error or through complex mathematical calculations.

3. What is the significance of primitive roots?

Primitive roots have many applications in number theory, cryptography, and other fields of mathematics. They are also used in algorithms for generating pseudorandom numbers.

4. How can I determine if a number is a primitive root for a given range?

To determine if a number is a primitive root for a given range, you can use the "primitive root test." This involves raising the number to different powers and checking if all the numbers in the range are produced. If so, the number is a primitive root. However, this method can be time-consuming for larger numbers and ranges.

5. Can all numbers be primitive roots?

No, not all numbers can be primitive roots. The existence of primitive roots depends on the properties of the range and the number itself. Some ranges have multiple primitive roots, while others have none. Additionally, some numbers cannot be primitive roots for any range.

Suggested for: Primitive roots - annoying problem

Replies
2
Views
606
Replies
43
Views
4K
Replies
3
Views
1K
Replies
3
Views
488
Replies
2
Views
1K
Replies
2
Views
1K
Back
Top