Past exam of the options II course of the University of Oxford / 2010 / C / C2 / i

A primitive root modulo $p$ is a residue class generating the cyclic multiplicative group $(\mathbb{Z}/p\mathbb{Z}{)}^{\times }$, so its order is $p-1$. If $g$ is one generator, all generators are $g^j$ with $\gcd (j,p-1)=1$. Thus the number iswhere $\phi$ is Euler's totient function. This includes $p=2$, with $\phi (1)=1$.