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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .