6
$\begingroup$

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$

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

6 Answers 6

5
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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}$.

$\endgroup$
2
  • 1
    $\begingroup$ 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). $\endgroup$ Dec 6, 2021 at 10:13
  • $\begingroup$ @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. $\endgroup$ Dec 9, 2021 at 0:42
3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

Hint $ $ Negation $\rm\:n\to -n\:$ is an involution $\rm\:-(-n) \equiv n,$ so the cycles (orbits) of this permutation have length $2$ or $1.\ $ But length $1$ is not possible since $\rm\: -a \equiv a\:$ $\Rightarrow$ $\rm\:n\:|\:2a\:$ $\Rightarrow$ $\rm\:n\:|\:2,\:$ by $\rm\:(n,a)=1.\ $ Thus all cycles have length $\,2\,$ so have form $\rm\:(\color{#c00}{a,\,-a}).\:$ These cycles partition $\Bbb Z_n^*$ into pairs, and each pair sums to $\,\rm \,0 \equiv \color{#c00}{a -a},\,$ hence the entire sum is also $\,\equiv 0$.

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.