There at least 4 divisors of $n-1$ which do not divide $\phi(n)$ if $n$ is a composite of the form $6k+1$ If $n$ is composite then $\phi(n) < n-1$ (Euler's totient function) hence there must be one or more divisors of $n-1$ which do not divide $\phi(n)$. For lack of a better terminology, let us call these divisors as non-totient divisors. While studying non-totient divisors, I made the following observation:

Claim : A composite number of the form $6k + 1$ has at least four non-totient divisors.

I am looking for a proof or disproof of this claim. I have verified the claim for $n < 10^6$.
Note: As Gerry pointed out, the same has been posted in Math Stack Exchange
 A: The claim is true. Here is the proof, in several steps.

Proposition 1:
Let $n = 6k + 1$ be composite. If $n$ has less than three non-totient divisors (NTD for short), then $n$ falls in one of the two cases:


A. The number $n$ is of the form $3 \times 2^m + 1$ and satisfies $\phi(n) = 3 \times 2^{m - 1}$;


B. The number $n$ is of the form $2 \times 3^m + 1$ and satisfies $\phi(n) = 2 \times 3^{m - 1}$ or $4 \times 3^{m - 1}$.

Proof:
Let $n = 6k + 1$ be composite and having at most two NTDs. Immediately $6k$ is one of the NTDs. Moreover, we note that either $3k$ or $2k$ is NTD. In fact, if none of them is NTD, then both of them divides $\phi(n)$, which forces $\phi(n) = 6k$.
Hence exactly one of $3k$ and $2k$ is NTD, and the other is not. There are thus two cases:

*

*$2k$ is NTD and $3k$ is not NTD. Then $3k$ should divide $\phi(n)$, which implies $\phi(n) = 3k$. Let $2^m$ be the highest power of $2$ dividing $6k$. Then obviously $2^m$ is also NTD. Consequently $2k = 2^m$, which is our case A.


*$3k$ is NTD and $2k$ is not NTD. We then have $\phi(n) = 2k$ or $\phi(n) = 4k$. In both cases, let $3^m$ be the highest power of $3$ dividing $6k$. Then $3^m$ is also NTD, hence $3k = 3^m$, which is our case B.


Proposition 2: The case B in Proposition 1 does not exist.

Proof:
If $n$ is an example of the above case B, then $n$ is prime to $2$ and $3$, and there are at most two different prime divisors of $n$, because $\phi(n)$ is not divisible by $2^3$. Hence we have:
$$\frac{2}{3} > \frac{\phi(n)}{n} = \prod_{p \mid n}\left(1 - \frac{1}{p}\right) \geq \frac{4}{5} \cdot \frac{6}{7} = \frac{24}{35},$$
a contradiction.

Now it remains the case A. In the rest of this post, we will prove the

Proposition 3: The case A in Proposition 1 does not exist.

Proof:
Assume that $n$ is an example of the above case A.
Firstly, the number $n$ is square-free. This is simply because $n$ is prime to $2$ and $3$, which are the only prime divisors of $\phi(n)$.
In view of the form of $\phi(n)$, we may write $n$ as a product: $n = p_0 \cdot p_1 \dots p_t$, where $p_0 = 3 \times 2^{r_0} + 1$ and $p_i = 2^{r_i} + 1$ for $i = 1,\dots,t$. Without loss of generality, assume that the sequence $r_1, \dots, r_t$ is strictly increasing.
For every $i > 0$, since $p_i$ is a Fermat prime number, we know that $r_i$ is a power of $2$. In particular, we have $r_i \geq 2r_1$ for every $i\geq 2$.
Let $r$ be the mininum of $r_0$ and $r_1$, and look at the identity
$$3 \times 2^m + 1 = (3 \times 2^{r_0} + 1)(2^{r_1} + 1) \cdots (2^{r_t} + 1).$$
Modulo $2^{r + 1}$, we see that the only possibility is $r_0 = r_1 = r$. The product $p_0 p_1$ is then equal to $1 + 2^{r + 2} + 3 \times 2^{2r}$.
If $r \geq 3$, modulo $2^{r + 3}$ yields immediately a contradiction, since every $r_i$ is at least $2r$ for $i \geq 2$. Also, $r = 1$ is not possible, since $2^1 + 1 = 3$.
Hence the only possibility is $r = 2$, $p_0 = 13$, $p_1 = 5$. Looking at $r_2$: if $r_2 = 4$, modulo $32$ gives contradiction; if $r_2 \geq 8$, modulo $128$ gives contradiction.

This concludes the proof of the original claim.
