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](https://math.stackexchange.com/questions/1874236/are-there-at-least-3-non-divisors-of-eulers-totient-function-for-numbers-of-the)



There at least 4 divisors of $n-1$ which do not divide $\phi(n)$ if $n$ is a composite of the form $6k+1$
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:


1. $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.
2. $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.


