I was just going over some old posts when I realized that I haven't talked about how to check if an integer k is primitive root of a prime p or a power of a prime p^r.
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.