0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\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 '13 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.