3
$\begingroup$

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?

$\endgroup$
5
  • 2
    $\begingroup$ See also oeis.org/A003277 and references there. $\endgroup$ Mar 12, 2013 at 19:20
  • 5
    $\begingroup$ Because they are there? $\endgroup$ Mar 12, 2013 at 22:27
  • 1
    $\begingroup$ @Gerry Myerson - The question asks for deeper reasons :) $\endgroup$ Mar 13, 2013 at 7:59
  • $\begingroup$ 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. $\endgroup$ Mar 13, 2013 at 22:06
  • $\begingroup$ 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... $\endgroup$ Mar 14, 2013 at 20:14

1 Answer 1

5
$\begingroup$

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))$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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