26.9.18

Finding a primitive root

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 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.