# A property of the totient function

Let $\ m\ge3$, and let $\ a_i$ be the natural numbers less than or equal to $\ m$ that are coprime to $\ m$ put in the following order: $$\ a_1<a_2<\cdots<a_\frac{\phi(m)}{2}\le \frac{m}{2}\le a_{\frac{\phi(m)}{2}+1}<a_{\frac{\phi(m)}{2}+2}<\cdots<a_{\phi(m)}.$$

If $\ a_{\frac{\phi(m)}{2}}>\frac{m}{2}$ and $\ a_{\frac{\phi(m)}{2}+1}\ge\frac{m}{2}$ then $\ a_{\frac{\phi(m)}{2}}+a_{\frac{\phi(m)}{2}+1}>m$ which is wrong.

If $\ a_{\frac{\phi(m)}{2}}\le\frac{m}{2}$ and $\ a_{\frac{\phi(m)}{2}+1}<\frac{m}{2}$ then $\ a_{\frac{\phi(m)}{2}}+a_{\frac{\phi(m)}{2}+1}<m$ which is wrong.

If $\ a_{\frac{\phi(m)}{2}}>\frac{m}{2}$ and $\ a_{\frac{\phi(m)}{2}+1}<\frac{m}{2}$ then $\ a_{\frac{\phi(m)}{2}+1}<a_{\frac{\phi(m)}{2}}$ which is wrong.

So $\ a_{\frac{\phi(m)}{2}}>\frac{m}{2}$ or $\ a_{\frac{\phi(m)}{2}+1}<\frac{m}{2}$ is wrong, $\ a_{\frac{\phi(m)}{2}}\le\frac{m}{2}$ and $\ a_{\frac{\phi(m)}{2}+1}\ge\frac{m}{2}$ is true, and it gives the result.

Does this proof work?

-
Notice that $k$ is coprime to $n$ iff $n-k$ is coprime to $n$. What does that tell you about the sequence $a_i$? – Olivier Bégassat Jul 26 '11 at 11:23
Your proof is not really a proof. You seem to have anticipated correctly that $a_{\frac{\phi(m)}{2}} + a_{\frac{\phi(m)}{2}+1}$ should sum to $m$. But without justifying this, the proof is incomplete. – Srivatsan Jul 26 '11 at 11:28
If we require monotonicity from $a_i$, I don't see how $a_{\frac{\phi(m)}{2}}>\frac{m}{2}$ can cohere with anything but $a_{\frac{\phi(m)}{2}+1}>\frac{m}{2}$. – Asaf Karagila Jul 26 '11 at 11:32
I'm using the fact that $\ a_{\frac{phi(m)}{2}}+a_{\frac{phi(m)}{2}+1}=m$ but I'm not seeking to prove it. – Chon Jul 26 '11 at 12:21
I can't see the problem: I considered a proposition that leads to a contradiction in all cases so the negation gives the result? – Chon Jul 26 '11 at 12:27