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

  • $\begingroup$ Emm! As you observed numbers with such property are $15,33,35,51,65,69,77,85,87,91,95$, and so on. We can see that all of these numbers are basically of the form $pq$ for some prime $p$ and $q$ and all these have exactly 4 divisors. Not sure if that helps, but yeah some observation :) $\endgroup$ – crskhr Sep 22 '19 at 6:09
  • $\begingroup$ @crskhr This is not true in general. $255$ is the smallest number with this property which has more than $8$ divisors. $\endgroup$ – NiloS Sep 22 '19 at 6:12
  • 1
    $\begingroup$ No! You misunderstood me. $255=pqr$ which again is product of $3$ primes. What i was trying to hint at is the following: If such a $n$ exists, then $n$ is the product of distinct primes, each with exponent 1. $\endgroup$ – crskhr Sep 22 '19 at 6:14

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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