MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
See also 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))$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.