4
$\begingroup$

Let $n$ be a positive integer. The Euler $\phi$-function is defined by

$$\displaystyle \phi(n) = \# \{1 \leq a \leq n-1 : \gcd(a,n) = 1\}.$$

It is in fact a multiplicative function, and one has the formula

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

Let $S_\phi(X)$ be the number of $1 \leq n \leq X$such that $\gcd(n,\phi(n)) = 1$. Does $S_\phi(X)$ have an asymptotic formula?

It is easy to see that for any prime $p$ we have $\gcd(p, \phi(p)) = 1$, so

$$\displaystyle S_\phi(X) \gg X (\log X)^{-1},$$

but whenever $n$ is not square-free, we have $\gcd(n, \phi(n)) > 1$. Therefore $S_\phi(X) \leq (1 - \zeta(2)^{-1}) X$.

$\endgroup$

1 Answer 1

8
$\begingroup$

Oeis has this as sequence A003277. Erdos proved in "Some asymptotic formulas in number theory" that $$S_{\phi}(X)=(1+o(1))\frac{Xe^{-\gamma}}{\log\log\log X}$$

$\endgroup$
1
  • 3
    $\begingroup$ Indeed, it is an amazing theorem (Pomerance and ... I'm forgetting the coauthor(s)) that for almost all integers $n$, the greatest common divisor of $n$ and $\phi(n)$ is exactly the part of $n$ composed of primes less than $\log\log n$. I guess one needs bounds on the "almost all" part to deduce the asymptotic formula above from this, but it does lead to the main term. $\endgroup$ Commented Oct 19, 2018 at 17:20

You must log in to answer this question.

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