If n is an integer, the numbers coprime to n, taken modulo n, form a group with multiplication as operation; it is written as (Z/nZ)× or Zn*. This group is cyclic if and only if n is equal to 2 or 4 or pk or 2 pk for an odd prime number p and k ≥ 1. A generator of this cyclic group, that is, all powers of some number g in Zn* is a number in Zn* is called a primitive root modulo n, or a primitive element of Zn*.
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 32 = 9, 33 = 13, 34 = 11, 35 = 5 and 36 = 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):
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). Then determine the different prime factors of φ(n), say p1,...,pk. Now, for every element m of (Z/nZ)×, compute
If the multiplicative order of a number k modulo p is p-1, then it is a primitive root. We can use this to test for primitive roots.
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 p0 such that, for every prime p ≥ p0, there exists a primitive root modulo p that is less than C p1/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.