5
$\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$
3
  • 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, 2016 at 14:09
  • $\begingroup$ Yup that is right $\endgroup$ Jul 29, 2016 at 16:41
  • 4
    $\begingroup$ Also posted to math.stackexchange.com/questions/1874236/… with no notice to either site. $\endgroup$ Jul 30, 2016 at 5:51

1 Answer 1

9
$\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$, 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.

$\endgroup$
2
  • $\begingroup$ Is ABC 'conjecture' (depending on the status of Mochizuki's claimed proof) anyhow involved here? $\endgroup$ Jul 29, 2016 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, 2016 at 14:57

Your Answer

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

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