For which positive integers $n$ is $$n+\varphi(n)^2$$ a perfect power , where $\varphi(n)$ denotes the totient-function ?
The following pari/gp program searches for solutions :
gp > for(n=1,10^8,if(ispower(n+eulerphi(n)^2)>0,print1(n," ")))
4 19 2880 5859
gp >
So, upto $n=10^8$ , there are $4$ positive integers : $4,19,2880,5859$ , each giving a perfect cube. For a perfect square I tried the approach
$$n+\varphi(n)^2=(\varphi(n)+d)^2$$ which leads to $$n=2d\varphi(n)+d^2$$ hence $$\frac{n}{\varphi(n)}>2d$$ Hence for $d\ge 4$, $n$ must already have at least $22$ prime factors and exceed $3\cdot 10^{30}$
$d=3$ gives $n-9=6\varphi(n)$, hence $3\mid n$. If we have $n=3^s\cdot t$ with $3\nmid t$, we get $$n-6\varphi(n)=3^s\cdot t-6\cdot 3^{s-1}\cdot 2\varphi(t)=3^s(t-4\varphi(t))=9$$
So either $\ t-4\varphi(t)=1\ $ or $\ t-4\varphi(t)=3\ $. In both cases we can easily conclude that $t$ must be odd. Because of $\frac{t}{\varphi(t)}>4$, we can conclude $\omega(t)\ge 140$ and $t>4\cdot 10^{337}$
$d=2$ gives $n-4=4\varphi(n)$, hence $4\mid n$. With $n=2^s\cdot t$ with odd $t$ we get $$n-4\varphi(n)=2^s\cdot t-2^{s+1}\varphi(t)=2^s(t-2\varphi(t))=4$$
and because of $s\ge 2$ we can conclude $t-2\varphi(t)=1$ which would solve the Lehmer problem , which asks for a composite number $n$ with $\varphi(n)\mid n-1$
Finally $d=1$ gives $n-1=2\varphi(n)$ solving the Lehmer problem.
Since no solution for the Lehmer problem exists upto $10^{20}$, for a perfect square we must have $n>10^{20}$
from Hot Weekly Questions - Mathematics Stack Exchange
Peter
Post a Comment