Exercise 2.3.40 (Sum of positive integers less than $n$ and prime to $n$)

Question

Prove that for $n \geq 2$ the sum of all positive integers less than $n$ and prime to $n$ is $n\phi(n)/2$.

Richard Ganaye · Accepted Answer

\begin{proof} We use the symmetry $a \mapsto n -a$ in the set of $a \in ]\!]0, n[\![$ such that $a\wedge n = 1$.

Consider the set
\begin{align*}
A &= \{a \in  ]\!]0, n[\![ \ \mid a \wedge n = 1\}.
\end{align*}
Then the sum of all positive integers less than $n$ and prime to $n$ is
$$ S = \sum_{a\in A} a.$$
Consider now the two subsets of $A$
\begin{align*}
B &= \{a \in A \mid 0 < a < \frac{n}{2} \},\
C &= \{a \in A \mid  \frac{n}{2} < a < n \}.
\end{align*}
Since $n\geq 2$, if $n$ is even $n \wedge \frac{n}{2} =  \frac{n}{2} >1$, and if $n$ is odd, $n/2$ is not an integer. In both cases $n/2 
ot \in A$. Therefore
$$A = B \cup C,\qquad \varnothing = B \cap C.$$
This shows that 
\begin{align}
 S = \sum_{a\in A} a = \sum_{a \in B} a + \sum_{a \in C} a.
 \end{align}

Consider the maps
$$
\chi
\left\{
\begin{array}{ccl}
B & 	o & C\
a & \mapsto& n-a,
\end{array}
ight.
\qquad
\xi
\left\{
\begin{array}{ccl}
C & 	o & B\
b & \mapsto& n-b.
\end{array}
ight.
$$
$\chi$ is  well defined, because $a\wedge n = 1 \iff (n-a) \wedge n = 1$, and $0 \leq a < n/2 \Rightarrow n/2 < n-a < n$, so $a \in B \Rightarrow n-a \in C$. Similarly $\xi$ is well defined.

Moreover, for all $a \in A$,  $(\xi \circ \chi)(a) = n-(n-a) = a$, so $\xi \circ \chi = 1_B$, and similarly $\chi \circ \xi = 1_C$. This shows that $\chi$ is bijective.

A first consequence is that $|B| = |C|$, thus $|A| = |B| + |C| = 2 |B|$, so $|B| = |A|/2$. Since $|A| =\phi(n)$, this shows anew that $\phi(n)$ is even for $n\geq 2$, and
\begin{align}
|B| = \frac{1}{2} \phi(n).
\end{align}

Another consequence is
\begin{align*}
\sum_{a \in C} a &=\sum_{b \in C} b\
 &=\sum_{a \in B} \chi(a)\qquad \qquad  (b = \chi(a))\
 &= \sum_{a \in B} (n-a).
\end{align*}
Then (1) becomes
\begin{align*}
\sum_{a\in A} a &= \sum_{a \in B} a + \sum_{a \in C} a\
&= \sum_{a \in B} a + \sum_{a \in B} (n-a)\
&= \sum_{a \in B} [a + (n-a)]\
&= \sum_{a \in B} n\
&= n |B|\
&= \frac{n\phi(n)}{2} \qquad (by (2)).
\end{align*}
So
$$\sum_{0<a<n,\ a\wedge n = 1} a = \frac{n\phi(n)}{2} \qquad (n\geq 2).$$
\end{proof}

Exercise 2.3.40 (Sum of positive integers less than $n$ and prime to $n$)

Answers

Comments

Exercise 2.3.40 (Sum of positive integers less than $n$ and prime to $n$)

Answers

Comments

Add answer