Let $ p=4k+1$ be a prime. Prove that $ p$ has at least $ \frac{\phi(p-1)}2$ primitive roots.
Problem
Source: Iranian National Olympiad (3rd Round) 2004
Tags: group theory, number theory proposed, number theory
09.01.2009 22:16
What's that¿ Every number $ n$ that has primitive roots has exactly $ \varphi(\varphi(n))$ of them (and this is rather straightforward to prove).
09.01.2009 22:18
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)
09.01.2009 22:30
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.
09.01.2009 22:33
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.
09.01.2009 22:34
He did not only mean it, he wrote it.
09.01.2009 23:10
ZetaX wrote: He did not only mean it, he wrote it. Hahah... You are great, ZetaX!
17.05.2010 09:05
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$.
04.02.2019 15:45
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$.
05.02.2019 20:07
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.