- #1

- 14

- 0

I've been told it's quite easy, but I can't see why it's true for the life of me

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

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

- 14

- 0

I've been told it's quite easy, but I can't see why it's true for the life of me

Physics news on Phys.org

- #2

- 1,059

- 1

If r is a primitive root, then r^[(p-1)/2] is not equal to 1. The question is about -r.

- #3

- 14

- 0

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!

- #4

- 1,059

- 1

Sounds O.K. to me. Take, (-r)^2 = r^2, well then what power is necessry to raise r^2 to 1?

- #5

- 14

- 0

OK, I got it!

Bunch of thanks for your help!

Bunch of thanks for your help!

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.

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.

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

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.

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.

Share:

- Replies
- 2

- Views
- 606

- Replies
- 43

- Views
- 4K

- Replies
- 3

- Views
- 1K

- Replies
- 13

- Views
- 1K

- Replies
- 3

- Views
- 689

- Replies
- 3

- Views
- 488

- Replies
- 2

- Views
- 1K

- Replies
- 2

- Views
- 1K

- Replies
- 1

- Views
- 929