# Question about primitive roots of p and $p^2$

If $g$ is a primitive root of a prime $p$, then $g$ is also a primitive root of $p^2$ if and only if $g^{p-1} \pmod p^2$ is not $1$. Is there a prime $p$ such that $p^2$ missing exactly $m$ primitive roots of $p$ , for arbitrarily large $m$ ? Does $m$ have a limit ?

• For odd $p$, and any fixed primitive root $g$ of $p$, there is exactly one $k$ modulo $p$ such that $g+kp$ is not a primitive root of $p^2$. So you are asking for the possible values of $\varphi(\varphi(p))$. For all $p$ except a few tiny ones, this is even. So we cannot miss exactly $47$ primitive roots. Jun 20, 2016 at 1:10
• So you mean we can miss 46 or 48? Jun 20, 2016 at 1:11
• Every even number is a new problem. But for instance it is not hard to show that there is no $k$ such that $\varphi(k)=14$. I can give you other examples if you wish: in elementary number theory courses, one useful accessible problem is to show that for a particular $a$, there is no $k$ such that $\varphi(k)=a$, so I have a small collection of such problems. Jun 20, 2016 at 1:22
• Okay I mean m is not necessarily successive Jun 20, 2016 at 1:25

For an odd prime $p$, and any fixed primitive root $g$ of $p$, there is exactly one $k$ modulo $p$ such that $g+kp$ is not a primitive root of $p^2$.

Thus the number of primitive roots "missed" by $p^2$ is the number of primitive roots of $p$, which is $\varphi(\varphi(p))$.

I do not know of an exact characterization of the numbers that cannot be $\varphi(k)$ for some $k$, let alone the ones that cannot be $\varphi(\varphi(p))$. But the only odd value attained by $\varphi(k)$ is $1$. And there are plenty of even numbers that are not attained, for example $14$.

• You mean the answer is yes ? For arbitrarily large $2m$ ? (m is not necessarily successive) Jun 20, 2016 at 1:21
• You can find lower bounds for $\varphi(n)$, for example here. Certainly $\varphi(n)\to\infty$ as $n\to\infty$,. In our case we are interested in $\varphi(p-1)$. So for arbitarily large $2m$, the number can be $2m$. Jun 20, 2016 at 1:44

We can prove something more generic.

Statement : ord$_{p^s}a=d\implies$ord$_{p^{s+1}}a=d$ or $p\cdot d$.

Proof:

Let ord$_{p^{s+1}}(a)=D$ and

let ord$\displaystyle_{p^s}a=d\iff a^d\equiv 1\pmod {p^s}=1+p^sq$ where $q$ is some integer

$\implies a^D\equiv 1\pmod{p^{s+1}}\equiv 1\pmod{p^s}\implies d\mid D$ i.e., $D=d\cdot k_1$(say) where $k_1$ is a positive integer.

Now, $a^{pd}=(a^d)^p=(1+p^sq)^p=1+\binom p1p^sr+\text{terms divisible by }p^{2s}\equiv 1\pmod{p^{s+1}}$ for $2s\ge s+1\iff s\ge1$

$\implies D\mid p\cdot d,$ i.e., $p\cdot d=k_2\cdot D,$(say) where $k_1$ is a positive integer.

Mutiplying $p\cdot d\cdot D=k_2\cdot D\cdot d\cdot k_1\implies k_1\cdot k_2=p$

Case$\#1:$ If $k_1=1,k_2=p,D=d\cdot k_1=d$

Case$\#2:$ If $k_2=1,k_1=p,D=d\cdot k_1=p\cdot d$

$\implies$ord$_{p^s}a=d\implies$ord$_{p^{s+1}}a=d$ or $p\cdot d$.