# primitive root

Given any positive integer $n$, the group of units $U(\mathbb{Z}/n\mathbb{Z})$ of the ring $\mathbb{Z}/n\mathbb{Z}$ is a cyclic group^{} iff $n$ is 4, ${p}^{m}$ or $2{p}^{m}$ for any odd positive prime $p$ and any non-negative integer $m$. A *primitive root ^{}* is a generator

^{}of this group of units when it is cyclic.

Equivalently, one can define the integer $r$ to be a primitive root modulo $n$, if the numbers ${r}^{0},{r}^{1},\mathrm{\dots},{r}^{n-2}$ form a reduced residue system^{} modulo $n$.

For example, 2 is a primitive root modulo 5, since
$1,\mathrm{\hspace{0.33em}2},{\mathrm{\hspace{0.33em}2}}^{2}=4,{\mathrm{\hspace{0.33em}2}}^{3}=8\equiv 3\phantom{\rule{veryverythickmathspace}{0ex}}(mod5)$
are all with 5 coprime^{} positive integers less than 5.

The generalized Riemann hypothesis^{} implies that every prime number^{} $p$ has a primitive root below $70{(\mathrm{ln}p)}^{2}$.

## References

Wikipedia, “Primitive root modulo n”

Title | primitive root |
---|---|

Canonical name | PrimitiveRoot |

Date of creation | 2013-03-22 16:04:33 |

Last modified on | 2013-03-22 16:04:33 |

Owner | CWoo (3771) |

Last modified by | CWoo (3771) |

Numerical id | 12 |

Author | CWoo (3771) |

Entry type | Definition |

Classification | msc 11-00 |

Synonym | primitive root modulo n |

Synonym | primitive element^{} |

Related topic | MultiplicativeOrderOfAnIntegerModuloM |

Related topic | PrimeResidueClass |

Related topic | UsingPrimitiveRootsAndIndexToSolveCongruences |