Friday May 13 Primitive squareroots and quadratic residues L

(Friday, May 13. Primitive squareroots and quadratic residues.) Let g be a primitive squareroot modulo a prime p > 2. Show that g^p-1/2 -1 mod p. We had seen a while back that a^2-1/2 plusminus 1 mod p. Conclude from (i) that a quadratic residue cannot be a primitive squareroot.

Solution

(a) Let g be a fixed primitive root then the set of quadratic non residues is g^(2k-1) for k from 1 to (p-1)/2

i.e., g raised to odd powers.

let r=ord(g^(2k-1)) then since the order of g is p>2

we have p divides r(2k-1). since 2k-1 is relatively prime to p theb r=p .

This shows that the set of primitive roots contains the quadratic non residues

The set of quadratic residues are g^(2k) for k=1 to (P -1)/2 and

since g^(2k)^(p-1)/2 = g^(p-1)^k = 1^k |p}

= 1 |p| then ord (g^(k-1)/2 = -1 |p| divides (p-1)/2 . so it can never be a primitive root.

(b). from a its is concluded that the quadratic residue cannot e a primitive root.

The set of primitive roots = the set of quadratic non residues