# Sum of elements of a set where $\gcd(p,q)=1$

Is there a formula for the sum of the elements of the set $N(q) = \{p \mid \gcd(p,q)=1, p < q\}$ ?

-
When $q$ is a prime, yes :) then it would be $$\frac{q(q-1)}{2}.$$ In general, I don't know, so I will leave that to someone more knowledgeable. – Clayton Feb 18 '13 at 15:12
@Andreas: Actually \gcd is a native MathJax (and LaTeX) operator. :-) – Asaf Karagila Feb 18 '13 at 16:25
@AsafKaragila, that was absent minded of me, fixed, thanks. (The point being that I usually write it as $(a, b)$.) – Andreas Caranti Feb 18 '13 at 16:44

We know there are $\phi(q)$ positive integers $a<q$ such that $(a,q)=1$

where $\phi(q)$ Euler's totient function

For $q\ge3$ we know $\phi(q)$ is even.

If $1\le a\le \lfloor \frac q2\rfloor$ and $(a,q)=1$

$(q-a,q)=(a,q)=1$

So, we have $\frac{\phi(q)}2$ pairs of numbers $a$ and $q-a$ whose sum is $q$

So, the sum will be $\frac{q\phi(q)}2$ for $q\ge3$

-
– lab bhattacharjee Feb 18 '13 at 15:36

Hint $\$ Use Gauss's famous grade-school trick, pairing up terms around the center, noting that $\rm\: (k,q)\equiv 1\iff (q\!-\!k,q) = 1,\:$ omitting $\rm\color{tan}{terms}$ not comprime to $\rm\,q,\:$ e.g. for $\rm\,q=15$

$$\begin{array}{l} \begin{array}{rrrrrrrr} 1 & 2 & \color{tan}3 & 4 & \color{tan}5 & \color{tan}6 & 7 \\ 14 & 13 & \color{tan}{12} & 11 & \color{tan}{10} & \color{tan}9 & 8 \\ \hline 15 & 15 & & 15 & & & 15 \end{array} \\ \rm\ \ sum\, =\, 15\cdot 4\, =\, 15\cdot \phi(15)/2 \end{array}$$

Remark $\$ This trick of pairing up reflections around the average value is a special case of exploiting innate symmetry - here a reflection or involution. Here we essentially exploit the reflection symmetry arising from negation $\rm\ k\to -k\equiv q\!-\!k\,\ (mod\ q),\:$ after noting that the reflection restricts to units (invertibles) $\rm\:mod\ q.\:$ Such symmetry applications are ubiquitous in number theory and algebra, e.g. see these posts on Wilson's Theorem and its group theoretic generalization.

-