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?
Best Answer
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.