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$ Commented Mar 12, 2013 at 19:20
  • 5
    $\begingroup$ Because they are there? $\endgroup$ Commented Mar 12, 2013 at 22:27
  • 1
    $\begingroup$ @Gerry Myerson - The question asks for deeper reasons :) $\endgroup$ Commented 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$ Commented 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$ Commented 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$

You must log in to answer this question.

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