> [!NOTE] Proposition (Number of primitive roots of $(\mathbb{Z}/p\mathbb{Z})^\times$) > Let $p$ be a [[Prime Numbers|prime]]. If there exists a [[Primitive Root Modulo n|primitive root]] modulo $p$, then there are exactly $\varphi(p-1)$ of them, where $\varphi$ denotes the [[Euler Totient Function]]. > **Proof**: Suppose $g$ is a primitive root modulo $p.$ Then $|g|=\varphi(p)= p-1.$ Suppose for some $1\leq k\leq p-1$ that $g^{k}\in (\mathbb{Z}/p\mathbb{Z})^{\times}$ is a primitive root modulo $p.$ Then $|g^{k}|=p-1$ By [[Order of Power of Group Element]], $|g^{k}|= \frac{|g|}{\gcd(k,|g|)}= \frac{p-1}{\gcd(k,p-1)}.$Solving $|g^{k}|=p-1$ gives $\gcd(g,p-1)=1.$ Thus the set $\{ g^{k} \mid \text{for all } 1 \leq k\leq p-1 \text{ such that} \gcd(p-1,k) =1 \}$is precisely the set of primitive roots modulo $p.$ The set has precisely $\varphi(p-1)$ elements by definition of $\varphi.$ **Proof**: From [[Subgroups of Cyclic Group]], the number of generators of $C_{p-1}$ i.e. the number of elements of order $p-1$ is $\varphi(p-1)$.