I was investigating the natural numbers $n$ such that $\gcd(n,\phi(n)) = 1$ where $\phi(n)$ is the Euler totient function. Clearly $\phi(n)$ is even for $n > 2$ hence $\gcd(n,\phi(n)) \ge 2$ if $n$ is even. Again if $n = p$ is an odd prime then $\phi(p) = p-1$ which is trivially co-prime to $p$. Hence all non-trivial $n$ such that $\gcd(n,\phi(n)) = 1$ must be odd composites. Apart from $1$ and the trivial set of primes, the sequence of composite numbers with this property are $15, 33, 35,51,65,69,77, 85,87, 91, 95, \ldots$ I observed the following.
Conjecture: If $n$ is an odd composite number such that $\gcd(n,\phi(n)) = 1$ then the number of divisors of $n$ is a perfect
power of $2$.
Can this be proved or disproved?
Related question: How many numbers $n$ are there such that $\gcd(n,\phi(n)) = 1$?
Best Answer
If $\gcd(n,\phi(n))=1$, then $n$ must be square-free.
To see this, assume $p^2|n$ for some prime $p$. Then $p|\phi(n)$, and so $p|\gcd(n,\phi(n))$.
If $n=p_1\cdots p_m$ where $p_1,\ldots,p_m$ are distinct primes, then the divisors of $n$ are all numbers formed by the product of a subset of these, and there are $2^m$ such subset (including the whole set which results in $n$ itself, and the empty set which gives 1).