# Counting Primitive Roots modulo a prime with Totient Function

Let $\psi: \mathbb{N}^+ \rightarrow \mathbb{N}^+$ be the Totient function which counts the number of positive integers coprime to its argument. Let $p$ be a prime number.

Then the number of primitive roots modulo $p$ (elements $a \in$ the ring of integers mod $p$, s.t. $a^{p-1} = 1$) is $\psi(p-1)$.

I have here a proof, but due to my messy note taking I cannot understand it.

Define $A(e) = |\{a | \text{order}(a) = e\}|$ so $A$ counts the number of elements in the ring which have the order of $A$'s argument. We somehow show that $A = \psi$ so that $\sum_{e|p-1} A(e) = \sum_{e|p-1} \psi(e) = p-1$. And then we somehow complete the proof!

I hope someone may understand what my professor was saying.

In the bracket in your second paragraph it seems that you want to compute the cardinality of $$\{a\in\mathbb Z/p\mathbb Z\,|\,a^{p-1}=1\}.$$ This cardinality is $$p-1$$, as every element $$a$$ in the cyclic group $$(\mathbb Z/p\mathbb Z)^\times$$, which has order $$p-1$$, satisfies $$a^{p-1}=1$$.
But you also use the adjective "primitive". I think you are actually asking: "how many generators does $$(\mathbb Z/p\mathbb Z)^\times$$ have?" The answer to this second question is $$\psi(p-1)$$, where $$p-1=|(\mathbb Z/p\mathbb Z)^\times|$$. Indeed, in any finite cyclic group $$G$$ (hence a group which is isomorphic to $$\mathbb Z/n\mathbb Z$$, where $$|G|=n$$) there are exactly $$\psi(n)$$ generators. You can see it this way: write $$G=$$ for some generator $$x\in G$$. Then $$x^i$$ generates $$G$$ if and only if $$gcd(n,i)=1$$.
• Yes I was asking about generators sorry. There was a more general theorem: The number of elements of order $e$ is $\psi(e)$ (in a ring mod prime) and the result about the primitives follows as a corollary. And you give a more direct reasoning. Thanks