Skip to main content
Changed $x$ to $N$ to agree with the notation of the original question
Source Link

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 $x$$N$ (roughly $\log\log{x}$$\log\log{N}$). One has to be much more careful about error terms if one does this though.

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 $x$ (roughly $\log\log{x}$). One has to be much more careful about error terms if one does this though.

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.

Source Link

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 $x$ (roughly $\log\log{x}$). One has to be much more careful about error terms if one does this though.