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$?