# Euler's Totient function $\forall n\ge3$, if $(\frac{\varphi(n)}{2}+1)\ \mid\ n\$ then $\frac{\varphi(n)}{2}+1$ is prime

While I was studying Euler's Totient function, $$\varphi(n)$$, I stumbled upon the marvelous book "Index to Mathematical Problems, 1980-1984" By Stanley Rabinowitz. In this page of the book (link to Google books sample), the open problems and conjectures about the Totient function appear. All are really awesome, but one of them was specially interesting to me:

CMB34 by M.V.Subbarao:

if $$(\varphi(n)+1)\ \mid\ n$$ then, $$n$$ or $$n/2 \in \Bbb P$$.

Well it has two parts, the 'trivial' one is that if $$n$$ is indeed a prime number, $$\varphi(n)=n-1$$, so $$\varphi(n)+1 = n-1+1 = n$$, and then $$n \mid n$$. But the other part is not trivial: when $$(\varphi(n)+1)$$ divides $$n$$ (even), then $$n/2$$ is a prime number. Simply amazing and still open (if I am not wrong).

I wanted to learn more, so I did my own try-outs of other combinations like CMB34, and I did find one that is very interesting, indeed I did not find any open conjecture or open problem about it, so here is my own proposed statement:

(1) $$\forall n\ge3$$, if $$(\frac{\varphi(n)}{2}+1)\ \mid\ n\$$ then $$(\frac{\varphi(n)}{2}+1)\in \Bbb P$$

And it really seems to work! I have made a Python test in the interval $$[1,50000]$$ and the statement is always true, no counterexamples. Here are some samples:

$$n = 52,\ \varphi(n)=24,\ \frac{\varphi(n)}{2}+1=13,\ 13\mid52$$, and $$13 \in \Bbb P$$

$$n = 57,\ \varphi(n)=36,\ \frac{\varphi(n)}{2}+1=19,\ 19\mid57$$, and $$19 \in \Bbb P$$

$$n = 66,\ \varphi(n)=20,\ \frac{\varphi(n)}{2}+1=11,\ 11\mid66$$, and $$11 \in \Bbb P$$

$$n = 68,\ \varphi(n)=32,\ \frac{\varphi(n)}{2}+1=17,\ 17\mid68$$, and $$17 \in \Bbb P$$

$$etc.$$

Having those results in mind, I tried to generalize to $$\frac{\varphi(n)}{2^i}+1, i\in\Bbb N$$. And for instance for the case $$i=2, (2^2)$$, apart from some specific initial small $$n$$ counterexamples $$n = \{3,4,6,28,36,66\}$$, for $$n\gt66$$ seems to be always true as well. I still did not try other values of $$i$$.

I have uploaded the test written in Python here.

I have continued trying to generalize, and the following statement seems also to be true always:

(2) $$\forall n\ge3, n=2k,\ k\in \Bbb N$$, if $$(\frac{\varphi(n)}{2}+1)\ \mid\ \frac{n}{2}\$$ then $$(\frac{\varphi(n)}{2}+1)\in \Bbb P$$

There are two differences with my main statement $$(1)$$: in this case, $$n$$ can only be an even number $$\ge3$$, so it can be divided by $$2$$, and the relationship is true when a factor of $$n/2$$ is found (instead of a factor of n). I will update the question if I find more successful combinations.

The same can be applied to those $$n$$ multiples of $$4$$, and in this case, the expression is (trivially) true when $$n = 4p\ \forall p \in \Bbb P, p\ge3$$, so the list of odd primes appears in the original natural order of the prime numbers:

(3) $$\forall n\ge3, n=4k,\ k\in \Bbb N$$, if $$(\frac{\varphi(n)}{2}+1)\ \mid\ \frac{n}{4}\$$ then $$(\frac{\varphi(n)}{2}+1)\in \Bbb P$$

This is in other words:

(3) $$\forall n\ge3, n=4k,\ k\in \Bbb N$$, if $$\frac{n}{4} = (\frac{\varphi(n)}{2}+1)$$ then $$(\frac{\varphi(n)}{2}+1)\in \Bbb P$$

In this case, the relationship is trivial for those $$n=4p$$ multiples of any $$p$$ prime, because

$$\frac{\varphi(4p)}{2}+1 = \frac{\varphi(4)*\varphi(p)}{2}+1 = \frac{2*\varphi(p)}{2}+1 = \varphi(p)+1 = p-1+1 = p$$

But the interesting point is that if $$n$$ is a multiple of $$4\ /\ n\not=4p, p \in \Bbb P$$ then the relationship is false always, so no primes are found. Anyway, the expressions (1) and (2) seem more interesting than (3).

I did not find any $$n$$ able to make the relationship true for $$\frac{n}{8}$$ or $$\frac{n}{16}$$.

The prime numbers $$p = (\frac{\varphi(n)}{2}+1)$$ generated by the expression (1):

1. Except for the case $$n=6$$ in the rest of cases the prime number $$p$$ seems to be always the greatest prime factor of $$n$$.

2. Trivial but interesting, if $$p$$ is factor of n, then $$(n/p)$$ is an upper bound of the other prime factors of $$q$$, so $$\forall q, q\in \Bbb P\ /\ q \not= p, \ q\mid n, \ q\le(n/p)$$.

And n is a subset of the numbers following the pattern:

$$n=(\frac{\varphi(n)}{2}+1)*k_1 /\ k_1 \in \{2,3,4,6\}$$

It could be possible that I can not see the wood for the trees, and my statement is trivial, or already known, or nonsense, so I would appreciate any help to understand those results.

I would like to share with you the following questions:

1. Is my proposed statement about the Totient function already known or trivial?
2. Is there a counterexample of it?
3. Could it be generalized?

Thank you!

** UPDATE 2015/04/22 ** My definition about the numbers $$n$$ covering the properties explained at the statement (1) has been accepted at OEIS! (link here).

** UPDATE 2015/05/01 ** Related question about other possible interesting property (link here):

(2)$$\ \forall n\in [3,29]\cup[31,1000000]$$,

if $$[(\frac{\varphi(n)}{2}+1)\ \mid\ n]\ \land\ [(\frac{\tau(n)}{2}+1)\ \mid\ n]\$$ then $$[(\frac{\varphi(n)}{2}+1)\cdot(\frac{\tau(n)}{2}+1)] = n$$

• @barto, thank you very much for the changes, much better now! – iadvd Apr 15 '15 at 9:01
• (+1) Nice question! amounts to asking for the set of primes $S = \{p_1,\cdots,p_k\}$ s.t., $\frac{1}{2}\prod\limits_{p \in S} (p-1) + 1 \vert \prod\limits_{p \in S} p$ :) – r9m Apr 15 '15 at 9:06
• @r9m cool, I did not think about it in that way :) – iadvd Apr 15 '15 at 9:10
• Note that if $n=3p$, $n=4p$, or $n=6p$ where $p$ is a prime, then $\frac{\varphi(n)}{2}+1 = p$, so the divisibility property holds in these cases. – rogerl Apr 17 '15 at 2:35
• There are no counterexamples through $n = 10^7$. – rogerl Apr 17 '15 at 2:35

It is not so difficult to see that your desired statement,

(1) $\forall n\ge3$, if $(\frac{\varphi(n)}{2}+1)\ \mid\ n\$ then $(\frac{\varphi(n)}{2}+1)\in \Bbb P$

is true if the Lehmer Totient Conjecture would be true (I am not sure about only if). This means that the statement (1) is a simple consequence of the Lehmer Totient Conjecture (a very difficult conjecture).

• thank you for the reference, any hint is very welcomed. – iadvd Apr 28 '15 at 2:46

Now I understand that this is the generic version of expression (1):

$\forall\ n=pk\ ,\ p\in\Bbb N\ ,$ if $\exists\ m\ /\ \varphi(m)=k\$ , then $\frac{\varphi(pk)}{\varphi(k)}+1 = p \mid n$

So the property is true only if the denominator of the fraction is one of the possible values taken by the totient function (OEIS link here) and the numerator contains a prime and a $k$ whose value $\varphi(k)$ is exactly the value of the denominator.

For instance for the family $k\in \{5,8,10,12\}$ whose $\varphi(k) = 4$ , the valid $n$ are $n=kp$ and the valid expressions are $\frac{\varphi(p5)}{4}+1=p$,$\frac{\varphi(p8)}{4}+1=p$, $\frac{\varphi(p10)}{4}+1=p$,$\frac{\varphi(p12)}{4}+1=p \mid n$.

The sequence for the case $k=2$ is very easy to convert into code and check running through $n$ so it deserved a place in the OEIS database (link here).