Primitive root

Definition

Suppose $n$ is a natural number such that the multiplicative group modulo $n$, i.e., the group $(\mathbb{Z}/n\mathbb{Z}{)}^{*}$, is a cyclic group. (This happens if and only if $n$ is of one of these four forms: $2,4,p^k,2p^k$, where $p$ is a prime number and $k\in \mathbb{N}$. Then, a primitive root modulo $n$ is a residue class modulo $n$ that generates the cyclic group.

We often use the term primitive root for an integer representative of such a residue class.

The number of primitive roots modulo $n$, if the multiplicative group is cyclic, is $\phi (\phi (n))$ where $\phi$ is the Euler phi-function. This is because the order of the multiplicative group is Failed to parse (syntax error): {\displaystyle \varphi(n)</amth>, and the number of generators of a cyclic group equals the Euler phi-function of its order. ==Particular cases== ===Number of primitive roots=== Here are the particular cases: {| class="sortable" border="1" ! Value of <math>n}  !! Number of primitive roots |- | 2 || 1 |- | 4 || 1 |- | $p$ (odd prime) || $\phi (p-1)$ |- | $p^k$, $p$ odd, $k\ge 2$ || $p^{k-2}(p-1)\phi (p-1)$ |- | $2p$, $p$ odd || $\phi (p-1)$ |- | $2p^k$, $p$ odd, $k\ge 2$ || $p^{k-2}(p-1)\phi (p-1)$ |}

Values of primitive roots

For an odd prime $p$, any number that is a primitive root modulo $p^2$ continues to be a primitive root modulo higher powers of $p$. We thus list primitive roots only for numbers of the form $p$ and $p^2$.

Value of $n$	Number of primitive roots	Smallest absolute value primitive root ($-n/2$ to $n/2$)	Smallest positive primitive root	All primitive roots from $1$ to $n$
2	1	1	1	1
3	1	-1	2	2
4	1	-1	3	3
5	2	2,-2	2	2,3
7	2	-2	3	3,5
9	2	2	2	2,5
11	4	2	2	2,6,7,8
13	4	2	2	2,6,7,11

Facts

• Quadratic nonresidue that is not minus one is primitive root for safe prime
• Safe prime has plus or minus two as a primitive root