A primitive root of a prime p is an integer g such that g (mod p) has multiplicative order p - 1. More generally, if GCD(g, n) = 1 (g and n are relatively prime) and g is of multiplicative order ϕ(n) modulo n where ϕ(n) is the totient function, then g is a primitive root of n. The first definition is a special case of the second since ϕ(p) = p - 1 for p a prime. A primitive root of a number n (but not necessarily the smallest primitive root for composite n) can be computed in the Wolfram Language using PrimitiveRoot[n].

Artin's conjecture | Artin's constant | full reptend prime | multiplicative order | primitive element | primitive root of unity