Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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

Your proof is correct, but you should clearly indicate where the proof starts and that you are using the result on the sum of two symmetric elements in the proof.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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