---
tag: 0KM2CJ80G7
kind: definition
name: Primitive root modulo n
aliases: [primitive-root]
msc: [11A07]
defines: 0F33KX9Q6F
uses: [0SBRX5CZ5R, 0VV04M41AN]
sources:
  - url: https://en.wikipedia.org/wiki/Primitive_root_modulo_n
    locator: Definition
---

## Definition

Let $n$ be a positive integer.
A primitive root modulo $n$ is an integer $g$ coprime to $n$ whose [[multiplicative order|0SBRX5CZ5R]] modulo $n$ is $\varphi(n)$, where $\varphi$ is [[Euler's totient function|0VV04M41AN]].

## Remarks

Equivalently, $g$ is a primitive root modulo $n$ when the powers $g, g^2, \dots, g^{\varphi(n)}$ represent all the residue classes coprime to $n$.
So a primitive root exists exactly when the group $(\mathbb{Z}/n\mathbb{Z})^\times$ is cyclic, and then $\overline{g}$ generates this group.
For example, $3$ is a primitive root modulo $7$: its powers are $3, 2, 6, 4, 5, 1$ modulo $7$.
There is no primitive root modulo $8$: each odd $a$ satisfies $a^2 \equiv 1 \pmod 8$, but $\varphi(8) = 4$.

## Explanations

### L1 human

A primitive root is a number whose powers run through all the residues coprime to $n$ before they come back to $1$.
Modulo $5$, the powers of $2$ are $2, 4, 3, 1$. So $2$ is a primitive root modulo $5$, but $4$ is not, since $4^2 \equiv 1$.