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?
8
-
2$\begingroup$ What's a totative of $n$? $\endgroup$Bernard– Bernard2015-02-14 16:19:34 +00:00Commented Feb 14, 2015 at 16:19
-
1$\begingroup$ Did you try the google? @Bernard en.wikipedia.org/wiki/Totative $\endgroup$Thomas Andrews– Thomas Andrews2015-02-14 16:29:26 +00:00Commented Feb 14, 2015 at 16:29
-
1$\begingroup$ I see, it's just the units modulo $n$. $\endgroup$Bernard– Bernard2015-02-14 16:31:08 +00:00Commented Feb 14, 2015 at 16:31
-
1$\begingroup$ @Bernard Technically, not true, because $n+1$ is a unit modulo $n$. They are the least positive representatives of the units modulo $n$. $\endgroup$Thomas Andrews– Thomas Andrews2015-02-14 16:32:02 +00:00Commented Feb 14, 2015 at 16:32
-
2$\begingroup$ Addressed to the OP: see en.wikibooks.org/wiki/Famous_Theorems_of_Mathematics/…. $\endgroup$Avi– Avi2015-02-14 16:33:44 +00:00Commented Feb 14, 2015 at 16:33
|
Show 3 more comments
2 Answers
$\begingroup$
$\endgroup$
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$.
Now, I didn't figure this out on my own. The answer comes from here: Sloane's OEIS A023896.
As for why I like the Kronecker delta function, that's because I'm a demon.
$\begingroup$
$\endgroup$
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}$
