Take the 2-minute tour ×
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.

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

share|improve this question
1  
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
add comment

2 Answers

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$

$(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$

share|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.