Problem: Prove that the sum of all integers $ t \in \{ 1, 2, \cdots, n \} $ and $ (t, n) = 1 $ is $ \dfrac {1}{2} n \phi (n) $, where $ \phi $ is the Euler Totient Function.

My proof:

Define the set $\mathcal{S}$ to be the set of all the elements $t$ such that $ 1 \le t \le n $ and $ (t, n) = 1 $. The cardinality of $\mathcal{S}$ is $\phi(n)$. For $ n = 2 $, the set $\mathcal{S}$ is $ \{ 1 \} $ and so the statement holds, since $ \dfrac {1}{2} \cdot 2 \cdot \phi(1) = 1 $. $ \\ $ $\mathrm{}\\$

Lemma: For natural $ n \ge 3 $, $\phi(n)$ is even.

Proof: If $n$ is a power of $2$, say $2^k$, then $\phi(n)=n \cdot \left( 1 - \dfrac {1}{2} \right) = \dfrac{n}{2}=2^{k-1}$, which is even, since $ n > 2 $. If $n$ is not a power of $2$, as to have at least one odd prime divisor, say $p$, from the Euler Totient Function formula, $$ \phi (n) = n \cdot \displaystyle\prod_{p \text { prime}, \ p \mid n} \left( \dfrac {p-1}{p} \right), $$and so, $(p-1)\mid\phi(n)$. Thus, since $p$ is odd, $2\mid\phi(n)$, which is to say that $\phi(n)$ is even. $ \Box $

$\mathrm{}\\$ From the Lemma, it follows that the cardinality of $\mathcal{S}$ is even, as long as $n\ge3$. We verified the statement for $n=2$, so what remains is $ n \ge 3 $. We will need the even cardinality of $\mathcal{S}$ shortly. Let $\mathcal{S}=\{t_1,t_2,\cdots,a_{\phi(n)}\}$. Let the desired sum be $R$. Now, note the following. If $t_k$ and $n$ are relatively prime, it follows that $n-t_k$ is relatively prime. Note that there is a bijection between $t_k$ and $n-t_k$, from Lemma $1$. That is, for every $t_k$, it follows that there is an $n-t_k$ that corresponds to it. If the cardinality of $\mathcal{S}$ was odd, this would not be the case.

We can now conclude that $ \{ n - t_1, n - t_2, \cdots n - a_{\phi(n)} \} $ is the same set as $ \{ a_1, a_2, \cdots, a_{\phi(n)} \} $, namely $\mathcal{S}$. We add up the two representations of $\mathcal{S}$. We have $$ a_1 + \cdots + a_{\phi(n)} = R = (n - a_1) + \cdots + (n - a_{\phi(n)}). $$Therefore, we solve for $R$ to get $ 2R = n \cdot \phi (n) $, or $ R = \dfrac {1}{2} n \phi (n) $, as desired.

$ \blacksquare $

Are there any other proofs or interesting results?


You don't need the lemma. For every $1\leq t \leq n$ with $(t, n)=1$, we have $(n-t,n)=1$. The map $t \mapsto n-t$ is a bijection, with itself as inverse: $t=n-(n-t)$. This has nothing to do with the parity of $\varphi(n)$.

The rest of your proof is correct: if $S=\sum_{(t,n)=1} t$, we have:

$$S = \sum_{(t,n)=1} t= \sum_{(t,n)=1} (n-t) = n\varphi(n) - S$$

so $$S = n\varphi(n)/2.$$

  • $\begingroup$ Will upvote when my vote lock is off. $\endgroup$ – Ahaan S. Rungta Nov 20 '13 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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