Partial solution : Observe that $r$ has a common factor with $n$ iff $n-r$ has a common factor with $n$. Hence, for $n>2$ if $n$ is odd, $n|f(n)$ and if $n$ is even $\frac{n}{2}|f(n)$. Hence if $p$ is a prime which doesn't divide $n, (n,n+p)=1$ and $n(n+p)|2f(n)\leq n(n+1)$ which is impossible Im working on the case $p|n$

I don't quite understand the problem... The point is, to prove for every $n>1$ and for every prime $p$ $f(n+p)\neq f(n)$??? If yes, the problem is equivalent to proving that there are no pairs $(n,p)$ such that $p(p+1+2n)=\phi((n+p)^2)-\phi(n^2)$. What now? EDIT: OK, I got somewhere. Let $d=(p,a+1)^2,e=(p,a)^2$ where $n=pa$ (the case $p\nmid n$ was proven by the previous poster) Now, using some facts about Euler's totient function, I derived after some transformations: $\frac{p+2a+1}{p-1}=(a+1)\phi(a+1)\frac{d}{\phi(d)}-a\phi(a)\frac{e}{\phi(e)}$ , so if $n$ is even, we can easily get that there are no such pairs $(n,p)$ if we let $p=2$. But the odd integers still make a problem...

we supose that f(n+p)=f(n). f(p)=p,f(2p)=f(p)=p,p=f(p)=f(2p)=f(3p)=...=f(pn) if we set n=p then we have f(p^2)=f(2p) but f(p^2)=p+p^2 >p

My partial solution to the case when $p$ divides $n$ (another one I've made precisely like lajanugen). We suppose that such $n$ and $p$ exist. It's not hard to show that if $\phi(n)$ is the number of integers not exceeding $n$ and mutually prime with it, then $f(n)=\frac{1}{2} n(n+1-\phi(n))$. Since $p$ divides $n$, we can take $n=kp$, and using the formula mentioned above, we'll obtain: $k(kp+1-\phi(kp))=(k+1)((k+1)p+1-\phi(kp+p))$. Apparently, there exists an integer $m$ such that: $kp+1-\phi(kp)=(k+1)m$ (*) and $(k+1)p+1-\phi(kp+p)=km$. (**) According to the known formula of $\phi(n)$, if $A$ is divisible by a prime number $Q$, then $Q-1|\phi(A)$. Hence, $\phi(kp+p)$ and $\phi(kp)$ are divisible by $p-1$. Let's consider our two equations by modulo $p-1$: $k+1=(k+1)m$ $(mod$ $p-1)$ and $k+2=km$ $(mod$ $p-1)$. Therefore, $p-1|m+1$ (after subtracting the second equation from the first), and $m \le p-1$ (otherwise (*) can't hold). If $p \ge 3$, then we get $m=p-2$. If $p=2$, then obviously $m=1$, but in this case from (**) we obtain $\phi(2k+2)=k+3$, that's impossible, because from the formula we have $\phi(2k+2) \le k+1$. Controversy. If $p=3$, then $m=1$. Analogously we have $\phi(3k+3)=2k+4$, which is refuted by the formula again. Let's consider $p=5$. Then, $m=3$ and $\phi(5k)=2k-2$, $\phi(5k+5)=2k+6$. If $5|k$ then $5|2k-2$ (we use the fact that if $A$ is divisible by $r^2$, then $\phi(A)$ is divisible by $r$, where $r$ is prime), which is impossible. In the same way we prove that 5 doesn't divide $k+1$. This means, that $\phi(5k)=\phi(5)\phi(k)=4 \phi(k)$, and $k-1=2\phi(k)$. From the second equation we have $k+3=2\phi(k+1)$. But hence $k$ is odd, and $\phi(k+1) \le \frac{k+1}{2} < \frac{k+3}{2} $ - controversy (we used $\phi(2t) \le t$ again). For another $p$-s, substituting $m=p-2$, using (*) we have $\phi(kp)=kp+1-(k+1)(p-2)=kp+1-kp-p+2k+2=2k-p+3$. But if $p|k$, $p|\phi(kp)=2k-p+3$ => $3|p$, but this case is already considered. Therefore, $p$ doesn't divide $k$, and $\phi(kp)=(p-1)\phi(k)$ (***), or $\phi(k)=\frac{2k-p+3}{p-1}$. (Likewise, $\phi(k+1)=\frac{2k+p+1}{p-1}$). So, we can conclude from (***) that $\phi(k)+1|k+1$. If we prove (or disprove at least ) the absence of such $k$ (except for $k=1$, that is unsuitable, as it's easy to show) - it will be great. It seems that among first 50 positive integers such ones don't exist. Can anyone help with this? Thanks. If you have any questions regarding my thoughts, I'm ready to clarify whatever I can .

cant we do this? the sum of the numbers lees than and relatively prime to $n$ is ${n{\phi n\}/2}}$ and the sum of the first $n$ numbers is $n(n+1)/2$,so $f(n)={n(n+1-\phi n\}/2}$

masum billal wrote: cant we do this? the sum of the numbers lees than and relatively prime to $n$ is ${n{\phi n\}/2}}$ and the sum of the first $n$ numbers is $n(n+1)/2$,so $f(n)={n(n+1-\phi n\}/2}$ Of course, I was using it - see the previous post.

Assuming everything BlackMax did is correct: One does not need to look at $\phi(k)+1\mid k+1$ in full generality, Instead, $\phi(k)=\frac{2k-p+3}{p-1}$ and $\phi(k+1)=\frac{2k+p+1}{p-1}$ together help a lot. The difference between $\phi(k+1)$ and $\phi(k)$ is 2 so one of these numbers will not be divisible by 4 - implying that either $k$ of $k+1$ will be either 4 (which can be analyzed by hand) or $q^m$ or $2q^m$ where $q$ is an odd prime. If for example $k=q^m$ or $k=2q^{m}$ then we can conclude $gcd(\phi(k), k)\mid 21$ - lest we have $q\mid p-3$ but we also have $p-1\mid k$ and this easily produces a contradiction since we would conclude that both $p-1$ and $p-3$ must be divisible by $q$ - here we assume $p>2$. But $gcd(\phi(k), k)=1$ implies that $m=1$ so that $k=q$ or $k=2q$. Both cases are solved by hand. The symmetric case for $k+1$ is done in the same way.

iura wrote: ... but we also have $p-1\mid k$ ... Why? I did obtain that $p-1 \mid 2k+2$, so this conclusion seems unclear for me. Anyway, thanks a lot for the idea, but please clarify it. However, using the property that either $k$ or $k+1$ is an odd prime's power (or double one) I've hopefully thought out another continuation of the solution: (since $q$ is an odd prime, we can use $q^{m-1}(q-1) \ge \frac{2}{3} q^m$, also we suppose $p \ge 7$, as the smaller cases are considered by me previously) 1) $k=q^m$ $\phi (k) = q^{m-1}(q-1) = \frac{2k-p+3}{p-1}$ $q^{m-1}(q-1)(p-1)=2q^m-p+3$, and: $4q^m \le \frac{2}{3}q^m(p-1) \le q^{m-1}(q-1)(p-1)=2q^m-p+3 \le 2q^m-4$ - contradiction. 2) $k=2q^m$ $\phi (k) = q^{m-1}(q-1) = \frac{2k-p+3}{p-1}$ $q^{m-1}(q-1)(p-1)=4q^m-p+3$, and: $4q^m \le \frac{2}{3}q^m(p-1) \le q^{m-1}(q-1)(p-1)=4q^m-p+3 \le 4q^m-4 $ - contradiction. 3) $k+1=q^m$ $\phi (k+1)=q^{m-1}(q-1)=\frac{2k+p+1}{p-1}$ $q^{m-1}(q-1)(p-1)=2q^m+p-1$ $\frac{2}{3}q^m(p-1) \le 2q^m+p+1 =2q^m+(p-1)$ $(\frac{2}{3}q^m-1)(p-1) \le 2q^m \le 4q^m$ => reduced to case 4 4) $k+1=2q^m$ $\phi (k+1)=q^{m-1}(q-1)=\frac{2k+p+1}{p-1}$ $q^{m-1}(q-1)(p-1)=4q^m+p-1$ $q^{m-1} \mid p-1$ => if $p=7$, we have $q=3$ and $m=1$ or $m=2$ => both cases can be done manually. Otherwise: $\frac{2}{3}q^m(p-1) \le 4q^m+p-1 =4q^m+(p-1)$ $\frac{20}{3}q^m-10 \le (\frac{2}{3}q^m-1)(p-1) \le 4q^m$ => we have $q=3$, $m=1$ again. Seems, that's all. Or something is wrong again?

mm yes, yes you're right, sorry. Your continuation works just fine though - essentially knowing that $k$ has few prime divisors means $\frac{\phi(k)}k$ is pretty large and yet it is less than $\frac 2{p-1}$ which bounds $p$.

iura wrote: mm yes, yes you're right, sorry. Your continuation works just fine though - essentially knowing that $k$ has few prime divisors means $\frac{\phi(k)}k$ is pretty large and yet it is less than $\frac 2{p-1}$ which bounds $p$. Just now I've noted that if $m=1$, then $q$ doesn't have to divide 6 (case 4). The drawback is eliminated manually again. At last, the problem is solved completely by us all together...

Can we make a synopsis to the topic. Is there another solution? Thanks.

$\phantom{every problem should have access to it }$

For the $n = pm$ case, continuing from $(p-1) | (2m+2)$, here's the case where $(p-1) | (m+1)$: \begin{align*} mp + p + 1 - \varphi(mp+p) &\equiv -1 + 1 + 1 - 0 \pmod{(p-1)} \\ &\equiv 1 \pmod{(p-1)} \\ \therefore (mp + p + 1 - \varphi(mp+p))/m &\equiv -1 \pmod{(p-1)} \\ \end{align*} But $mp + p + 1 - \varphi(mp+p) < mp + p \le mp + m = m(p+1)$, so $(mp + p + 1 - \varphi(mp+p))/m = p-2$. This means $(mp + 1 - \varphi(mp))/(m+1) = p-2$ as well. Now note that this means by some algebra that: \begin{align} \varphi(mp+p) &= 2m + p + 1, \end{align}\begin{align} \varphi(mp) &= 2m - p + 3. \end{align} Case 1: $p \not | m$. \begin{align*} (2) \Rightarrow 2m - p + 3 &= \varphi(m)\varphi(p) \\ \Rightarrow 2m + 2 - (p-1) &= \varphi(m)(p-1) \\ \Rightarrow 2\left(\frac{m+1}{p-1}\right) - 1 &= \varphi(m) \\ \end{align*} This means $\varphi(m)$ is odd, so $m = 2$. But now by (2), $4 - p + 3 = \varphi(2p) \Rightarrow 7 - p = p - 1 \Rightarrow p = 4$, which is absurd. Case 2: $p | m$. Now $p | \varphi(mp)$ by the usual formula, so $(2) \Rightarrow 2m - p + 3 \equiv 0 \pmod{p} \Rightarrow 3 \equiv 0 \pmod{p}$, and so $p = 3$. We now have $\varphi(3m) = 2m$. By the formula, it can be noted that this only occurs for $m = 3^k$. But now, \begin{align*} (1) \Rightarrow \varphi(mp + p) &= 2m + p + 1 \\ \Rightarrow \varphi(3(3^k+1)) &= 2 \cdot 3^k + 4 \\ \Rightarrow \varphi(3) \cdot \varphi(3^k+1) &= 2 \cdot 3^k + 2 \cdot 2 \\ \Rightarrow \varphi(3^k + 1) &= 3^k + 2 \end{align*} which is absurd. $\square$