# What is sum of totatives of n(natural numbers $\lt n$ coprime to $n$ )?

Same question as in title:

What is sum of natural numbers that are coprime to $n$ and are $\lt n$ ?

I know how to count number of them using Euler's function, but how to calculate sum?

• What's a totative of $n$? Commented Feb 14, 2015 at 16:19
• Did you try the google? @Bernard en.wikipedia.org/wiki/Totative Commented Feb 14, 2015 at 16:29
• I see, it's just the units modulo $n$. Commented Feb 14, 2015 at 16:31
• @Bernard Technically, not true, because $n+1$ is a unit modulo $n$. They are the least positive representatives of the units modulo $n$. Commented Feb 14, 2015 at 16:32
• Addressed to the OP: see en.wikibooks.org/wiki/Famous_Theorems_of_Mathematics/….
– Avi
Commented Feb 14, 2015 at 16:33

Assume $n>2$. Then, if $n/2$ is an integer, then $n/2$ is certainly not a totative. Now it's easy to see that if $k$ is a totative, then $n-k$ is also a totative. So we can split $\phi(n)$ totatives into $\phi(n)/2$ pairs $\{k,n-k\}$, each containing two distinct elements (because $n/2$ isn't a totative) which sum to $n$. So sum of all totatives is $n\cdot\phi(n)/2=\frac{n\phi(n)}{2}$
Let's call this function $f$. Then $$f(n) = \sum_{i = 1}^{n - 1} \delta_{1}^{\gcd(i, n)} i = \frac{n \phi(n)}{2},$$ where $\delta$ is the Kronecker delta function and $\phi$ is Euler's totient function. Clearly if $n$ is prime, then $f(n) = T_{n - 1}$, where $T_n$ is the $n$th triangular number.
Work a few examples. I'll do two for you: $f(6) = 1 + 5 = \frac{6 \times 2}{2} = 2$ and $f(8) = 1 + 3 + 5 + 7 = \frac{8 \times 4}{2} = 16$.