# Why is the sum modulo n of elements in $\mathbb{Z}_n^*$ equal to 0?

I'm talking about the set $$\mathbb{Z}_n^* = \{x \in \mathbb{Z}_n : \text{gcd}(x,n)=1\}$$ I noticed that for $n>2$, if you add all the elements in the set, you get $0\mod{n}$. Can someone explain why this is? I also noticed that if $a$ is in the set, then so is $n-a$, but how can I go about showing that $\text{gcd}(n-a,n)=1$?

For example, $$\mathbb{Z}_8^* = \{1,3,5,7\}$$ And $1+7 = 8$, $3+5=8$. So $1+3+5+7 \equiv_8 0$

• This is false when $n=2$. Mar 27, 2012 at 11:47
• Good point. Thanks for clarifying. Mar 27, 2012 at 11:52
• $ax+ny=1$ implies $(n-a)(-x) + n(y+x)=1$ so $(n-a,n)=1$ Mar 27, 2012 at 12:33

Your remark is what you need.

Assume that $a \in \mathbb{Z}_n^*$ and some integer $k > 1$ divide both $n-a$ and $n$. Then $k$ would divide their difference $n - (n-a) = a$. Hence $k$ divide $n$ and $a$ and hence $a$ cannot belong to the set. Thus $n-a \in \mathbb{Z}_n^*$

Now you just need to observe that $a + (n-a) = n = 0$ in $\mathbb{Z}_n^*$ and $$\sum_{a \in \mathbb{Z}_n^*} a = \sum_{a \in \mathbb{Z}_n^*, a < n/2} (a + n-a) = 0.$$

This is an edit of my previous answer.

The following proof is incomplete and more complex than the simple argument that uses the simmetry $$a\to-a$$ of $$\Bbb Z_n^\times$$ employed, but is possibly the simplest case of a useful argument.

Assume first that $$n=p$$ is a prime. Let $$x\in\Bbb Z_p^\times$$. The multiplication by $$x$$ (i.e. the map $$a\mapsto ax$$) defines a permutation of $$\Bbb Z_p$$ which restricts to a permutation of $$\Bbb Z_p^\times$$. Therefore $$\sum_{a\in\Bbb Z_p^\times}a= \sum_{a\in\Bbb Z_p^\times}(xa)= x\sum_{a\in\Bbb Z_p^\times}a.$$ If $$n\neq2$$ we can always choose $$x\neq1$$ and the above identity shows that $$\sum_{a\in\Bbb Z_p^\times}a$$ must be $$0$$.

If $$n$$ is not prime the problem is that a congruence $$xA\equiv A\bmod n\qquad\qquad(*)$$ does not imply $$A\equiv 0\bmod n$$ even when $$x\neq1$$ is invertible in $$\Bbb Z_n$$ because $$A$$ may not be cancelled. The latter situation happens when $$A\notin\Bbb Z_n^\times$$, i.e. $${\rm gcd}(A,n)>1$$.

So, assume $$A\not\equiv0\bmod n$$ and write $$d={\rm gcd}(A,n)$$, $$A=Bd$$ and $$n=dm$$ and note that $${\rm gcd}(B,m)=1$$. The congruence $$(*)$$ becomes $$xB\equiv B\bmod m$$ which now implies $$x\equiv1\bmod m$$ because $$B\in\Bbb Z_m^\times$$. But the latter conclusion contradicts the possibility to choose $$1\neq x\in\Bbb Z_m^\times$$ when $$m\neq2$$, which is guaranteed by the fact that the canonical map $$\Bbb Z_n^\times\longrightarrow\Bbb Z_m^\times$$ is surjective.

In particular this proves the result when $$n$$ is odd and leaves open the only possibility that $$\sum_{a\in\Bbb Z_{2m}^\times}a=m$$ in $$\Bbb Z_{2m}$$.

• Beware that this proof only works for prime $\,n\,$ since it implicitly assumes nonzero elements are cancellable i.e. cancel $S\neq 0\,$ in $\,xS = S\Rightarrow x = 1\Rightarrow\!\Leftarrow,\,$ so $\,S=0,\,$ where $S$ is the sum. Please edit to restrict (vs. delete) the answer since it is being used as a dupe target (in the prime case). Dec 6, 2021 at 10:13
• @BillDubuque, hi Bill, funny thing to have to edit a post about 10 years after it was written. I modified the argument so to make it work for all $n$ odd but couldn't find a truely elementary way (except the same $a\to -a$ business, of course) to deal with the last case. Dec 9, 2021 at 0:42

If $d$ divides both $n-a$ and $n$ then it divides their difference, $n-(n-a)$, which is $a$.

Every common divisor of $n-a$ and $n$ is also a common divisor of $a$ and $n$. This shows that if $a$ is in $(\mathbb Z/n\mathbb Z)^\times$ then also $n-a$ is in this set. The pair $(a,n-a)$ sums up to $n$ which is congruent to $0$ modulo $n$. Also, the numbers $a$ and $n-a$ are distinct since $a \equiv n-a \pmod n$ would imply $n|2a$, hence $n|2$ (because $n$ and $a$ are coprime). For $n\neq 2$ this is a contradiction. For $n=2$, however, the statement is actually false since $(\mathbb Z/2\mathbb Z)^\times = \{1\}$ which does not sum up to $0$ modulo $2$.

Coprimes to $$\,n\,$$ are closed under negation, so $$\,a\,$$ and $$-a\,$$ $$\rm\color{#c00}{pair}$$ up and cancel out of the sum, so the sum is $$\equiv 0\,$$ (they always pair, else $$\, a \equiv -a\,$$ so $$\,n\,|\,2a,\ (n,a)\!=\!1$$ $$\Rightarrow$$ $$\,n\,|\,2,\,$$ contra $$\,n\!>\!2).\,$$ $$\bf\small QED$$

Said $$\rm\color{#c00}{pairing}$$ can be viewed group theoretically: negation $$\,n\to -n\,$$ is an involution $$\,-(-n) \equiv n$$, i.e. it's a permutation of order $$2$$ so its cycles (orbits) have length $$2$$ or $$1$$. These cycles partition $$\Bbb Z_n^*$$ into pairs $$(a,-a),\ a\not\equiv -a,\,$$ and singles $$(a),\ a\equiv -a$$. By above there can be no singles, and each pair sums to $$\,0\,$$ hence so too does the entire sum.

This is a prototypical example of Wilson's theorem for groups.

• Coprimes are closed under negation since coprimes are precisely the invertibles (units) $\bmod n$, and this is clear for invertibles: $aa^{-1}\equiv 1\Rightarrow (\color{#0a0}{-a})(\color{#c00}{-a^{-1}})\equiv 1,\,$ so $(\color{#0a0}{-a})^{-1}\equiv \color{#c00}{-a^{-1}},\,$ i.e. $\,1/(-a) = -1/a.\,$ We use the rep $\,n-a\equiv -a\,$ in the standard nonnegative residue system $\,\{0,1,2,\ldots, n-1\}.\ \$ May 8, 2023 at 1:44

Observe that if $\gcd(n-a,n)=d$ then $d|n$ and $d|(n-a)$. Since $d|n$, we have $d|a$. Hence $d|\gcd(n,a)=1$. So you have $d=1$.