Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Prove if $n$ has a primitive root, then it has exactly $\phi(\phi(n))$ of them.

Let $a$ be the primitive root then I know other primitive roots will be among $\{a,a^2,a^3 \cdots\cdots a^{\phi(n)} \}$ because any other number will be congruent modulo $n$ to one of these. Then I figured as the answer is $\phi(\phi(n))$ so for $a^k$ to be primitive root, $k$ must be coprime with $\phi(n)$.But I don't know the reason.Am I missing any silly point?

share|cite|improve this question
up vote 7 down vote accepted

Hint: If $G$ is a cyclic group of order $n$ generated by an element $g$, then the order of the element $g^m$ is $n/\gcd(m,n)$ (you should have seen this result shortly after cyclic groups were introduced). In particular $g^m$ is of order $n$, if and only if $\gcd(m,n)=1$.

share|cite|improve this answer

As you pointed out, if $g$ is a primitive root of $n \ge 3$, then the primitive roots must be among $g, g^2, \dots, g^{\varphi(n)-1}$.

To count the exact number, as you observed, we need to show that for $1 \le k \le\varphi(n)-1$, $g^k$ is a primitive root iff $k$ is relatively prime to $\varphi(n)$.

Suppose that $k$ is relatively prime to $\varphi(n)$. Then there exist integers $x$ and $y$ such that $xk=y\varphi(n)+1$. It follows that $(g^k)^x=(g^{\varphi(n)})^y g\equiv g\pmod{n}$. Since $g^{kx}\equiv g\pmod{n}$, for any $e$ we have $$g^e\equiv (g^{kx})^e\equiv (g^k)^{xe}\pmod{n}.$$ It follows that any power of $g$ is congruent to some power of $g^k$. This implies that $g^k$ is a primitive root of $n$.

On the other hand, if $k$ is not relatively prime to $\varphi(n)$, let $d \gt 1$ be a common divisor. Then $(g^k)^{\varphi(n)/d}\equiv 1\pmod{n}$, since $k\varphi(n)/d$ is a multiple of $\varphi(n)$. It follows that $g^k$ has order $\le \varphi(n)/d$, so cannot be a primitive root.

share|cite|improve this answer
I didn't understand " It follows that any power of $g$ is congruent to some power of $g^k$. This implies that $g^k$ is a primitive root of $n$." How $g^{kx} \equiv g \implies g^k\text{ is primitive root}$? – Saurabh Jul 5 '12 at 6:52
@SaurabhHota: For "any" $w$, $w\equiv g^e$ for some $e$. So if $g^{kx}\equiv g$, then $w\equiv g^e\equiv (g^{kx})^e\equiv (g^k)^{ex}$. – André Nicolas Jul 5 '12 at 7:04
Thanks, Now I have understood. – Saurabh Jul 5 '12 at 7:13
Thanks for the question!. I put in more detail in the answer, since what was there seems to have left doubts. – André Nicolas Jul 5 '12 at 7:15

For $a^k$ to be a primitive root, you have to show that $1,a^k,a^{2k},\dots,a^{(\phi(n)-1)k}$ are different (modulo $n$). So, show that if $\gcd(k,\phi(n))\ne1$ then these numbers aren't different (easiest way is by showing 1 is repeated), and show that if the gcd is 1 then the numbers are all distinct.

share|cite|improve this answer

If $a^k$ is primitive, then for any $m$ we have some $t$ such that $a^m=(a^k)^t=a^{tk}$, thus $tk\equiv m\mod \phi(n)$. If $k$ and $\phi(n)$ had gcd $c$, then $m=t(k/c)c+x(\phi(n)/c)c$ for some $t,x$ hence is divisible by $c$. If we let $m=1$ we get that $c=1$, thus $k$ and $\phi(n)$ are coprime.

On the other hand, if $k$ and $\phi(n)$ are coprime then we have some $t$ such that $tk\equiv 1\mod \phi(n)$, so for any $m$ we have $mtk\equiv m\mod \phi(n)$ thus $(a^k)^{mt}=a^m$. Hence $a^k$ is a primitive root.

Thus there is a bijection between the set of primitive roots and the set of positive integers less than $\phi(n)$ and coprime to it, of which there are $\phi(\phi(n))$. Thus there are $\phi(\phi(n))$ primitive roots.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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