Exercise 2.3.41* ($f : n \mapsto \sum_{0<a<n, (a,n) = 1} a$ is one-to-one)

Proof. By Problem 40, $f(n)$, the sum of the positive integers less than $n$ and prime to $n$, is given, if $n\ge 2$, by

Suppose that $f(m)=f(n)$, where $m\ge 2,n\ge 2$. Then

If $n=1$, then $f(1)={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{0<a<1}a=0$ since the sum is empty. Therefore $f(m)=0$, so $m=1$. We can assume now that $m\ge 2,n\ge 2$.

Then the decompositions of $n,m$ in prime factors are

(It is more convenient here to arrange the prime numbers in descending order.)

Then (1) gives

that is

All prime factors of $p_1-1,\dots ,p_k-1$ are less that $p_1$. It is important to note that the exponents $2a_i-1$ are not zero, so that $p_i$ divides $P$ for every index $i$. Therefore, the greatest prime factor of $P$ is $p_1$. Similarly, considering the right member, the greatest prime factor of $P$ is $q_1$. The unicity of the decomposition in prime factors shows that $p_1=q_1$.

Since $p_1$ does not divide any other factor $p_2^{2a_2-1},\dots ,p_k^{2a_k-1},p_1-1,\cdots ,p_k-1$. The exponent of $p_1$ in the prime decomposition of $P$ is $2a_1-1$, and similarly the exponent of $q_1(=p_1)$ in the prime decomposition of $P$ is $2b_1-1$. Therefore

so $a_1=b_1$ and $p_1^{2a_1-1}=q_1^{2b_1-1}$. If we simplify both members of (2) by $p_1^{2a_1-1}=q_1^{2b_1-1}$, and $p_1-1=q_1-1$, we obtain

So we are in the same situation, which implies $p_2=q_2$, and $a_2=b_2,p_2^{2a_2-1}=q_2^{2b_2-1}$, by the same reasoning.

Without loss of generality, we can assume $k\le l$. Reasoning by induction, we can simplify, until exhaustion of one of the left member. If $k<l$, we obtain after all simplifications

This is impossible, so $k=l$. In this case, $p_i^{a_i}=q_i^{b_i}$ for all $i$, $1\le i\le k=l$, so $n=m$.

The function $f$ is injective. □