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.

$\endgroup$

3 Answers 3

Reset to default
5
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Commented Nov 11, 2010 at 18:47
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.