Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
    
This is false when $n=2$. –  Chris Eagle Mar 27 '12 at 11:47
    
Good point. Thanks for clarifying. –  quantum Mar 27 '12 at 11:52
1  
$ax+ny=1$ implies $(n-a)(-x) + n(y+x)=1$ so $(n-a,n)=1$ –  Thomas Andrews Mar 27 '12 at 12:33

6 Answers 6

up vote 4 down vote accepted

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

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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\:(a,\:-a).\:$ These cycles partition the units into pairs which each sum to $0$, hence the entire sum of units is also $0$.

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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