# 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

• To make sure I understand: a non-totient divisor of $n$ is a divisor of $n-1$ not dividing $\phi(n)$, right? – Wojowu Jul 29 '16 at 14:09
• Yup that is right – Stacker Jul 29 '16 at 16:41
• Also posted to math.stackexchange.com/questions/1874236/… with no notice to either site. – Gerry Myerson Jul 30 '16 at 5:51

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$. 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 \cdots p_t$, where $p_0 = 3 \times 2^{r_0} + 1$ and $p_i = 2^{r_i} + 1$ for $i = 1,\cdots,t$. Without loss of generality, assume that the sequence $r_1, \cdots, 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.

• Is ABC 'conjecture' (depending on the status of Mochizuki's claimed proof) anyhow involved here? – Sylvain JULIEN Jul 29 '16 at 14:42
• @SylvainJULIEN I have edited the post and now it contains a complete proof. The ABC conjecture is not the same story: it does not involve an arithmetic function such as $\phi$ here. – WhatsUp Jul 29 '16 at 14:57