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.

Need to prove this :

Let $a$ element in $\mathbb Z_n$ , then $a$ is the generator of group $(\mathbb Z_n,+)$ iff $\gcd(a,n)=1$

Have no idea how to prove this, would appreciate some guidance.

share|improve this question
1  
You mean a is a generator, not the generator of the group. –  1015 Dec 30 '12 at 17:15

4 Answers 4

up vote 1 down vote accepted

For the harder direction, consider the group elements $1\cdot a$, $2\cdot a$. and so on up to $n\cdot a$. Here $k\cdot a$ is an abbreviation for $a+a+\cdots +a$ ($k$ times).

If $1\le x\lt y \le n$, then $x\cdot a$ and $y\cdot a$ are distinct elements of our group. For suppose to the contrary that $x\cdot a\equiv y\cdot a\pmod{n}$. Then $n$ divides $(y-x)\cdot a$. But $n$ and $a$ are relatively prime, so $n$ divides $y-x$. This is impossible, since $1\le y-x\le n-1$.

Thus the objects $1\cdot a$, and so on up to $n\cdot a$ are distinct elements of our group. But the list has length $n$, so these must be all the elements of our group. This shows that $a$ is a generator of our group.

share|improve this answer
    
May I ask to look at my answer. Thanks Andre for your time and sorry for this request. ;-) –  Babak S. Dec 31 '12 at 9:15
    
@BabakSorouh: It is a good thing to point out the generalization, as you did. And the generalization is certainly correct. My inclination would be to deal with the general after the more concrete special case. –  André Nicolas Jan 6 '13 at 16:35

Just a useful theorem which generalizes your question:

Theorem: Let $G=\langle a \rangle$ be a cyclic group of order $n$. If $b\in G$ and $b=a^s$, then $b$ can generate a subgroup of $G$ of order $\frac{n}{\gcd(n,s)}$.

Here you are looking for thoes elements which generate whole group. And we know that all elements in $\mathbb Z_n$ are as $a^s$ for some $s$ wherein $a$ is the generator of $\mathbb Z_n$. If we take $a=1$ when $$\mathbb Z_n=\{0,1,2,...,n-1\}$$ then $x=s.1$ will generate whole group, according to above theorem, if $(s,n)=1$. This is what you want and other answers tell.

share|improve this answer

Hint: $n$ and $m$ are relatively primes iff there exist integers $u$ and $v$ such that $un+vm=1$.

share|improve this answer
    
OK au+nv=1 I knew that but cant see how it helps me. what are u and v?? –  baaa12 Dec 30 '12 at 17:07
    
@baaa12, $u,v$ are integers. This is a result on number theory. After that you write $au=1-nv$ and take the congruence class, i.e. $\bar a\bar u=\bar 1$. –  Sigur Dec 30 '12 at 17:12

Hint: if $a$ generates the group then $\bar 1$ should be obtained from $a$. But what does this mean in terms of congruence $\pmod n$?

share|improve this answer
    
Why the down vote? –  Sigur Dec 30 '12 at 17:02
    
a^k mod n = 1? didnt quite understand.... –  baaa12 Dec 30 '12 at 17:06
    
You are working whit additive group. So you should use $ka$. See the other hint above. –  Sigur Dec 30 '12 at 17:08

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.