Euler's Totient function $\forall n\ge3$, if $(n-\phi(n)) = \sqrt{n}\$,$\$then $(n-\phi(n)) \in \Bbb P$

Recently I opened a question about what it might be a new property of Euler's Totient function.

I am still studying the Totient function and I found another interesting relationship, it is very different from the ones I wrote in my former question, so I would like to ask about it apart because this might be another interesting topic. As far as I have checked, I did not find any reference to this property, but if I am wrong I will remove the question. This is my new proposed statement:

$\forall n\ge3$, if $(n-\phi(n)) = \sqrt{n}\$,$\$then $(n-\phi(n)) \in \Bbb P$

Meaning that $n=p^2$ is the perfect square of a prime $p$ if and only if the distance between $n$ and $\phi(n)$ is exactly $p$.

I have also tested this using Python, and no counterexamples are found in the interval $[1..7000]$.

Usually when I find these kind of possible properties I test them, but I do not have enough theoretical knowledge to prove them, so any comment, hint or explanation about it is very appreciated. So as usual my questions are:

1. Is my proposed statement about the Totient function already known or trivial?

2. Is there a counterexample of it? Thank you!

1 Answer

Your statement needs to be more precise.

The implication $\Rightarrow$ is obvious, if $n=p^2$ then it follows immediately from the definition or formula pf $\phi(n)$ that $n-\phi(n)=p$.

For the converse, you need to be more precise. The way in which is stated, is correct but trivial: you are saying $n=p^2$ if and only if $n=p^2$ and $n=(n-\phi(n))^2$.

If you mean $n=p^2 \Leftrightarrow n-\phi(n)$ is prime, this is not true. $n=15$ fails the converse.

Added

If $p=n-\phi(n)=\sqrt{n}$ it follows that $n=p^2$.

Now, it is easy to see that for all integers $m$ we have $\phi(m^2)=m \phi(m)$. Therefore

$$p=p^2-p\phi(p) \Rightarrow \phi(p) = p-1$$

This implies $p \in P$.

• I am trying to say: when $p=n-\phi(n) = \sqrt{n}$ then $p \in \Bbb P$. Probably is not written correctly, or it is trivial. Please let me know your thoughts, thank you! – iadvd Apr 16 '15 at 5:10
• @iadvd Added a proof – N. S. Apr 16 '15 at 5:20
• I have rewritten the expressions, I hope it will be better now. If it is trivial please let me know and I will remove the question. Thank you! – iadvd Apr 16 '15 at 5:21
• thank you very much for your kind explanation and the time you took for it, I always get lost on the multiplicative function properties! If you had some time and you are interested in the topic, please it would be great if you could have a look to a similar question I wrote yesterday, probably there is a similar reason and I am not able to understand it: math.stackexchange.com/questions/1235390/… – iadvd Apr 16 '15 at 5:29