3
$\begingroup$

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.

3 Answers 3

4

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".

  • 0
    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.2010-11-11
3

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

2

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\:$.