# Why to count integers that are relatively prime to their euler function?

Let $N(x)$ be the number of positive integers $n\leq x$ such that $\gcd(n,\phi(n))=1$. Here $\phi(n)$ is the Euler totient function. A theorem of Erdos from 1948 says that
$$N(x) \sim \frac{e^{-C_0} x}{\log\log\log x},\quad x\to \infty,$$ where $C_0$ is the Euler constant. See also Theorem 11.23 in Montgomery-Vaughan's "Multiplicative number theory". Erdos quotes a result of Szele saying that these numbers are exactly those $n$ for which there is exactly one abstract group of order $n$.

My question is whether there is a deeper, or more enlightening, reason to count such integers?

-
See also oeis.org/A003277 and references there. –  Robert Israel Mar 12 '13 at 19:20
Because they are there? –  Gerry Myerson Mar 12 '13 at 22:27
@Gerry Myerson - The question asks for deeper reasons :) –  Lior Bary-Soroker Mar 13 '13 at 7:59
In general, mathematicians count things because that's what they do. No deeper reason is really required. The fact that in this case there is a connection to group theory, as well as to Carmichael numbers, is a bonus. –  Robert Israel Mar 13 '13 at 22:06
But there are infinitely many things to count. One usually has a good reason to count one thing and not the other. BTW I see that this site counts how many characters left... –  Lior Bary-Soroker Mar 14 '13 at 20:14

If $G$ is a group of order $n$ with $gcd(n,\phi(n))=1$, then $G$ is cyclic. Conversely, if $n$ is an integer, such that every group of order $n$ is cyclic, then $gcd(n,\phi(n))=1$. So, counting these numbers is certainly interesting in group theory.
Also nice (perhaps) is, that the the number of integers in $[1,n]$, coprime to $\phi(n)$ counts the number of incongruent primitive roots modulo $n$ , provided $n$ has a primitive root, i.e., the group $(\mathbb{Z}/n\mathbb{Z})^{\ast}$ is cyclic. Of course, this number is $\phi(\phi(n))$.