1
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ Is ABC 'conjecture' (depending on the status of Mochizuki's claimed proof) anyhow involved here? $\endgroup$ – Sylvain JULIEN Jul 29 '16 at 14:42
  • $\begingroup$ @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. $\endgroup$ – WhatsUp Jul 29 '16 at 14:57

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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