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.