Is the probability that n and phi(n) (totient function) are coprime one for random squarefree n?

Question

The probability that a prime p does not divide a random integer n is (1-1/p), so for random n we could argue that the probability that n and φ(n) are coprime is

$\prod_{p|n} \left(1-1/p \right) = \phi(n)/n.$

The average order of φ(n)/n is given by

${ 1 \over N } \sum_{n=1}^N {\phi(n) / n} = 6/\pi^2 + O(\log N/N).$

Now the probability that a random integer is squarefree is $6/\pi^2$.

So my question is: does gcd(n,φ(n))=1 for almost all squarefree n? Or to put it another way, for random squarefree n is the probability that n and φ(n) are coprime one? (Of course we have gcd(55,φ(55))=5, etc.)

I have not been able to find anything about this on the internet and so would like to know if this has been considered before. Thanks.

EDIT: Take integer N and let f(N) = number of squarefree n<=N such that gcd(n,φ(n))>1 (e.g. 21 or 55). Does f(N)/q(N) tend to zero as N tends to infinity, where q(N) is the number of squarefree numbers <= N?

Answer 1

Quite the reverse is true: The probability that $n$ and $\phi(n)$ are relatively prime is zero! More precisely, the ratio $$\frac{1}{N} \cdot \# \{ n : \ n \leq N \ (n, \phi(n))=1 \}$$ goes to $0$ as $N$ goes to $\infty$.

Proof: Fix a positive real number $\epsilon$, we will prove that this ratio is less than $\epsilon$ for $N$ sufficiently large. The product $(1-1/2)(1-1/3)(1-1/5)(1-1/7)(1-1/11) \cdots$ is zero (because $\sum 1/p$ diverges); choose $P$ such that $\prod_{p < P} (1-1/p) < \epsilon/2$.

We claim that, for $N$ sufficiently large:

• The proportion of $n$ which are not divisible by some prime less than $P$ is $< \epsilon/2$.

• The proportion of $n$ for which $\prod_{p < P} p$ does not divide $\phi(n)$ is $< \epsilon /2$.

So, with probability $> 1-\epsilon$, the GCD of $n$ and $\phi(n)$ is divisible by some prime less than $P$.

The first bullet point is easy: The density of primes not divisible by some prime less than $P$ is $\prod_{p < P} (1-1/p) + O(1/N) < \epsilon/2 + O(1/N)$.

For the second part, fix a prime $p$ less than $P$. The sum $$\sum_{\begin{smallmatrix} q \equiv 1 \mod p \\ q \ \mbox{prime} \end{smallmatrix}} \frac{1}{q}$$ diverges, by a quantitative version of Dirichlet's theorem. So we can find $Q$ such that $$\prod_{\begin{smallmatrix} q \equiv 1 \mod p \\ q \ \mbox{prime} \\ q \leq Q \end{smallmatrix}} (1- 1/q)$$ is arbitrarily small. Letting $K$ be the number of primes less than $P$, choose $Q$ such that this product is less than $\epsilon/(2K)$.

The probability that $p$ does not divide $\phi(n)$ is bounded above by the probability that $n$ is divisible by none of the primes in the above product. We constructed that probability to be less than $\epsilon/(2K)$.

So, for each of the $K$ primes $p$ less than $P$, the probability that $p$ does not divide $\phi(n)$ is less than $\epsilon/(2K)$. This establishes the second bullet point.

Answer 2

I'm not sure what you mean by a random integer $n$, but would you agree that the probability that a random squarefree integer be divisible by $55$ is nonzero? For if $55\mid n$ then $5\mid\gcd(n,\phi(n))$.

Added In Derek's new notation it's well-known that $q(N)\sim 6N/\pi^2$. This constant arises via $$\frac6{\pi^2}=\prod_p \left(1-\frac1{p^2}\right).$$ Sticking to the example of the number $55$, if $g_{55}(n)$ is the number of squarefree numbers up to $n$ that are divisible by $55$ then $g_{55}(n)=h_{55}(n/55)$ where $h_{55}(n)$ is the number of squarefree numbers up to $n$ that are not divisible by $55$. But $h_{55}(n)\sim\alpha n$ where $\alpha$ is the same Euler product with the $p=5$ and $p=11$ terms dropped: $$\alpha=\frac6{\pi^2}\frac{5^2\times 11^2}{24\times 120}.$$ Thus $$\frac{g_{55}(n)}{q(n)}\to\frac{55}{24\times 120}=\frac{11}{576}$$ as $n\to\infty$, but of course $f(n)/q(n)\ge g_{55}(n)/q(n)$.

Of course one can perform this argument with other numbers in place of $55$.

Answer 3

The asymptotics of the "cyclic numbers", i.e., numbers 'n' such that gcd(n,phi(n)) = 1 was worked out by Erdos in 1948. If I recall the numbers of such numbers less than n is asymptotically n*e^{-\gamma}/(log(log(n))).

The asymptotics of abelian and nilpotent numbers is not known. By the way, the term cyclic numbers was coined in our paper (Shankar and Pakianathan) although the problem of determining such numbers itself goes back to Burnside.

Answer 4

Also relevant is Sloane's A060679, orders of non-cyclic groups, which is $n$ such that $\gcd(n,\phi(n))>1$, and its complement A003277. Although the asymptotic density of the latter tends to zero, as David Speyer showed in one of the answers, they're not rare: one in 3 at 30,000, as the b-file shows. This is denser than the primes at that point. I wonder what asymptotic order they have?