If $n$ is composite then $\phi(n) < n-1$, hence there is at least one divisor $d$ of $n-1$ which does not divide $\phi(n)$. We call $d$ as the totient divisor of $n$. Trvially, if $n$ is prime then it has no totient divisor and if $n-1$ is prime then $n$ has exactly 1 totient divisor. The number of such integers $\le x$ is $\pi(x)$.

I counted how many integers $\le x$ have exactly $2,3,4,5, ...$ totient divisors. I observed nothing interesting. Then I counted how many even integers $\le x$ have exactly $2,3,4,5, ...$ totient divisors. I observed nothing interesting either. Finally I counted how many odd integers $\le x$ have exactly $2,3,4,5, ...$ totient divisors. I found something which looked interesting.

Let $T_{o}(n,x)$ be the number of odd integers $\le x$ which have $n$ totient divisors. I plotted the graph of $T_{o}(n,x)$ vs. $x$ for different values of $x$ and found a consistent pattern in them as shown below.

enter image description here

The red dots are the spikes and the green dots are the crests or local minima. We observe that every primes $>2$ appears on a green dot i.e. odd primes seem to appear only at the crests. This suggests odd numbers prefer to have a composite number of totient divisors i.e.somehow odd numbers do not like having a prime number of totient divisors.

Question: In the observed data why is $T_{o}(p,x) < T_{o}(p \pm 1,x)$, for a prime $p >2$. What is the phenomenon that is driving primes to appear on the local minimas?

If this observation is true then we can claim that

Odd numbers prefer not to have a prime number of totient divisors.

Note: Every prime $> 2$ is green but the converse is not true. We have a crest at 25.


2 Answers 2


The number of totient divisors of $n$ is $d(n-1)-d((n-1, \varphi(n))$. As $n$ gets large, then almost all $n$ have the property that $\varphi(n)$ is divisble by all small primes. The average number of prime divisors $p<y$ of $n-1$ is of magnitude $\log\log y$, hence, for almost all $n$ we have that the number of prime divisors of $(n-1, \varphi(n-1))$ tends to infinity. On the other hand the powerful part of $n-1$ is bounded, thus both $n-1$ and $(n-1, \varphi(n-1))$ are divisible by a large number of primes with exponent 1. Hence for almost all $n$ both $d(n-1)$ and $d((n-1, \varphi(n-1))$ are divisible by a growing power of 2, in particular, the number of totient divisors tends not to be prime.

  • $\begingroup$ Why is this bias not observed for even numbers? $\endgroup$ Sep 6, 2016 at 6:58
  • $\begingroup$ The argument sketched assumes that $n-1$ has a decent number of prime divisors. This will be true most of the same for large $n$, but for small $n$ a little help by being even becomes quite important. $\endgroup$ Sep 7, 2016 at 19:19

First, consider the number of divisors of a given number $m$. This is a product of numbers derived from the exponents of the prime factorization of $m$. The only way this is a prime is if $m$ is itself a prime to a power one less than some (likely different) prime. In general, think of the divisor lattice of $m$ as a parallelpiped of grid points, with the total number almost always composite.

Now consider throwing away a part of this block of divisors. Divisors $d$ of $m$ do not divide some other integer $f$ if and only if they do not divide a special divisor of $m$ which is $d'=\gcd(m,f)$. So out of our divisor block, we carve out a smaller block out of a corner, and consider how many are left.

If $d'$ and $m$ contain all the powers of a prime $p$ that divides $m$ (i.e. $p$ divides $m$ and $p$ does not divide $m/d'$), then the number of remaining divisors is composite. One way to see this is if $d$ divides $m$, $d$ does not divide $d'$ and $p$ does not divide $d$, then $dp^i$ also does not divide $d'$ for $i$ from 0 up to the appropriate power of $p$. (A situation where this fails and such a number is prime is if $m=q^jp^i$ for a prime $q$, and $i+1$ is prime, and then $d'$ has to be $m/q$. But the end point is to consider what usually happens, so this is like a measure 0 exception.)

Now to your situation. If $n$ is even, $n-1$ is odd and $\phi(n)$ has an odd divisor which may or may not relate to a divisor of $n-1$, and in general we do not expect $(n-1)/\gcd(n-1,\phi(n))$ to be coprime to any prime divisors of $n-1$. Not much to say without further analysis.

If $n$ is odd however, then both $n-1$ and $\phi(n-1)$ share some powers of $2$. I believe the effect you are seeing is when $\phi(n-1)$ has as many or more powers of $2$ than does $n-1$, which leads to the number of selected non-divisors of $\phi(n)$ being composite. $\phi(n)$ is divisible by 4 more often than $n$ is, for example.

Interesting data, but I don't see how much further you can take it, especially if you are looking at the conjecture $\phi(n)$ divides $n-1$ implies $n$ is prime.

Gerhard "But Enjoy The Journey Anyway" Paseman, 2016.08.25.

  • $\begingroup$ You might consider gathering more data for larger $x$. I note that prime power values for the number of nondivisors are also relatively low. You might be able to explain the distribution by looking at the distribution of the relative block sizes (compare the exponents in the factorizations of n-1 and gcd(n-1,\phi(n))). Gerhard "Data Isn't Always Number Shaped" Paseman, 2016.08.25. $\endgroup$ Aug 25, 2016 at 15:52

Your Answer

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

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