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.

I understand that for a number $a$ to have a multiplicative inverse in mod $n$, it must be coprime to $n$; therefore, all numbers that do not have a multiplicative inverse mod $n$ must share a factor with $n$.

Now, my prediction was that if $n$ is even, then the sum of all numbers that do not have a multiplicative inverse mod $n$ is $\frac{n}{2}\bmod{n}$, and if $n$ is odd, then the sum is $0\bmod{n}$.

Originally my proof was constructed something like this: if $n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$, then the sum of all the elements of this array:

$$\begin{align} \begin{matrix} p_1 & p_2 & \cdots & p_k \\ 2p_1 & 2p_2 & \cdots & 2p_k \\ \vdots & \vdots & \cdots & \vdots \\ n-2p_1 & n-2p_2 & \cdots & n-2p_k \\ n-p_1 & n-p_2 & \cdots & n-p_k \end{matrix} \end{align}$$

would cancel out in the correct way. However, while trying to prove this, I hit a roadblock because I wasn't sure how to account for the multiplicity of the factors of $n$.

If I understand Wikipedia correctly, this is the same as finding the sum of all numbers that are not units in the ring of integers modulo $n$, $\mathbb{Z}/n\mathbb{Z}$. Is there any way to do this? If the result is so nice, I feel like there is also a nice way to prove this.

share|improve this question

3 Answers 3

up vote 4 down vote accepted

If $k$ is not coprime with $n$, then $n-k$ is not coprime with $n$ either. So you can group those $k$ by pairs $(k,n-k)$, and if $n$ is even and $\neq 2$ (and only in this case), $n/2$ is not coprime with $n$ and "alone".

share|improve this answer
    
I think that's what I was trying to get at and kept overcomplicating it... I'll probably take this as the answer but I'd like to see other interesting proofs as well. –  Eugene Bulkin Nov 11 '10 at 18:47

Note that if $(a,n) = 1$, then $(n-a,n)=1$.

share|improve this answer

HINT $\ $ It's a special case of Wilson's theorem for groups - see my answer here - which highlights the key role played by symmetry (here a negation reflection / involution). Namely, since your set is closed under negation, its non-fixed points $\rm -k\not\equiv k\:$ pair up and contribute zero to the sum, leaving only the sum of the fixed points $\rm - k\equiv k\ \iff\ 2\:k\equiv 0\:,\ $ so $\rm\ k\equiv 0\ $ if $\rm\: n\:$ is odd, else $\rm\ k \equiv 0,\ n/2\:$.

share|improve this answer

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.