# How many numbers $n$ are there such that $\gcd(n,\phi(n)) = 1$?

Let $$f(x)$$ be the number of such natural numbers $$n \le x$$ such that $$\gcd(n,\phi(n)) = 1$$. Since $$\phi(n)$$ is even for $$n \ge 3$$, hence apart from $$1$$ and the trivial set of primes, all numbers with the above property must be square free odd composites. But not all square free composites have this property e.g. the number $$21$$ is an exception. The sequence of odd composite numbers with this property are $$15, 33, 35,51,65,69,77, 85,87, 91, 95, \ldots$$

My calculations for $$x = 6.5 \times 10^9$$ suggests that

$$0.23223 < \frac{f(x)}{x} < 0.27863$$

Question: What is known about the asymptotics of $$f(x)$$?

Related question: A conjecture on numbers coprime to its Euler's totient function

• Note that any such $n$ must be square free. Moreover, $n=2$ is the only such even number.... Since the density of square free numbers is $6/\pi^2$, these two observations should already show that the limit is less than .3... Adding extra observations will probably decrease much more, I would not be surprised if when you increase the $x$ you get smaller lowerbounds. – N. S. Sep 22 at 4:10
• @N.S. Yes that is true. Also my calculations are still running; the lower is increasing and the upper bound is decreasing and it looks like they will converge to a value of about $0.2554$. Not sure if it has a nice closed form expression. – Nilotpal Kanti Sinha Sep 22 at 4:16
• These are exactly the $n$ such that there is only one group of order $n$ up to isomorphism. (As Gerry points out in his answer, this is OEIS A003277: oeis.org/A003277) – Travis Willse Sep 22 at 15:58
• (And per that link these are the cyclic numbers.) – Travis Willse Sep 22 at 17:17

These numbers are tabulated at the Online Encyclopedia of Integer Sequences. It says, Erdős proved that $$a(n) \sim e^{\gamma} n \log \log \log n$$ (where $$a(n)$$ is the $$n$$th such number). The reference may be Paul Erdős, Some asymptotic formulas in number theory, J. Indian Math. Soc. (N.S.) 12 (1948) 75-78.

• ... and in particular, the limiting density is $0$, though the convergence is /very/ slow. – Travis Willse Sep 22 at 7:05
• @Travis . On MathOverflow, the expression $\log \log \log \log n$ came up in a number-theory result and one remark was that "it goes to infinity with great dignity". – DanielWainfleet Sep 22 at 10:23
• (...slow enough that Erdős' formula estimates a density on $[1, e^{e^{e^e}}]$ of $e^{-\gamma-1} \approx 0.20654\!\ldots$; $e^{e^{e^e}} \approx 2 \cdot 10^{1\,656\,520}$.) – Travis Willse Sep 22 at 16:30

This is a follow-up from Gerry's answer, an asymptotic formula with an error term can be found. Let $$N(x)$$ be the number of $$n\leq x$$ with the property $$(n,\phi(n))=1$$. Then

$$N(x)= \frac x{\log\log\log x}\left(e^{-\gamma}+O\left( \frac{\log\log\log\log x}{\log\log\log x}\right) \right).$$

This is outlined in Chapter 11 of 'Multiplicative Number Theory I' written by H. Montgomery and R. Vaughan. Especially Theorem 11.23 is the result of Erdős. Then in the Chapter 11-exercise 2, such formula is found.

The proof of Theorem 11.23 is consisted of estimates in the three cases. Let $$p=p(n)$$ be the smallest prime divisor of $$n$$.

1. $$p\leq \log\log x$$.

2. $$\log\log x < p\leq y = (\log\log x)^{1+\epsilon}$$.

3. $$y.

A hint given in the exercise is 'specify $$\epsilon$$ as a function of $$x$$'.

We take $$\epsilon = \frac{\log\log\log\log x}{\log\log\log x}$$, and apply these in the proof of Theorem 11.23. The result follows.

Then the estimate of $$n$$-th number $$a_n$$ with $$(a_n,\phi(a_n))=1$$, is

$$a_n=\left(e^{\gamma}+O\left(\frac{\log\log\log\log n}{\log\log\log n}\right)\right)n\log\log\log n.$$