What's that¿ Every number $ n$ that has primitive roots has exactly $ \varphi(\varphi(n))$ of them (and this is rather straightforward to prove).

Yes, you're right! I didn't claim that problem is not easy, and students whom this exam was token from didn't know this easy fact. (This was first problem and easiest problem of an exam)

ZetaX wrote: What's that¿ Every number $ n$ that has primitive roots has exactly $ \varphi(\varphi(n))$ of them (and this is rather straightforward to prove). If $ n\not =p^k,2p^k,2,4$, then $ Z_n^*$ is not cyclic group, therefore had not primitive roots.

Yes, but he meant those $ n$'s that for those $ n$'s that we have a primitive root we have exactly $ \varphi(\varphi(n))$ primitive roots.

He did not only mean it, he wrote it.

ZetaX wrote: He did not only mean it, he wrote it. Hahah... You are great, ZetaX!

eh... but in the paper the problem was sth else : Prove that if $p=4k+1$ is a prime then there exist at least $\frac{\phi(p-1)}{2}$ natural numbers like $g$ such that $0 < g < p$ and $g$ is a primitive root modulo any power of $p$.

shoki wrote: eh... but in the paper the problem was sth else : Prove that if $p=4k+1$ is a prime then there exist at least $\frac{\phi(p-1)}{2}$ natural numbers like $g$ such that $0 < g < p$ and $g$ is a primitive root modulo any power of $p$.

This is also easy to prove since if $g$ is a primitive root mod $p$ but not $p^2$ then $g+p$ is a primitive root mod $p^2$.

Hmm @above Can you clarify your proof? I don't see how that gives $\phi (p-1)/2$ primitive root modulo $p^2$. Anyway, I use the fact that if $g$ is a primitive root modulo $p$, then so does $p-g$. For the proof of above proposition: we have $p-g\equiv g^a\pmod{p}$ for some $a\in \{ 0,1,2,\dotsc ,p-1\}$. We get $g^{a-1}\equiv -1 \equiv g^{(p-1)/2} \pmod{p}$ where $-1\leqslant a-1\leqslant p-2$. So $a-1=(p-1)/2$. So $p-g\equiv g^{1+(p-1)/2}$. Since $\gcd ( p-1,1+(p-1)/2 )=1$, we get the desired claim. Back to the problem. We'll show that at least one of the pair $g,p-g$ must be primitive root modulo $p^2$. Suppose to the contrary that they both are not primitive root modulo $p^2$. Let $k\in (0,p)$ be any primitive root modulo $p$ that is not a primitive root of $p^2$. We have $k^d\equiv 1\pmod{p^2}$ for some $d\mid p(p-1)$ that $d<p(p-1)$. If $p\mid d,$ we get $k^d\equiv k^{d/p}\pmod{p}\implies k^{d/p}\equiv 1\pmod{p}$ where $d/p<p-1$. Contradiction. So $p\nmid d$. But we also can't have $d<p-1$. Thus $d=p-1$. Applying the above result, we get $g^{p-1}\equiv 1\pmod{p^2}$ and $$(p-g)^{p-1}\equiv \binom{p-1}{1}p(-g)^{p-2}+(-g)^{p-1}\equiv 1\pmod{p^2}.$$Combining the two congruences gives us $-(p-1)pg^{p-2}\equiv 0 \pmod{p^2}$ which is clearly impossible. Done.