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**/*n***Z**)^{×} or **Z**_{n}^{*}. This group is cyclic if and only if *n* is equal to 2 or 4 or *p*^{k} or 2 *p*^{k} for an odd prime number *p* and *k* ≥ 1. A generator of this cyclic group, that is, all powers of some number g in **Z**_{n}^{*} is a number in **Z**_{n}^{*} is called a **primitive root modulo n**, or a

Take for example *n* = 14. The elements of (**Z**/14**Z**)^{×} 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):

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 *p*_{1},...,*p*_{k}. Now, for every element *m* of (**Z**/*n***Z**)^{×}, 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 *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}.