Solving the Primitive Root Problem for g & -g Modulo p

[b0mb0nika]

let g be a primitive root of the odd prime p
show that -g is a primitive root or not according as
p==1 ( mod 4) or p==3(mod4)

how would i start in solving this problem
thanks

 

[robert Ihnot]

For p==1 Mod 4, there exists an X such that X^2 ==-1 Mod p. This is not true for p==3 Mod 4. If x is a primitive root then x^((p-1)/2) = -1 since the smallest power of x that is 1 Mod p is x^(p-1). So, those are the facts needed.

 

[wais]

To start solving this problem, we first need to understand what a primitive root is and how it relates to the given conditions of p.

A primitive root, also known as a primitive element, is an integer g that generates the multiplicative group of integers modulo p. This means that for any integer a coprime to p, there exists an integer k such that g^k ≡ a (mod p). In other words, g raised to different powers can produce all the possible remainders when divided by p.

Now, let's consider the two cases given: p ≡ 1 (mod 4) and p ≡ 3 (mod 4).

Case 1: p ≡ 1 (mod 4)
In this case, p can be expressed as p = 4q + 1 for some integer q. This means that p is congruent to 1 modulo 4.

Using this information, we can show that -g is also a primitive root modulo p.
Since g is a primitive root, we know that g^q ≡ -1 (mod p).
Multiplying both sides by -1, we get (-g)^q ≡ 1 (mod p).
This shows that -g is also a primitive root modulo p.

Case 2: p ≡ 3 (mod 4)
In this case, p can be expressed as p = 4q + 3 for some integer q. This means that p is congruent to 3 modulo 4.

Using this information, we can show that -g is not a primitive root modulo p.
Assume that -g is a primitive root, then (-g)^q ≡ 1 (mod p) for some integer q.
But we know that g^q ≡ -1 (mod p) from the definition of primitive root.
Multiplying both sides by -1, we get (-g)^q ≡ 1 (mod p).
This means that (-g)^q ≡ g^q ≡ -1 (mod p).
However, this contradicts the fact that g is a primitive root.
Therefore, -g is not a primitive root modulo p in this case.

In conclusion, the statement holds true and the solution depends on the congruence of p modulo 4. If p ≡ 1 (mod 4),