Take for example n = 14. The elements of (Z/14Z)^{×} are the congruence classes of 1, 3, 5, 9, 11 and 13. Then 3 is a primitive root modulo 14, as we have 3^{2} = 9, 3^{3} = 13, 3^{4} = 11, 3^{5} = 5 and 3^{6} = 1 (modulo 14). The only other primitive root modulo 14 is 5.
Here is a table containing the smallest primitive root for various values of n (see A046145 (http://www.research.att.com/cgibin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A046145)):
n  primitive root mod n 

2  1 
3  2 
4  3 
5  2 
6  5 
7  3 
8   
9  2 
10  3 
11  2 
12   
13  2 
14  3 
No simple general formula to compute primitive roots modulo n is known. There are however methods to locate a primitive root that are faster than simply trying out all candidates: first compute φ(n), the order of (Z/nZ)^{×}. Then determine the different prime factors of φ(n), say p_{1},...,p_{k}. Now, for every element m of (Z/nZ)^{×}, compute
The number of primitive roots modulo n is equal to φ(φ(n)) since, in general, a cyclic group with r elements has φ(r) generators.
There exist positive constants C, ε and p_{0} such that, for every prime p ≥ p_{0}, there exists a primitive root modulo p that is less than C p^{1/4+ε}. If the generalized Riemann hypothesis is true, then for every prime number p, there exists a primitive root modulo p that is less than 70 (ln(p))^{2}.
Search Encyclopedia

Featured Article
