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 ?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ 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. $\endgroup$– André NicolasJun 20, 2016 at 1:10
-
$\begingroup$ So you mean we can miss 46 or 48? $\endgroup$– sumpeloh miyapahJun 20, 2016 at 1:11
-
$\begingroup$ 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. $\endgroup$– André NicolasJun 20, 2016 at 1:22
-
$\begingroup$ Okay I mean m is not necessarily successive $\endgroup$– sumpeloh miyapahJun 20, 2016 at 1:25
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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$.
answered Jun 20, 2016 at 1:18
-
$\begingroup$ You mean the answer is yes ? For arbitrarily large $2m$ ? (m is not necessarily successive) $\endgroup$ Jun 20, 2016 at 1:21
-
$\begingroup$ 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$. $\endgroup$ Jun 20, 2016 at 1:44
$\begingroup$
$\endgroup$
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$.
