Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 2 down vote accepted

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$


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$

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.