**Conjecture:**If k^((p-1)/2) mod p is equal to (p-1) then k is a primitive root of p.

To check if k is a primitive root of p:

1. Compute x = k^((p-1)/2) mod p

2. If x == (p-1) then k is a primitive root of p

For example, Let p = 11.

2 is a primitive root of 11 and 2^5 = 10 mod 11

**Conjecture:**If k^(((p-1)(p^(r-1)))/2) mod (p^r) is equal to (p^r - 1) and k is the smallest such integer then k is a primitive root of p^r.

Note that there might be other primitive roots other than the smallest one.

As discussed many many many times on this blog only p, p^r, 2p, or 2p^r where p is some prime and r is an integer greater than 0 have primitive roots. All other integers do not.