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.


1 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.

  • $\begingroup$ 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 $\endgroup$
    – Mark
    Sep 6, 2013 at 14:37
  • $\begingroup$ I was tempted to change the \psi notation to Euler's \phi notation for conventionality, but the OP used \psi in the Question, so I rolled back that edit. $\endgroup$
    – hardmath
    Aug 23 at 22:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .