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

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