13
$\begingroup$

A classical theorem of Erdos shows that the density of numbers n with $\gcd(n,\varphi(n))=1$ is zero. Actually, something stronger is proven: the number of integers $n\leq N$ with $\gcd(n,\varphi(n))=1$ is $(1+o(1))\frac{e^{-\gamma}N}{\log(\log(\log(N)))}$.

Now I was wondering what can be said on the number (say $t(N)$) of square-free integers $n\leq N$ with $\gcd(n,\varphi(n))$ prime. To be honest, I am not interested on a full asymptotic description of this function of $N$. I am just happy to know whether $t(N)/N$ tends to zero.

$\endgroup$

2 Answers 2

10
$\begingroup$

Peter Mueller has given a full answer to your question already. But let me say a word about what's going on "behind the scenes." The key observation, which goes back at least to Erdos but is possibly older, is that for any fixed integer $M$, the set of $n$ with $\phi(n)$ divisible by $M$ has asymptotic density $1$. This is because all $n$ outside of a set of density zero have a prime factor $\equiv 1\pmod{M}$, which in turn traces back to the fact that the sum of the reciprocals of the primes $\equiv 1\pmod{M}$ diverges.

Anyway, let's apply this with $M:= \prod_{p \leq z}p$ for some large $z$. (Here $p$ always denotes a prime.) Then $M \mid \phi(n)$ for almost all $n$, and so $\gcd(n,M) \mid \gcd(n,\phi(n))$ for almost all $n$. So if $\gcd(n,\phi(n))$ is prime for such an $n$, then $\gcd(n,M)=1$ or $\gcd(n,M)=p$.

Now what are the odds that $\gcd(n,M)=1$ or $p$? The proportion of $n$ with $\gcd(n,M)=1$ is precisely $\phi(M)/M = \prod_{p \leq z}(1-1/p)$, and this is $\ll \frac{1}{\log{z}}$ by Mertens' theorem. What are the odds that $\gcd(n,M)=p$? Well, in this case, $p$ better be a prime $\leq z$, and then $\gcd(n,M)=p$ if and only if $p \mid n$ and $\gcd(n/p, M/p)=1$. So for each $p \leq z$, the odds are $$ \frac{1}{p} \frac{\phi(M/p)}{M/p} = \frac{1}{p} \prod_{\substack{q \leq z \\ q \neq p}}(1-1/q) \ll \frac{1}{p \log{z}};$$ summing over $p \leq z$ gives $$ \ll \frac{\log\log{z}}{\log{z}}. $$

Putting everything together, we see that the upper density of $n$ with $\gcd(n,\phi(n))$ prime is $\ll (\log\log{z})/\log{z}$ for each fixed large $z$. Since $z$ can be taken arbitrarily large, this density must in fact be $0$. Hence, $t(N)/N\to 0$.

This is the same strategy Erdos used to prove the result of his that you quoted, except that one doesn't fix $z$ but instead takes $z$ as a function of $N$ (roughly $\log\log{N}$). One has to be much more careful about error terms if one does this though.

$\endgroup$
16
$\begingroup$

By a result of Murty and Murty, the answer is yes, that is $t(N)/N$ tends to zero. More precisely, they prove the following: Let $t_k(N)$ be the number of $n\le N$ such that $\gcd(n,\varphi(n))$ has precisely $k$ distinct prime factors. Then \begin{equation} t_k(N)=(1+o(1))\frac{e^{-\gamma}N(\log\log\log\log N)^k}{k!\log\log\log N}. \end{equation}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.