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