Counting Primitive Roots modulo a prime with Totient Function

Question

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.

Answer 1

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=<x>$ for some generator $x\in G$. Then $x^i$ generates $G$ if and only if $gcd(n,i)=1$.

I hope this helps.